×
INTELLIGENT WORK FORUMS
FOR COMPUTER PROFESSIONALS

Contact US

Log In

Come Join Us!

Are you a
Computer / IT professional?
Join Tek-Tips Forums!
  • Talk With Other Members
  • Be Notified Of Responses
    To Your Posts
  • Keyword Search
  • One-Click Access To Your
    Favorite Forums
  • Automated Signatures
    On Your Posts
  • Best Of All, It's Free!

*Tek-Tips's functionality depends on members receiving e-mail. By joining you are opting in to receive e-mail.

Posting Guidelines

Promoting, selling, recruiting, coursework and thesis posting is forbidden.

Students Click Here

Train Route Planner, Infinite Loop

Train Route Planner, Infinite Loop

Train Route Planner, Infinite Loop

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

For example:

CODE

% 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:

CODE

:-[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

RE: Train Route Planner, Infinite Loop

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

RE: Train Route Planner, Infinite Loop

(OP)
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:





CODE


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?

RE: Train Route Planner, Infinite Loop

(OP)
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:

CODE


% 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).

RE: Train Route Planner, Infinite Loop

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

CODE


% 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.

Red Flag This Post

Please let us know here why this post is inappropriate. Reasons such as off-topic, duplicates, flames, illegal, vulgar, or students posting their homework.

Red Flag Submitted

Thank you for helping keep Tek-Tips Forums free from inappropriate posts.
The Tek-Tips staff will check this out and take appropriate action.

Reply To This Thread

Posting in the Tek-Tips forums is a member-only feature.

Click Here to join Tek-Tips and talk with other members! Already a Member? Login


Close Box

Join Tek-Tips® Today!

Join your peers on the Internet's largest technical computer professional community.
It's easy to join and it's free.

Here's Why Members Love Tek-Tips Forums:

Register now while it's still free!

Already a member? Close this window and log in.

Join Us             Close