I'm very new to Prolog. I defined in graph.pl
the following graph:
And here's my Prolog code:
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).
I understand it like this: there is a path between vertex X
and vertex Y
only if there is an edge between vertex X
and vertex Z
AND there is a path between vertex Z
and vertex Y
(some kind of recursion).
Is that right for the presented graph? When I ask Prolog about the path between vertex A
and vertex F
it gives me true
... which isn't even right! What might be wrong in this code?
Cycles in the graph. You need to track what nodes you're visiting, and check them. Try this, using a helper predicate with an accumulator to track the visited nodes:
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).