CODEWITHSUNDEEP
prolog
spikestar
spikestar

Reputation: 173

Prolog displaying a path

I have the following simple graph:

x <---> y <---> z

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

path(Start,End,Path) :-           % path/3: there is a `Path` from `Start` to `End`
    path(Start,End,[Start],Path).

path(End,End,RPath,Path) :-       % internal helper predicate `path/4`
    reverse(RPath,Path).
path(Start,End,Visited,Path) :-
    edge(Start,Next),
    \+ memberchk(Next,Visited),
    path(Next,End,[Next|Visited],Path).

Sample queries:

?- path(x,z,P).
P = [x, y, z] ;                   % works as expected
false.

?- path(z,x,P).                        
false.                            % unexpectedly fails!

What can I do to make above query succeed?

Upvotes: 1

Views: 321

Answers (2)

repeat
repeat

Reputation: 18726

First, we write down the known facts by defining predicate edge/2:

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

Then we use edge/2 in tandem with path/4 like so:

?- path(edge,Path,x,z).              % one direction
  Path = [x,y,z]
; false.

?- path(edge,Path,z,x).              % other direction
  Path = [z,y,x]
; false.

How about the following very general query? What are 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 = z, Path = [x,y,z]
; From = y , To = x, Path = [y,x]
; From = y , To = z, Path = [y,z]
; From = z , To = y, Path = [z,y]
; From = z , To = x, Path = [z,y,x]
; false.

Upvotes: 1

CapelliC
CapelliC

Reputation: 60024

If you want to handle an undirected graph:

path(Start, End, Visited, Path) :-
    ( edge(Start, Next) ; edge(Next, Start) ),
    ...

Upvotes: 1

Related Questions