Find all possible paths without revisiting

Question

I need a predicate routing which gives all the cities between start & end. For example:

path(chicago,atlanta).
path(chicago,milwaukee).
path(milwaukee,detroit).
path(milwaukee,newyork).
path(chicago,detroit).
path(detroit, newyork).
path(newyork, boston).
path(atlanta,boston).
path(atlanta, milwaukee).

?- routing(chicago,newyork,X).
X=[chicago,milwaukee,newyork];
X=[chicago,detroit,newyork];
X=[chicago,milwaukee,detroit,newyork];
X=[chicago,atlanta,milwaukee,newyork];
X=[chicago,atlanta,milwaukee,detroit,newyork]

I have tried this, and keep coming back to it.

routing(FromCity,ToCity,[FromCity|ToCity]) :-
  path(FromCity,ToCity).

routing(FromCity,ToCity,[FromCity|Connections]) :- 
  path(FromCity,FromConnection), 
  path(FromConnection,ToConnection),
  path(ToConnection,ToCity),
  routing(ToConnection,ToCity,Connections).

routing(FromCity,ToCity,[]).

but it just keeps giving

X=[chicago,milwaukee,newyork];
X=[chicago,chicago,newyork];
X=[chicago,chicago,chicago,newyork]
...
..

Can some one please point me in the right direction ...

score 4 · Accepted Answer · edited May 23 '17 at 12:23

If you are sure (by definition) that your graph is acyclic, you can simplify your rule, exploiting Prolog depth first search:

routing(FromCity, ToCity, [FromCity, ToCity]) :-
  path(FromCity, ToCity).

routing(FromCity, ToCity, [FromCity|Connections]) :- 
  path(FromCity, ToConnection),
  routing(ToConnection, ToCity, Connections).

This find all availables paths on backtracking:

?- routing(chicago,newyork,X).
X = [chicago, atlanta, milwaukee, newyork] ;
X = [chicago, atlanta, milwaukee, detroit, newyork] ;
X = [chicago, milwaukee, newyork] ;
X = [chicago, milwaukee, detroit, newyork] ;
X = [chicago, detroit, newyork] ;
false.

Note the difference between the first and second pattern of list construction: [FromCity, ToCity] vs [FromCity|Connections]. This because Connections will be a list, while ToCity will be an atom, when the rule will succeed.

If your graph contains cycles, this code will loop. You can refer to another answer for a simple schema that handles this problem.

Hello, I have a similar problem but I would like to use the 'write' function to write out the paths inside the program.So all I would have to call in the function is start and end Is there any way to configure your sample above to make it work? — Fjodor, Oct 07 '14 at 12:56
@Fjodor: you cannot write the path reliably, because of backtracking. Try to write(Connections) after the recursive call — CapelliC, Oct 07 '14 at 13:44

score 1 · Answer 2 · edited May 23 '17 at 10:27

How about proceeding as follows?

First, we pick a better predicate name than path. How about edge?

edge(chicago  , atlanta  ).
edge(chicago  , milwaukee).
edge(milwaukee, detroit  ).
edge(milwaukee, newyork  ).
edge(chicago  , detroit  ).
edge(detroit  , newyork  ).
edge(newyork  , boston   ).
edge(atlanta  , boston   ).
edge(atlanta  , milwaukee).

As defined above, edge/2 is clearly not symmetric, otherwise the following query wouldn't succeed!

?- edge(X, Y), \+ edge(Y, X).
  X = chicago  , Y = atlanta
; X = chicago  , Y = milwaukee
; X = milwaukee, Y = detroit
; X = milwaukee, Y = newyork
; X = chicago  , Y = detroit
; X = detroit  , Y = newyork
; X = newyork  , Y = boston
; X = atlanta  , Y = boston
; X = atlanta  , Y = milwaukee.

Next, we define connected_to/2 as the symmetric closure of edge/2:

connected_to(X, Y) :- edge(X, Y).
connected_to(X, Y) :- edge(Y, X).

Finally, we use meta-predicate path/4 together with connected_to/2:

?- path(connected_to, Path, From, To).
; From = To                   , Path = [To]
; From = chicago, To = atlanta, Path = [chicago,atlanta]
; From = chicago, To = boston , Path = [chicago,atlanta,boston]
; From = chicago, To = newyork, Path = [chicago,atlanta,boston,newyork]
...

So... does the most general query of path/4 (with connected_to/2) terminate universally?

?- path(connected_to, Path, From, To), false.
false.                                 % terminates universally

Last, let's count the total number of different ground paths:

?- setof(P, From^To^(path(connected_to,P,From,To),ground(P)), _Ps),
   length(_Ps, N_Ps).
N_Ps = 244.

score 0 · Answer 3 · answered Dec 03 '15 at 21:38

Here's my solution that works on directed or undirected graphs, with or without cycles.

It also tries to find all paths, without revisiting.

c(1,2).
% ... c(X,Y) means X and Y are connected

d(X,Y):- c(X,Y).
d(X,Y):- c(Y,X).
% Use d instead of c to allow undirected graphs

findPathHelper(_, Begin, [], End):- d(Begin, End).
findPathHelper(Front, Begin, [Next|NMiddle], End):-
    not(member(Begin,Front)),
    d(Begin, Next),
    append([Front,[Begin]], NFront),
    findPathHelper(NFront, Next, NMiddle, End).

findPath(Start, End, Path):-
    findPathHelper([], Start, Middle, End),
    append([[Start],Middle,[End]], Path).

Find all possible paths without revisiting

3 Answers3

Linked