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

Answer 2

If you are interested in knowing if a path exists—but not necessarily in the actual path(s)—compute the transitive closure of the binary relation edge/2.

Luckily for you, transitive-closure is a common idiom in prolog!

To express the irreflexive transitive closure of edge/2, use meta-predicate closure/3—defined in the earlier question "Definition of Reflexive Transitive Closure":

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

Note that closure/3 has very good termination properties.

If all clauses of edge/2 are ground facts, closure(edge, _, _) terminates universally! Look:

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

Answer 3

The format you use (edge/2) make sense for learning about Prolog, and you should follow mbratch' advice about the tutorial.

Actually, there are good alternatives already available, in some case with useful predicates ready to go: for instance, in library(ugraph), there is reachable/3. Now, with your data, this path/2 predicate

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

does

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

Let's see what it means:

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

put in Es all edges, with notation as required by library,

vertices_edges_to_ugraph([],Es,G)

builds in G the corresponding graph

reachable(X,G,Path)

make a list Path of all vertices reachable (duh) from X

member(Y,Path)

see if Y is present in Path.

Since I queried with Y free, I get all reachable vertices from X, that I bound to a.

Answer 4

It is checking in a cycle! I executed the example with the trace. command before hand, and saw, that the program returns to the problem to find the path from a to f after cycling around. path(a,f) needs path(e,f) to be true, following in short notation we need to be true:

(d,f), (c,f), (b,f), an then (a,f) again.

To resolv the loop you need a mechanism to prevent loop. My first Idea would be to keep a list of node-names and also check, if the list does not include the current X while checking the path.