Database the Prolog way
Written by Mike James   
Friday, 24 September 2010
Article Index
Database the Prolog way
Compiling Prolog
A complete Prolog program

 

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

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 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. Enter all of the clauses into the editor. Compile the program.

 

edit

 

Switch to the command line and enter:

route(nottinghill_gate,maida_vale,F).

Which produces the output

One change required
nottinghill_gate->bayswater->paddington
  ->paddington->warwick_avenue
                      ->maida_vale

I hope you enjoy using this route finder but if you get lost then my advice is to ask a policeman...

You can see that Prolog, and logic programming in general,require a big change in the way that you think about problems but it is often more effective than the apparently more direct procedural approach - something that is rarely stated but is very true.

If you try to extend the tube program you will almost certainly have many a frustrating hour or two as your brain retrains itself to think in terms of logical assertions, but you will have a lot of fun on the way to a working program.

If you would like to be informed about new articles on I Programmer you can either follow us on Twitter, on Facebook , on Digg or you can subscribe to our weekly newsletter.

<ASIN:0201403757>

<ASIN:0262514451>

<ASIN:0136070477>

<ASIN:0136070477>

<ASIN:193435659X>



Last Updated ( Friday, 24 September 2010 )
 
 

   
RSS feed of all content
I Programmer - full contents
Copyright © 2014 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.