That is Prolog contains a complete search algorithm with "back tracking". That is if you are searching for a set of values X, Y and Z to make a clause true Prolog with try a value for X and Y and then try all values of Z. If it finds a value of Z that makes the clause true then the search stops. If it doesn't it backtracks and changes the value of Y and starts the search on Z again. This continues until all values of Y have been tried when it backtracks again to X and tries the whole search over with a new value of X. This is why Prolog is so good a finding values that satisfy a set of conditions - it comes with a built in sophisticated search.  

If you ignore the data clauses that define how the stations are connected you have to admit that this is powerful stuff coming from just two Prolog instructions:

connect(X,Y):-adjacent(X,Z,_,_), connect(Z,Y).
connect(X,Y):-adjacent(X,Y,_,_).

In practice all we need are some extra statements to keep track of the list of stations on the route but the rest is more or less fine detail and mechanics.

But this simple demonstration shows the power of Prolog - it allows you to turn statements that concern the relationships between the data in the database into programs which access the data. In fact there is almost no distinction between the statement of a relationship and its use.

For example, it is obvious that if adjacent(X,Y) then it is also the case that adjacent(Y,X) so why bother entering both into the database. In Prolog you can state is obvious symmetry as

next(X,Y):-adjacent(X,Y,_,_).
next(X,Y):-adjacent(Y,X,_,_).

which can be read as saying that stations X and Y are next to each other if X is adjacent to Y or Y is adjacent to X. If you include this statement in a Prolog program then that is almost all you have to do. From then on questions about X being next to Y will be answered correctly even if you have only entered one of the two pieces of information about adjacency.

You can carry on adding rules that define how the data should be interpreted until you can answer very complex queries. 

The Full Tube

The next example is a complete Prolog program that  will not only tell you whether one station is connected to another, but will give you the route and tell you if and where you have to change.

It can only handle one change of line and it doesn't attempt to find the best route in terms of time but it would be very easy to extend the program to include these features.

Of course this is more complicated than the simple example given earlier but not that much more complicated and given what it does it's remarkably simple.

What we need is a clause like route(X,Y,F) where X and Y are the two stations and F is the route between them to be found.  The database for the task consists of the list of adjacent clauses as given earlier that define the part of the underground system that the program works with. As you can see this is fairly limited but if you have a map of the underground you can extend it as you much as you like. Notice that the time between stations isn't actually used in this program, but it is included so that the program can be extended to include time considerations without invalidating the database.

adjacent(edgware_road,paddington,district,1).
adjacent(paddington,bayswater,district,1).
adjacent(bayswater,nottinghill_gate,district,1).
adjacent(paddington,warwick_avenue,bakerloo,1).
adjacent(warwick_avenue,maida_vale,bakerloo,1).

You can add extra stations to make the database more interesting.

We need the same sort of clauses that define the basic properties of the database that were described earlier.

The next(X,Y,L) clause supplies the symmetry condition that if X is adjacent to Y on line L then Y is also adjacent to X on line L.

next(X,Y,L):-adjacent(X,Y,L,_).
next(X,Y,L):-adjacent(Y,X,L,_).

Most of the work of the program is performed by two clauses - direct_connect and one_change.

The first defines the conditions for a route between two stations X and Y to be all on one tube line.

direct_connect(X,Y,L,S,F):-
    next(X,Z,L),not(member(Z,S)),
       direct_connect(Z,Y,L,[Z|S],F).

The extra variables S and F are used to keep track of the route. S is the route so far and F is the final route between the two stations.

The direct_connect clause is more or less as described in the main text apart from the addition of the condition that the a station will only be added to the route if it isn't already part of the route. (This is the purpose of the not(member(Z,S)) part of the clause.) If you think about it you should be able to see that this stops a circular route building up!

This clause also has some list processing statements. If you look at the final part you can see [Z|S] is the instruction which builds the list of stations - it adds Z to the front of the list of the route found so far.

We also need a clause that deals with the case that two stations are next to each other and there is no intermediate station Z

direct_connect(X,Y,L,S,[Y|S]):- next(X,Y,L).

The one_change clause defines the condition for a route between two stations to involve one change of lines. If you think about it this can be built up out of two direct connection routes with an intermediate station:

one_change(X,Y,L,F):-
        direct_connect(X,Z,L,[X],F1), 
        direct_connect(Z,Y,L2,[Z|F1],F),L\=L2.

Essentially all this says is that if there is a one_change route between X and Y then there is a direct_connect route from X to Z on line L and a direct_connect route from Z to Y on line L2. You may be a little confused by the details of this definition but it helps to notice that  Z is the interchange station! The final condition makes sure that lines at the change are different.

The rest of the program deals with the fine detail. For example, the clause exist is the condition for a station to exist i.e. it must be mentioned in at least one 'adjacent' clause.

exist(X):-next(X,_,_).

This guards against spelling mistakes etc.

We also need the member clause used in the direct_connect clause to avoid putting stations in to form a loop:

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

This simply says that X is a member of the list if it is the first item or if it is the member of the list with the first item removed.

Now  we have all of the clauses needed to create the route clause that is used to find either a direct or one change route.

First it checks that the two stations exist in the data base. If there is a direct_connect route then it prints a message to that effect and then prints the route.

route(X,Y,F):-exist(X),exist(Y), 
       direct_connect(X,Y,_,[X],F),
       write('Direct Connection'),nl,
       revwrite(F).

On the other hand if there is a one_change route then it prints a message to that effect.

route(X,Y,F):-exist(X),exist(Y), 
              one_change(X,Y,_,F),
              write('One change required'),nl,
              revwrite(F).

In this case the interchange station is the one that is listed twice in the route list.

The revwrite clause simply write the list in reverse order:

revwrite([X]):-write(X).
revwrite([H|T]):-revwrite(T), write('->'),write(H).

Now we can try the whole collection of clauses out.