Prolog graph not finding path

Question

I have a problem of linking small-town NZ via a Prolog program. I have been given a set of data which is the roads, their to and from's and the distance. I thought the first problem would be straight-forward but I have been pulling my hair our for hours on this with no luck, all I have to do is print out a viable path given a route. Why can't the solution below find a correct path?

road('Wellington', 'Palmerston North', '143').
road('Palmerston North', 'Wanganui', '74').
road('Palmerston North', 'Napier', '178').
road('Palmerston North', 'Taupo', '259').
road('Wanganui', 'Taupo', '231').
road('Wanganui', 'New Plymouth', '163').
road('Wanganui', 'Napier', '252').
road('Napier', 'Taupo', '147').
road('Napier', 'Gisborne', '215').
road('New Plymouth', 'Hamilton', '242').
road('New Plymouth', 'Taupo', '289').
road('Taupo', 'Hamilton', '153').
road('Taupo', 'Rotorua', '82').
road('Taupo', 'Gisborne', '334').
road('Gisborne', 'Rotorua', '291').
road('Rotorua', 'Hamilton', '109').
road('Hamilton', 'Auckland', '126').

route(Current, Finish, []) :- route(Current, Finish, [Current]).    
route(Current, Finish, _) :- Current==Finish.    
route(Current, Finish, Visits) :- traverse(Current, Next, Visits), route(Next, Finish, Visits).

traverse(Current, Next, [Next|_]) :- road(Current, Next, _).

Whenever I call: route('Wellington','Napier', X). It fails despite there being a path, Wellington->Palmerston North->Napier. Thanks in advance, I know I'm probably doing something stupid as I am new to Prolog.

coder coder · Accepted Answer · 2016-10-07T05:19:28

I think you have some extra clauses that you don't need:

route(Current, Current, [Current]).    
route(Current, Finish, [Current|T]) :- road(Current, Next, _),
                                       route(Next, Finish, T).

Example:

?- route('Wellington','Napier', X).
X = ['Wellington', 'Palmerston North', 'Wanganui', 'Napier'] ;
X = ['Wellington', 'Palmerston North', 'Napier'] ;
false.

Note that the defined clauses of form road('X','Y'). means that there is a road from 'X' to 'Y' but not the vice versa:

?- route('Palmerston North','Wellington',L).
false.

So the roads you declared are one way only.

If you add foe example the clause:

road('Palmerston North','Wellington', '143').

Then if you query:

?- route('Wellington','Wellington', X).
X = ['Wellington'] ;
X = ['Wellington', 'Palmerston North', 'Wellington'] ;
X = ['Wellington', 'Palmerston North', 'Wellington', 'Palmerston North', 'Wellington'] ;
X = ['Wellington', 'Palmerston North', 'Wellington', 'Palmerston North', 'Wellington', 'Palmerston North', 'Wellington']

and goes on....So it falls into circles. To solve this you could write:

route2(X,Y,L,N):- length(L,N),route(X,Y,L),sort(L,L).

so you give the length of the path (because else it will search for ever due to cycles) and accept only paths with different cities by using sort(L,L).

Prolog graph not finding path

1 Answers