1

I'm trying to write a Prolog program to give me all possible paths between two points in a graph (with cycle).

edge(a,b).
edge(a,c).
edge(a,d).
edge(b,e).
edge(c,e).
edge(c,f).
edge(d,f).
edge(f,g).
edge(g,e).
edge(e,a).

show_path(X,Y,[X,Y]) :- edge(X,Y).
show_path(X,Z,[X|T]) :- edge(X,Y), not(member(Y, T)), show_path(Y,Z,T).

I'm trying to use not(member()) to exclude the cycles and avoid infinite loop but it doesn't yield all possible solutions. How can I alter the program to get the all possible paths between two points in a graph with cycle?

Guy Coder
  • 24,501
  • 8
  • 71
  • 136
Afshin Mehrabani
  • 33,262
  • 29
  • 136
  • 201

2 Answers2

1

You can easily see that not(member(Y, T)) fails when T is not instantiated. For example try:

?- not(member(X,L)).
false.

where you see that it fails. To solve that you need to keep an extra list that will be instantiated in every step beginning with empty list:

show_path(X,Y,R):-show_path(X,Y,[],R).

show_path(X,Y,_,[X,Y]) :- edge(X,Y).
show_path(X,Y,L,[X|R]) :- edge(X,Z),\+member(Z,L),
                          show_path(Z,Y,[Z|L],R).

Example:

?- show_path(a,e,L).
L = [a, b, e] ;
L = [a, b, e, a, c, e] ;
L = [a, b, e, a, c, f, g, e] ;
L = [a, b, e, a, d, f, g, e] ;
L = [a, c, e] ;
L = [a, c, e, a, b, e] ;
L = [a, c, e, a, d, f, g, e] ;
L = [a, c, f, g, e] ;
L = [a, c, f, g, e, a, b, e] ;
L = [a, d, f, g, e] ;
L = [a, d, f, g, e, a, b, e] ;
L = [a, d, f, g, e, a, c, e] ;
false.

You could have the output that @Fatalize suggested also by writing:

show_path(X,Y,[X,Y]) :- edge(X,Y).
show_path(X,Y,R) :- edge(X,Z), show_path(Z,Y,RZ),R=[X|RZ],       
                           sort(R,R1),length(R,N),length(R1,N1),
                           (N>N1->!,fail ;true).

Example:

?- show_path(a,e,L).
L = [a, b, e] ;
L = [a, c, e] ;
L = [a, c, f, g, e] ;
L = [a, d, f, g, e] ;
false.
coder
  • 12,832
  • 5
  • 39
  • 53
1

Your program does not work because not(member(Y, T)) will always be false: at this point, T is not instantiated so it's always possible to find a list which contains Y.

You can fix your program by adding an accumulator:

show_path(X,X,T,P) :- reverse([X|T],P).
show_path(X,Z,T,P) :- edge(X,Y), not(member(X,T)), show_path(Y,Z,[X|T],P).

show_path(X,Y,P) :- show_path(X,Y,[],P).

It's not clear what you mean by avoiding cycles. Here, it will avoid passing twice on the same point, unlike @coder's answer. For example:

?- show_path(a,e,Z).
Z = [a, b, e] ;
Z = [a, c, e] ;
Z = [a, c, f, g, e] ;
Z = [a, d, f, g, e] ;
false.
Fatalize
  • 3,513
  • 15
  • 25
  • Clear solution but doesn't work with this graph: https://gist.github.com/afshinm/27f1c8a6f84821dc0b73db3d5fa04949 – Afshin Mehrabani Nov 25 '16 at 15:00
  • @AfshinMehrabani I just updated my answer in the meantime, make sure you tried on the last version. I cannot check myself because the graph you link is not in the format `edge(X,Y)` and you don't indicate what you expect to get. – Fatalize Nov 25 '16 at 15:01
  • sorry can you please explain why you used `reverse` and `dif`? I can't understand the point of those two.. – Afshin Mehrabani Nov 25 '16 at 15:14
  • 1
    @AfshinMehrabani You are right, we don't need `dif` because the `not(member…)` will already check that. As for `reverse`, we need it because the accumulator will accumulate the path in the reverse order that you want in `P`, thus we reverse it at the end. – Fatalize Nov 25 '16 at 15:23