graph - Definir gráfico en Prolog: borde y camino, encontrando si hay un camino entre dos vértices

transitive-closure

Question

Soy muy nuevo en Prolog. graph.pl en graph.pl el siguiente gráfico:

Y aquí está mi código de Prolog:

edge(a,e).
edge(e,d).
edge(d,c).
edge(c,b).
edge(b,a).
edge(d,a).
edge(e,c).
edge(f,b).
path(X,X).
path(X,Y):- edge(X,Z) ; path(Z,Y).

Lo entiendo así: hay un camino entre el vértice X y el vértice Y solo si hay un borde entre el vértice X y el vértice Z Y hay una ruta entre el vértice Z y el vértice Y (algún tipo de recursión).

¿Es correcto para el gráfico presentado? Cuando le pregunto a Prolog sobre el camino entre el vértice A y el vértice F , me da la true ... ¡que ni siquiera está bien! ¿Qué podría estar mal en este código?

Answer 1

¡Está revisando un ciclo! Ejecuté el ejemplo con el trace. comando previo, y vio, que el programa vuelve al problema para encontrar el camino de a a f después de completar el ciclo. ruta (a, f) necesita que la ruta (e, f) sea verdadera, siguiendo en notación corta necesitamos ser verdaderos:

(d, f), (c, f), (b, f), y luego (a, f) nuevamente.

Para resolver el ciclo, necesitas un mecanismo para evitar el ciclo. Mi primera Idea sería mantener una lista de nombres de nodo y también verificar, si la lista no incluye la X actual mientras verifica la ruta.

Answer 2

Ciclos en el gráfico. Debe rastrear qué nodos está visitando y verificarlos. Pruebe esto, usando un predicado auxiliar con un acumulador para rastrear los nodos visitados:

path(A,B) :-   % two nodes are connected, if
  walk(A,B,[]) % - if we can walk from one to the other,
  .            % first seeding the visited list with the empty list

walk(A,B,V) :-       % we can walk from A to B...
  edge(A,X) ,        % - if A is connected to X, and
  not(member(X,V)) , % - we haven''t yet visited X, and
  (                  % - either
    B = X            %   - X is the desired destination
  ;                  %   OR
    walk(X,B,[A|V])  %   - we can get to it from X
  )                  %
  .                  % Easy!

edge(a,e).
edge(e,d).
edge(d,c).
edge(c,b).
edge(b,a).
edge(d,a).
edge(e,c).
edge(f,b).

Answer 3

El formato que usa (edge ​​/ 2) tiene sentido para aprender sobre Prolog, y debe seguir los consejos de mbratch sobre el tutorial.

En realidad, ya hay buenas alternativas disponibles, en algunos casos con predicados útiles listos para funcionar: por ejemplo, en la biblioteca ( ugraph ), se puede alcanzar / 3. Ahora, con sus datos, este predicado de ruta / 2

path(X,Y) :-
    findall(A-B, edge(A,B), Es),
    vertices_edges_to_ugraph([],Es,G),
    reachable(X,G,Path),
    member(Y,Path).

hace

?- path(a,X).
X = a ;
X = b ;
X = c ;
X = d ;
X = e.

Veamos lo que significa:

findall(A-B, edge(A,B), Es)

poner en Es todos los bordes, con notación según lo requiera la biblioteca,

vertices_edges_to_ugraph([],Es,G)

construye en G el gráfico correspondiente

reachable(X,G,Path)

hacer una lista Ruta de todos los vértices accesibles (duh) desde X

member(Y,Path)

ver si Y está presente en Path.

Como realicé consultas con Y free , obtengo todos los vértices alcanzables de X, que ligé a a .

Answer 4

Si está interesado en saber si existe una ruta, pero no necesariamente en la (s) ruta (s) real (es), investigue el cierre transitivo de la relación binaria edge/2 .

Afortunadamente para ti, el cierre transitivo es una expresión común en Prolog .

Para expresar el cierre transitivo irreflexivo de edge/2 , use meta-predicate closure/3 -definido en la pregunta anterior " Definition of Reflexive Transitive Closure ":

?- closure(edge, X, Y). X = a, Y = e ; X = a, Y = d ; X = a, Y = c ; ...

Tenga en cuenta que el closure/3 tiene muy buenas propiedades de terminación.

Si todas las cláusulas de edge/2 son datos closure(edge, _, _) , ¡el closure(edge, _, _) termina universalmente! Mira:

?- closure(edge, _, _), false.
false.