es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Representaciones gráficas en Prolog

11 Jul, 2023 Programación

Considere el siguiente gráfico:

enter image description here

y que está descrito por el término Prolog siguiente:

graph([connected(a,[b,c]), connected(b,[a,c]), connected(c,[a,b,d]), connected(d,[c]) ]).

Me gustaría definir un predicado que transforme las conexiones anteriores en una lista de pares correspondientes. En otras palabras, un predicado que produzca [[a,b],[a,c],[b,c],[c,d]] para el término-gráfico dado anteriormente.

¿Podría aconsejarme cómo hacerlo?

Mi intento hasta ahora es el siguiente:

Mapear un vértice vecino de 2 a pares:

map2ne(adjacent(H,[K|T]),Pair) :-
    append([H],[K],L),
    append([H],T,M),
    append([L],[M],Pair).

Esto se ejecuta correctamente.

Mapear un vértice vecino de 3 a pares:

map3n(adjacent(H,[K,L|T]),Pair) :-
    append([H],[K],A1),
    append([H],[L],A2),
    append([A1],[A2],Z),
    append([H],T,M),
    append(Z,[M],Pair).

Esto también se ejecuta correctamente.

Pero cuando intento extenderlo a un vértice vecino de n, falla:

mapmany(adjacent(H, [K|_]),Pair) :-
    append([H],[K],L),
    append(L,[],Pair),
    mapmany(adjacent(H,[K|_]),M),
    append(M,Pair,Pair).

Y también falla esto, que tenía la intención de mapear muchos vértices vecinos de n a pares:

mapping(Map,Pairs) :-
    select(X,Map,Y),
    mapmany(X,PairX),
    append([PairX],Pairs),
    mapping(Y,Pairs).
Tags:  , , , ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Para transformar el grafo de términos en Prolog en una lista de pares correspondientes, podemos definir un predicado que utiliza la recursión para iterar sobre los nodos conectados y extraer sus pares. Aquí tienes una implementación de ejemplo:

    % caso base - un grafo vacío retorna una lista vacía
pairs([], []).

% extraer pares de nodos conectados y concatenarlos con los resultados de los nodos restantes
pairs([conectado(Nodo, Vecinos) | T], Pares) :-
    extraer_pares(Nodo, Vecinos, ParesNodo),
    pairs(T, ParesRestantes),
    append(ParesNodo, ParesRestantes, Pares).

% predicado auxiliar recursivo para extraer pares de un único nodo y sus vecinos
extraer_pares(_, [], []).

% extraer pares de vecinos restantes y concatenarlos con los pares del vecino actual
extraer_pares(Nodo, [Vecino | T], [[Nodo, Vecino] | Pares]) :-
    extraer_pares(Nodo, T, Pares).

    Para utilizar este predicado con el grafo de términos en Prolog proporcionado, lo llamaríamos de la siguiente manera:

    ?- graph([conectado(a,[b,c]), conectado(b,[a,c]), conectado(c,[a,b,d]), conectado(d,[c])]), pairs(X, Y).
X = [[a,b], [a,c], [b,a], [b,c], [c,a], [c,b], [c,d], [d,c]],
Y = [[a,b], [a,c], [b,c], [c,d]].

    Ten en cuenta que esta implementación incluye pares duplicados para aristas bidireccionales (por ejemplo, connected(a, [b, c]) y connected(b, [a, c])) – si se desea eliminar estos duplicados, se necesitaría un paso separado para eliminarlos.

Comments are closed.