TEACH ROUTE David Young, November 1986 Updated Aaron Sloman December 1994 This is an introduction to two libraries, LIB ROUTE and LIB ROUTETREE. LIB ROUTE demonstrates Branch and Bound search, applied to finding optimum routes on the London Underground. LIB ROUTETREE enables you to display a route graphically using VED. This file does not seek to explain the search strategy, but simply to enable you to use the libraries. CONTENTS - (Use g to access required sections) -- Using ROUTE -- Finding a route -- The searching information -- Getting rid of search information -- Looking at the search tree -- Displaying the tree using showtree -- What the picture looks like -- Using routetree -- Compare the tree with the Computers and Thought book -- Finding a route with trace information printed, using chatty -- Looking at and adding to the map -- Using the routine in your programs -- Looking at the ROUTE program -- Exercises -- Using ROUTE -------------------------------------------------------- To find a route on a small section of the Underground, you need only load the library, then call the routine ROUTE, passing it the names of the start and destination stations. The library knows about 20 stations with 6 lines connecting them. The section it knows about corresponds exactly to Figure 2 of Chapter 5 of the Computers & Thought book by Mike Sharples et al. To load the library, obey the following instruction: lib route; (you can put the VED cursor on the line and then do ESC d, to obey a one line command). To find out the information the program starts with do database ==> Notice that each item in the database is a list of the form [[ ] connects [ ]] e.g. [[VICTORIA Warren Street] connects [VICTORIA Oxford Circus]] The first item in the [ ] list is a list whose hd (head) is the name of the current line (in upper case) and whose tl (tail) is the name of a station, which may contain one or more words. In station names, each word begins with a capital letter, and full stops and apostrophes are omitted. The only abbreviation is St for Saint. Thus [St Jamess Park] is correct. -- Finding a route ---------------------------------------------------- To find a good route between, say, Victoria and Marble Arch, mark and do the following instructions: ;;; prevent spurious printout false -> chatty; ;;; get a route route([Victoria], [Marble Arch]) ==> This should produce a route, which is a list of lists, something like this: ** [[[VICTORIA Victoria] at 0 mins] [[VICTORIA Green Park] at 2 mins] [[VICTORIA Oxford Circus] at 4 mins] [[CENTRAL Oxford Circus] at 7 mins] [[CENTRAL Bond Street] at 9 mins] [[CENTRAL Marble Arch] at 11 mins]] The procedure ROUTE takes, as you can see, two lists as arguments. The first contains the name of the starting station and the second the name of the desired destination. The result is a list of intermediate points between the start location and the final location, and the time taken to reach that point from the start location. -- The searching information ------------------------------------------ While the route program is working it stores information in the database about the places it has had to explore while searching for a route from the given starting place to the given destination. You can see what has been added to the database by printing it out database ==> The search for the route is represented by the database entries of the form [arrived [] at mins from []] e.g. [arrived [BAKERLOO Charing Cross] at 10 mins from [JUBILEE Charing Cross]] with the initial location represented by two entries (in this case), i.e. [arrived [VICTORIA Victoria] at 0 mins from [start]] [arrived [CIRCLE Victoria] at 0 mins from [start]] as there are two lines going through the start station. The final location is represented like this: [finished at [CENTRAL Marble Arch]] The times are calculated using a very simple (and totally unrealistic) assumption that the time between any two adjacent stations on the same line is 2 minutes, and the time to change from one line to another at any station is exactly 3 minutes. Each database entry of the form [arrived ==] represents a point in the search tree explored by the program while it is seeking a route. -- Getting rid of search information ---------------------------------- If you wish to clear the database of the search information and start again with another query you can use the following procedure. define clear_route(); flush([finished == ]); flush([arrived ==]); enddefine; You can invoke it thus clear_route(); Print out the database after clearing the route to check that it works. database ==> This should merely have the "connects" information. Then find another route, in preparation for the next section; route([Victoria], [Oxford Circus]) ==> -- Looking at the search tree ----------------------------------------- As the program runs, it generates a tree corresponding to the possible routes outward from the start station. After the route has been found, the information corresponding to the seach tree is left in the database. When you then give the command database ==> it prints out a lot of information showing the places explored to find the route. There is a library program that can be used to display the information graphically in VED. You can load it by giving the command: lib routetree This makes available a procedure getroutetree that can search the database for the trail of stations explored by the route procedure the last time it ran, and build a tree structured list, showing the search tree, with station names and line names abbreviated to three characters. Try it out getroutetree() ==> This might print out something like ** [Victoria [VIC 0 [Pim 2 [Vau 4]] [Gre 2 [* Oxf 4]]] [CIR 0 [Slo 2 [Sou 4]] [St 2 [Wes 4]]]] This shows the stations on the Victoria line and the Circle line that were explored before it found the destination station, Oxford street, marked with an asterisk, with an estimated journey time of 4 minutes. -- Displaying the tree using showtree --------------------------------- You can print this out using showtree, thus: ;;; get the search tree out of the database and save it. vars search_tree = getroutetree(); ;;; display it showtree(search_tree); The names were truncated to three characters to make it easier to show the tree graphically. Notice now this display shows that on each of the two lines (VIC and CIR) you can go in two directions from Victoria. So there are four paths from Victoria that the route-finding program had to explore. -- What the picture looks like ---------------------------------------- Each node will correspond either to arriving at a station from another on the same line, or to joining a new line at a station, and also shows the time taken from the initial location. Station names are shown as 3-letter abbreviations using lower case for the second and third; line names are shown as 3-letter abbreviations using upper case. The first sort of node just shows the station name; to find the line go up the tree till you come to line name. Likewise the second sort of node just shows the new line name; to find the station look at the next node up in the tree. The start station is of course at the top; the destination station will appear somewhere near the bottom, marked with an asterisk. -- Using routetree ---------------------------------------------------- The procedure routetree makes it easier to examine much larger trees, which are typically too large to be displayed in a VED window. Try the following. ;;; clear the current route clear_route(); ;;; search again for a route from Victoria to Marble Arch route([Victoria], [Marble Arch]) ==> ;;; get the search tree out of the database and save it. vars search_tree = getroutetree(); ;;; print it out search_tree ==> ;;; Use showtree to display it graphically showtree(search_tree); You can move round that large VED file using the arrow keys or using the WORDLEFT and WORDRIGHT keys (usually the "0" key and the "." key on the right hand keypad, except on a Sun4 where they are the R14 and R15 keys: see your keyboard map for details.) Alternatively you can use routetree, as follows. Routetree is a slightly more convenient program to explore a big tree like the last one produced. Before giving the instruction to draw the tree using routetree, you need to know how to manipulate the display to navigate a big tree. When the tree display appears, you can move the VED cursor around to explore it using the normal cursor movement keys. These are often on the numeric keypad, eg 2 for up, 6 for right and so on. If you are not using a terminal set up this way then use whichever keys move the VED cursor. As a last resort you should be able to do Up Ctrl-P, Down Ctrl-N, Left Ctrl-B, Right Ctrl-F. (unless you use vedoldkeys()). You should soon find out which directions are useful for moving the cursor to different positions in the tree. To finish inspecting the tree, you must press the ENDFILE key. On many keyboards this is the key marked "End" in the middle keypad. On some you have to press ESC then the SCREENDOWN key, or possibly ESC then ">". If you can't get it to stop, you can always interrupt with CTRL C. For more details refer to HELP * SEETREE. Now you are in a position to look at a tree. First load the necessary library if you have not already done so uses routetree; Now, assuming that you have already used ROUTE to find a route, give the instruction routetree(); This will draw the tree and leave you ready to move around it, using the cursor move keys. End with the ENDFILE key or key sequence. -- Compare the tree with the Computers and Thought book --------------- If you make the tree for the route from Victoria to Marble Arch, you will get Figure 3 from Chapter 5 of the Computers & Thought book. Note, however, that it is drawn rather differently: in the book lower levels in the figure show later times. On your screen, the levels just correspond to the number of nodes passed through in the tree, though the times are shown at each node. This is just a matter of draughting; in actually doing the search the ROUTE program correctly took into account the time to get to each node. -- Finding a route with trace information printed, using chatty ------- You can get the route procedure to print out information about how it is searching for a route, by doing true -> chatty; Test it thus: clear_route(); true -> chatty; route([Victoria], [Marble Arch]) ==> This prints out the progress of the search. You may prefer it to keep quiet, especially if you are using it as part of a tourist guide. You can do this with the following command: false -> chatty; If you do true -> verychatty; then the effect will be to print out not only the stations arrived at, but also the future consequences of each arrival. Try this on a short route. clear_route(); true -> verychatty; route([Victoria], [Green Park]) ==> You will find that the search pattern is printed out as the search proceeds: every time the search reaches a new station or joins a new line, notification is printed. Note that this also shows the program tracing its way backwards before it realises it has done so. Try some other routes, preferably with the map from the book in front of you. (If you do not have the map you can reconstruct it from the library file - see below.) Note that sometimes the route returned will not be the best one in the REAL underground - for instance to go from Embankment to Warren Street in real life you would probably take the Northern Line, but as the library happens not to know about that line it will route you up the Bakerloo line. After each route has been found you can, if you wish use getroutetree() to dig the search tree out of the database, and display it using either showtree(getroutetree()); or routetree(); Though remember that the latter goes into a special mode in which cursor move keys become tree navigation keys. -- Looking at and adding to the map ----------------------------------- The database in the library can easily be extended to know about more lines and stations. It is possible to expand the map, which is held in the database. To see what the program knows about already, do database ==> after loading the library. If you have already found a route, there will also be information in the database about that route. The map itself is represented by the lines which include the word "connects". You can clear the route information while leaving the map information with the command clear_route(); defined above. You can add new information using ADD. This is how to start off the Northern Line going north from Embankment. The format should be clear from the example. add([[NORTHERN Embankment] connects [NORTHERN Charing Cross]]); add([[NORTHERN Charing Cross] connects [NORTHERN Leicester Square]]); Of course if you did this you would probably also want to connect Leicester Square to Piccadilly Circus on the Piccadilly Line. Each statement must refer to two stations directly connected together - ie with no intervening stations. For this program to work properly, you MUSTN'T connect stations UNLESS they are adjacent on a line. You do not need to mention the two possible directions of travel separately. -- Using the routine in your programs --------------------------------- You may wish to incorporate the ROUTE program into your own tourist guide to London. To do that, you will have to write a procedure that finds out from the user the start and destination stations, and then calls ROUTE. It could then just print out the list that ROUTE returns, but it may be clearer to the user if it modified the list first, perhaps only saying where to join and where to leave each line. Be warned: printing the information really clearly takes quite a lot of thought. What happens if the user mistypes the station name, or mentions one the program doesn't know about? ROUTE checks for this, and will print an error message and return the value FALSE instead of a list if it can't find a station. If you want your own routine to catch this and take appropriate action you can use CHECKSTAT to do so: try checkstat([St Jamess Park])=> checkstat([Nightsbridge])=> -- Looking at the ROUTE program --------------------------------------- ROUTE is written in the reduced language TPOP (with a minor exception or two mentioned in the comments). It is a fairly long program and you will not want to plough all the way through it, but you may find it helpful to look at some sections and try to understand what they are doing. The appendix to Chapter 5 of the Computers & Thought book is a description of this program. To look at the code, do showlib route -- Exercises ---------------------------------------------------------- 1. Write a program that asks the user for their start and destination stations and prints out the route they should take and an estimate of the time taken. This could either stand alone as a specialist program or could be part of a more general tourist guide with broader knowledge. 2. At the start of the ROUTE library, the following lines appear: vars travtime changetime; 2 -> travtime; 3 -> changetime; These variables are of course the time to travel between stations and the time to change lines. Try assigning different values to them and rerunning the program on some carefully selected routes to see the effect. You might, for instance, make CHANGETIME equal to 0: then the program will find the shortest route if all the stations are the same distance apart. A possible exercise would be to extend the program so as to allow different times to be associated with each link in the map, and different line changing times. Using this information would require a change to the code. 3. (Harder) Understanding search strategies: set both TRAVTIME and CHANGETIME to 1. Look at the search trees. Explain why the search that the program now carries out is called 'Breadth-First' search. 4. (Much harder - only for those with a good working knowledge of programming and plenty of time) Look at the code in LIB ROUTE. It keeps all the pending arrivals in the database, in the order in which they were generated. To find the next event it searches through all of them. It would be more efficient to keep them in a list in time order, with the earliest at the start. Then the next event would always be the head of the list. When future events were generated they would need to be inserted into the list at the appropriate place. Modify the program to do this. --- $poplocal/local/teach/route --- Copyright University of Sussex 1994. All rights reserved. ----------