How to handle a path in Prolog graph traversal

Question

I have written in Prolog:

edge(x, y).
edge(y, t).
edge(t, z).
edge(y, z).
edge(x, z).
edge(z, x).

path(Start, End, Path) :-
   path3(Start, End, [Start], Path).

path3(End, End, RPath, Path) :-
   reverse(RPath, Path).
path3(A,B,Path,[B|Path]) :-
   edge(A,B),
   !.
path3(A, B, Done, Path) :-
   edge(A, Next),
   \+ memberchk(Next, Done),
   path3(Next, B, [Next|Done], Path).

Its taking care of cyclic graphs as well, I am getting an irregular output when I try to traverse same node from same node.

eg: path(x,x,P). expected output should be:

P = [x, z, t, y, x]
P = [x, z, y, x]
P = [x, z, x]

However, I am getting output:

p = [x]             ------------> wrong case
P = [x, z, t, y, x]
P = [x, z, y, x]
P = [x, z, x]

How can I get rid of this unwanted case. Thanks

The cut in your program is incorrect. To see this, try path(x,Y,P) where Y is a variable. — false
– false, Commented Dec 3, 2014 at 13:32

Community · Accepted Answer · 2017-05-23 12:06:16Z

We use meta-predicate path/4 together with edge/2:

?- path(edge,Path,x,Last), edge(Last,x).
  Last = z, Path = [x,y,t,z]
; Last = z, Path = [x,y,z]
; Last = z, Path = [x,z]
; false.

Alright! Above three answers are exactly what the OP wished for in the question.

Just for fun let's look at all possible paths based on edge/2!

?- path(edge,Path,From,To).
  From = To       , Path = [To]
; From = x, To = y, Path = [x,y]
; From = x, To = t, Path = [x,y,t]
; From = x, To = z, Path = [x,y,t,z]
; From = x, To = z, Path = [x,y,z]
; From = y, To = t, Path = [y,t]
; From = y, To = z, Path = [y,t,z]
; From = y, To = x, Path = [y,t,z,x]
; From = t, To = z, Path = [t,z]
; From = t, To = x, Path = [t,z,x]
; From = t, To = y, Path = [t,z,x,y]
; From = y, To = z, Path = [y,z]
; From = y, To = x, Path = [y,z,x]
; From = x, To = z, Path = [x,z]
; From = z, To = x, Path = [z,x]
; From = z, To = y, Path = [z,x,y]
; From = z, To = t, Path = [z,x,y,t]
; false.

CapelliC · Accepted Answer · 2014-12-03 10:17:28Z

0

path(Start, End, Path) :-
    edge(Start,First),
    path3(Start, End, [Start,First], Path).

should work

answered Dec 3, 2014 at 10:17

CapelliC

60.1k5 gold badges50 silver badges94 bronze badges

Collectives™ on Stack Overflow

How to handle a path in Prolog graph traversal

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related