CODEWITHSUNDEEP
prolog
zer0kai
zer0kai

Reputation: 259

Prolog routes in directed graph

I am quite new to Prolog and want to create a program, where I can ask for a route with the predicate "route(Startpoint,Endpoint,Route)".

My code so far is:

% facts

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

% predicates

route1(X,Y,[X,Y]) :- connection(X,Y).
route1(X,Y,R) :- connection(X,Z), route1(Z,Y,RZ), R=[X|RZ].

route2(X,Y,[X,Y]) :- connection(Y,X).
route2(X,Y,R) :- connection(Z,X), route2(Z,Y,RZ), R=[X|RZ].

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

My code works for some routes, but not when it comes to a cycle (like in the facts above). How can I prevent in Prolog, that a station gets visited in a route multiple times?

For example when I ask "?- route1(s1,s4,R).", Prolog gives me the correct route "[s1,s2,s3,s4]" first, but it also gives me other routes like "[s1, s2, s3, s4, s5, s6, s7, s1, s2, s3, s4]", "[s1, s2, s3, s4, s5, s6, s7, s1, s2, s3, s4, s5, s6, s7, s1, s2, s3, s4]" and so on.

Thanks in advance!

Upvotes: 2

Views: 510

Answers (1)

coder
coder

Reputation: 12972

You could just write:

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

sort/2 removes duplicates so if you want your solution not to have duplicates the sorted list and the output list must have same length.

?- route1(s1,s4,R).
R = [s1, s2, s3, s4] ;
false.

Another ways to do that would be :

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

route1(X,Y,_,[X,Y]) :- connection(X,Y).
route1(X,Y,L,R) :- connection(X,Z),\+member(Z,L),
                   route1(Z,Y,[Z|L],RZ),R=[X|RZ].

Example:

?- route1(s1,s4,R).
R = [s1, s2, s3, s4] ;
false.

Upvotes: 2

Related Questions