Prolog definition which detects a path

Question

Context, first. I have the following bi-directional graph.

Graph

Represented in Prolog like this:

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

connection(X,Y) :- relation(X,Y).
connection(X,Y) :- relation(Y,X).

So I have the relation between the nodes, and then the connections between the nodes related, as I said before, in both directions.

What I am looking to do is a prolog definition path(X,Y) capable to tell if there's a path in the graph between two nodes (giving true if, at least, one path exists between both nodes, and false if there's no existing paths between both nodes).

So, the goal output in this model should look like this:

?- path(a,d).
true.

?- path(b,a).
true. 

?- path(f,b).
true

?  path(a,g).  % The node g doesn't exist
false.

I know this involves using a visited list, and I had seen examples of this, but giving all the posible paths between two nodes. However, this isn't what I'm looking for. What I'm looking is a definition which detects if there is a path between two nodes, not to give all the posible paths between two nodes.

Edit: So, thanks to @mbratch, I can now adapt the suggested problem to a solution:

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

connection(X,Y) :- relation(X,Y).
connection(X,Y) :- relation(Y,X).

path_exists(X,Y) :- path(X,Y,_), !.

path(A,B,Path) :-
       travel(A,B,[A],Q), 
       reverse(Q,Path).

travel(A,B,P,[B|P]) :- 
       connection(A,B).
travel(A,B,Visited,Path) :-
       connection(A,C),           
       C \== B,
       \+member(C,Visited),
       travel(C,B,[C|Visited],Path).

I'm not sure I'm following what you want. Can't you take the solution given in the link you cited and change it to what you want? The link solves the problem of providing at paths between the nodes, and it sounds like you just want to know if a path exists between the nodes. — lurker, Jul 03 '13 at 21:22
@mbratch What i'm looking is to know **if a path exists between the nodes**, nothing else. — SealCuadrado, Jul 03 '13 at 21:27
If you run the example code shown in the link, if it returns at least one path, then you know a path exists. You can then do a little work to make it more efficient if needed. For example, have it stop when it finds the first path. It would fail if it found none. I think it's basically all the logic you need. — lurker, Jul 03 '13 at 21:31
@mbratch Yes, but there's a difference, in the example shown in the link you are giving `path(X,Y,P)`, with `X` and `Y` as nodes of the graph, and `P`, as a path list. When you run the example shown `path(1,5,P)`, in this case, `P` will give you all the posible paths between the nodes. In this case I am asking for, I am giving just the nodes (`1` and `5` in the example of the link), so, supposing `1` and `5` are nodes of my graph, the goal output of my program should be giving me **just true or false**, not all the possible paths. — SealCuadrado, Jul 03 '13 at 21:44
`path` in that example does everything you need. You can ignore `P`. You would have `path_exists(X, Y) :- path(X, Y, _), !.` and that's it. It stops if it finds one path and gives true. If it doesn't find a path, it gives false. — lurker, Jul 03 '13 at 21:50
That's what I was asking for, I tested it and it worked. That leaves me just to adapt the problem to the program proposed. Thanks! =D — SealCuadrado, Jul 03 '13 at 21:58

score 2 · Answer 1 · edited May 23 '17 at 12:07

What you want to get is commonly called "transitive closure of a binary relation".

We can obtain the transitive-closure of connection/2 by using meta-predicate closure/3 like this:

% Q: Which `To` can be reached via `connection` starting at `From`?
?- closure(connection,From,To).

First, let's run the queries the OP gave:

?- closure(connection,a,d).
  true                                % OK: succeeds non-deterministically
; false.                      

?- closure(connection,b,a).
  true                                % OK: succeeds non-deterministically
; false.

?- closure(connection,f,b).
  true                                % OK: succeeds non-deterministically
; false.

?- closure(connection,a,g).
false.                                % OK: finitely fails

Let's ask the most general query!

?- closure(connection,X,Y).
  X = a, Y = c
; X = a, Y = d
; X = a, Y = e
; X = a, Y = f
; X = a, Y = b
; X = b, Y = d
; X = b, Y = e
; X = b, Y = f
; X = b, Y = c
; X = b, Y = a
; X = c, Y = d
; X = c, Y = e
; X = c, Y = f
; X = c, Y = b
; X = d, Y = e
; X = d, Y = f
; X = e, Y = f
; X = c, Y = a
; X = d, Y = b
; X = d, Y = c
; X = d, Y = a
; X = e, Y = d
; X = e, Y = b
; X = e, Y = c
; X = e, Y = a
; X = f, Y = e
; X = f, Y = d
; X = f, Y = b
; X = f, Y = c
; X = f, Y = a
false.

Prolog definition which detects a path

1 Answers1