Database The Prolog Way
Written by Mike James   
Wednesday, 10 December 2014
Article Index
Database The Prolog Way
Compiling Prolog
A complete Prolog program

 

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.

The complete program is:

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

next(X,Y,L):-adjacent(X,Y,L,_).
next(X,Y,L):-adjacent(Y,X,L,_).
direct_connect(X,Y,L,S,F):-
                next(X,Z,L),
                not(member(Z,S)),
                direct_connect(Z,Y,L,[Z|S],F).
direct_connect(X,Y,L,S,[Y|S]):- next(X,Y,L).
one_change(X,Y,L,F):-
                direct_connect(X,Z,L,[X],F1),
                direct_connect(Z,Y,L2,[Z|F1],F),
                L\=L2.
exist(X):-next(X,_,_).
member(X,[X|_]).
member(X,[_|T]):-member(X,T).
route(X,Y,F):-exist(X),exist(Y),
              direct_connect(X,Y,_,[X],F),
              write('Direct Connection'),nl,
              revwrite(F).
route(X,Y,F):-exist(X),exist(Y),
              one_change(X,Y,_,F),
              write('One change required'),nl,  
              revwrite(F).
revwrite([X]):-write(X).
revwrite([H|T]):-revwrite(T), write('->'),write(H).

 

 

If you are using the downloaded version enter all of the clauses into the editor and compile the program.

 

edit

 

If you are using the online version enter all of the clauses into the lefthand panel.   

Switch to the command line and enter:

route(nottinghill_gate,maida_vale,F).

Which produces the output (make sure you have table results ticked in the online version):

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

Note the double occurrence of paddington is due to this being the change of line. 

I  admit that there is a bug that can cause time wasting inefficient journeys but you can fix it in no time at all.

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.

 

mapicon

 

More Information

SWI Prolog

Related Articles

The Triumph Of Deep Learning

Robot cars - provably uncrashable?

<ASIN:0201403757>

<ASIN:0262514451>

<ASIN:0136070477>

<ASIN:0136070477>

<ASIN:193435659X>



Last Updated ( Wednesday, 10 December 2014 )
 
 

   
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.