CODEWITHSUNDEEP
prologgraph-theorytransitive-closure
SealCuadrado
SealCuadrado

Reputation: 769

Prolog definition which detects a path

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

Upvotes: 2

Views: 2795

Answers (1)

repeat
repeat

Reputation: 18726

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

We can obtain the of connection/2 by using 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.

Upvotes: 2

Related Questions