Train Route Planner, Infinite Loop

[FallenBlade]

I have a file containing how stations in the London underground are linked.

For example:

% CIRCLE LINE

connected(high_st_kensington,notting_hill_gate,circle).
connected(notting_hill_gate,bayswater,circle).

% NORTHERN LINE (left branch)

connected(mornington_crescent,euston,northern_l).
connected(euston,warren_st,northern_l).

I have written code to find a route from one station to another, here:

:-[tube].

route(X,Z) :-
connected(X,Z,_),
write('From '),write(X),nl,
write('Arrive at '),write(Z),nl,nl.

route(X,Z) :-
connected(X,Y),
write('From '),write(X),nl,
write('To '),write(Y),nl,nl,
route(Y,Z).

It works fine, apart from if it get's caught in a loop of stations before reaching the destination station.

Is there anyway I can stop the looping?

Thank you.

Tom

 

[joel76]

You can use a list where you store the stations already visited.

 

[FallenBlade]

This is what I have intended to do. But adding a list to my code seems to break it. Just slowly implementing this, I haven't added the code to add stations into the list, just pass the list around:

route(X,Z):- 
        V = [], 
        getroute(X,Z,V). 

getroute(X,Z,V) :- 
        connected(X,Z,L), 
        write('From '),write(X),nl, 
        write('On the '),write(L),write(' line'),nl, 
        write('Arrive at '),write(Z),nl,nl. 

getroute(X,Z,V) :- 
        connected(X,Y,L), 
        write('From '),write(X),nl, 
        write('On the '),write(L),write(' line'),nl, 
        write('To '),write(Y),nl,nl, 
        route(Y,Z,V).

It now just repeats the write message for the first move over and over and then says "no".

Any ideas? Is it how I'm creating the list?

 

[FallenBlade]

I have been playing with the code and I believe this should work, but it fails in exactly the same way as my last post:

% Load in the tube file. 
:-[tube]. 

% route takes a starting location'X' and a destination 'Z'. 
% Creates an empty list 'V' and calls getroute. 
route(X,Z):- 
        V = [], 
        getroute(X,Z,V). 

% getroute takes a starting location'X', destination 'Z' and 
% a list of stations visited. 

% this getroute acts if the X is directly connected to Z 
% and the list is empty. 
getroute(X,Z,[]) :- 
        connected(X,Z,L), 
        V = [X], 
        write('From '),write(X),nl, 
        write('On the '),write(L),write(' line'),nl, 
        write('Arrive at '),write(Z),nl,nl. 

% this getroute acts if X is connected to Z through Y 
% and the list is empty. 
getroute(X,Z,[]) :- 
        connected(X,Y,L), 
        V = [X], 
        write('From '),write(X),nl, 
        write('On the '),write(L),write(' line'),nl, 
        write('To '),write(Y),nl,nl, 
        route(Y,Z,V). 

% this getroute acts if the X is directly connected to Z 
% and the list is not empty. 
getroute(X,Z,[V|T]) :- 
        connected(X,Z,L), 
        notinlist(X,V), 
        V2 = [X|V], 
        write('From '),write(X),nl, 
        write('On the '),write(L),write(' line'),nl, 
        write('Arrive at '),write(Z),nl,nl. 

% this getroute acts if X is connected to Z through Y 
% and the list is not empty. 
getroute(X,Z,[V|T]) :- 
        connected(X,Y,L), 
        notinlist(X,V), 
        V2 = [X|V], 
        write('From '),write(X),nl, 
        write('On the '),write(L),write(' line'),nl, 
        write('To '),write(Y),nl,nl, 
        route(Y,Z,V2). 

% notinlist returns true if X is not in the [H|T] list.	
notinlist(_, []). 
notinlist(X, [H|T]):- 
        X =\= H, 
        notinlist(X, T).

 

[FallenBlade]

I have been working on this all day and developed it to here:

% Load in the tube file. 
:-[tube]. 

% route takes a starting location'X' and a destination 'Z'. 
% Creates an empty list and calls getroute. 
route(X,Z):- 
        getroute(X,Z,[X]). 

% getroute takes a starting location 'X', destination 'Z' and 
% a list of stations visited. 
        
% this getroute acts if the X is directly connected to Z. 
getroute(X,Z,_) :- 
        connected(X,Z,L), 
        write('From '),write(X),nl, 
        write('On the '),write(L),write(' line'),nl, 
        write('Arrive at '),write(Z),nl,nl. 

% this getroute acts if X is connected to Z through Y 
getroute(X,Z,V) :- 
        connected(X,Y,L), 
        nonmember(Y,V), 
        V2 = [Y|V], 
        write('From '),write(X),nl, 
        write('On the '),write(L),write(' line'),nl, 
        write('To '),write(Y),nl,nl, 
        getroute(Y,Z,V2). 

% nonmember returns true if X is not in the [H|T] list.	
nonmember(X,Y) :- 
        member(X,Y), !, fail. 
nonmember(X,Y). 

member(X, [X | _]). 
member(X, [_ | Y]) :- 
        member(X, Y).

But now it seems to get stuck on a station that can go to two places.

It tries to go from Station A to Station B.

Then it tries Station A to Station C.

Then it tries Station A to Station B.

And just loops.