15

I'm very new to Prolog. I defined in graph.pl the following graph:

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?

Guy Coder
  • 24,501
  • 8
  • 71
  • 136
yak
  • 3,770
  • 19
  • 60
  • 111
  • 5
    `;` is OR. `,` is AND. So your `path` clause is incorrect. – lurker Jan 16 '14 at 12:25
  • @mbratch: When I changed `;` to `,` Prolog hung out... giving no answer. For my graph the answer should be false/no. – yak Jan 16 '14 at 12:27
  • 3
    The `;` is still incorrect and must be `,`. The other problem is that the code doesn't handle the issue of paths that are in a circuit, so it can go round and round the circuit until stack overflow before it gets to a solution. You would need to collect a list of "where you've been" to make sure you don't repeat paths. – lurker Jan 16 '14 at 12:29
  • @mbratch: Ok,thanks, it makes sense now. But how should appropriate rule for my graph look like? – yak Jan 16 '14 at 12:35
  • 1
    One way is to have your rule collect a list of edges that you've traveled and not choose them if you've been there already. If you google 'prolog graph', you'll find several examples online that have this exact problem all spelled out, such as http://www.csupomona.edu/~jrfisher/www/prolog_tutorial/2_15.html. – lurker Jan 16 '14 at 12:45
  • I restored your original code, so all the comments (and your question) make sense (i.e. are in sync). – Will Ness Jan 16 '14 at 17:56
  • See [this](http://stackoverflow.com/q/26946133) for a general solution. – false Mar 23 '16 at 20:16

4 Answers4

16

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).
Nicholas Carey
  • 71,308
  • 16
  • 93
  • 135
  • The simpler way to get it done. Maybe memberchk/2 is preferable to member/2. – CapelliC Jan 18 '14 at 09:50
  • 1
    This predicate has some surprising practical applications. With a few simple changes, it can be used as an [English-to-Prolog translator](https://gist.github.com/jarble/05034095e3e208022c9ece90f03d00c1). – Anderson Green Sep 29 '16 at 05:09
7

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.

CapelliC
  • 59,646
  • 5
  • 47
  • 90
7

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, is a common idiom in !

To express the irreflexive transitive closure of edge/2, use 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.
Community
  • 1
  • 1
repeat
  • 18,496
  • 4
  • 54
  • 166
  • 2
    `edge(X,s(X)).` terminates universally, yet `closure(edge,0,X)` describes an infinite set that can only be described with infinitely many answers. Thus non-termination! – false May 13 '16 at 18:53
  • Terrific! And terrifying, too. Will edit to clarify! Thx! – repeat May 13 '16 at 19:51
2

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.

nxthor
  • 71
  • 5