Finding all possible paths in a graph without cycl

问题:

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?

回答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.

回答2:

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.