Define graph in Prolog: edge and path, finding if there is a path between two vertices

Question

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?

Answer 1

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).