Vfrdtyky

Modelling the stops of an underground tube line like so:

stop(line1, 1, station1).

stop(line1, 2, station2).

stop(line1, 3, station3).

stop(line1, 4, station4).

stop(line1, 5, station5).

stop(line2, 1, station2).

stop(line2, 2, station4).

where stop(L, N, S) means S is the N'th stop on line L, I'm trying to define path(S1, S2, P) that calculates possible paths between S1 and S2.

Here a path is a list of "segments", a segment being a journey along the same line, i.e. segment(L,S1,S2) represents the continuous journey from S1 to S2 along line L. So a possible solution to path(a,d,P) is P=[segment(line1, a, b), segment(line2, b, d)], i.e. go from a to b on line1, then go from b to d on line2.

An additional constraint is that a path should not include the same line more than once.

I've got the following:

segment(L, S1, S2) :- stop(L, N1, S1), stop(L, N2, S2), N2>N1.

line_present_in_path(_, ) :- false.

line_present_in_path(L, [H|_]) :- segment(L, _, _) = H.

line_present_in_path(L, [_|T]) :- line_present_in_path(L, T).

path(S1, S2, [H]) :- segment(_, S1, S2) = H, H.

path(S1, S2, [H|T]) :- segment(L, S1, X) = H, H, +line_present_in_path(L, T), path(X, S2, T).

but something peculiar happens. If I explicitly specify all the parameters myself, it recognises it as a correct path:

?- path(station1, station4, [segment(line1, station1, station2),segment(line2, station2, station4)]).

true ;

false.

However, if I ask it to calculate all paths, it only finds one path, different to the path it just verified as correct:

?- path(station1, station4, P).

P = [segment(line1, station1, station4)] ;

false.

I must admit I'm new to Prolog so I might be missing something basic. But, I really can't understand why it can verify a given path as correct, but it doesn't find that path when trying to find all paths.

The bug is in the second clause for the path/3 predicate. Rewriting it for clarity:

path(S1, S2, [segment(L, S1, X)|T]) :-

    + line_present_in_path(L, T),

    path(X, S2, T).

With a goal such as path(station1, station4, P), you call the line_present_in_path/2 predicate with a variable in the second argument. That call always succeeds and thus its negation always fails. In general, you should be cautious of only using +/1 with a sufficiently instantiated argument.

Hint: to solve the bug, use an additional argument to the path predicate to hold the stations found so far. E.g.

path(S1, S2, Path) :-

    path(S1, S2, Path, ).



path(S1, S2, Path, Visited) :-

    ...

You can use the de facto standard member/2 predicate to check if a station is already in the path and add it to the visited list otherwise. Path finding is a common question and you will find several related answers here in StackOverflow. But try first to solve it on your own.