All routes in directed graph

Question

I want to make a program which should give out all possible routes between two stations. The problem I have is that it doesn't give me all routes. My code so far is:

connection(s1,s2).
connection(s2,s3).
connection(s3,s4).
connection(s4,s5).
connection(s5,s1).
connection(s1,s4).
connection(s2,s5).

direction1(X,Y) :- connection(X,Y).
direction2(X,Y) :- connection(Y,X).

route1(X,Y,R):- route1(X,Y,[X],R).
route1(X,Y,_,[X,Y]) :- direction1(X,Y).
route1(X, Y, Visited, Route) :- direction1(X, Z), Z \= Y, \+ member(Z, Visited), route1(Z, Y, [Z|Visited], Route1), Route = [X|Route1].

route2(X,Y,R):- route2(X,Y,[X],R).
route2(X,Y,_,[X,Y]) :- direction2(X,Y).
route2(X, Y, Visited, Route) :- direction2(X, Z), Z \= Y, \+ member(Z, Visited), route2(Z, Y, [Z|Visited], Route2), Route = [X|Route2].

route(X,Y,R) :- route1(X,Y,R); route2(X,Y,R).

For example when I ask for "?- route(s1,s4,R)" it only gives me R = [s1, s4], R = [s1, s2, s3, s4] and R = [s1, s5, s4]. But there are also the routes (s1,s2,s5,s4) and (s1,s5,s2,s3,s4) and I don't know why I don't get them. How to fix this?

Thanks in advance!

max66 max66 · Accepted Answer · 2016-11-24T21:09:57

Is enough

direction(X,Y) :- connection(X,Y).

direction(X,Y) :- connection(Y,X).

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

route(X,Y,_,[X,Y]) :-
   direction(X,Y).

route(X, Y, Visited, [X | Hr]) :-
  direction(X, Z),
  Z \= Y,
  \+ member(Z, Visited),
  route(Z, Y, [Z | Visited], Hr).

I mean: use only one direction/2 instead the duplication of direction1/2 and direction2/2. The use of the Visited list permit you to avoid the potential loop.

So you can unify route1/3 and route2/3 in a single route/3.

Your code fail finding [s1, s2, s5, s4] because from s1 to s5 you need direction1/2 (so route1/3 and route1/4) but from s5 to s4 you need direction2/2 (but route1/4 doesn't call direction2/2).

In similar way your code fail finding [s1, s5, s2, s3, s4] because you need direction2/2 (so route2/3 and route2/4) from s1 to s2 but you need direction1/2 from s2 to s4.

All routes in directed graph

1 Answers