What?? Subways in her form of public transportation to a system that's already working fine? And by the way, has anyone talked to the potential users about this crackpot idea?
Imagine that it's 15 years hence and the ign of a new subway system. The designers would like to try out various placements of subway stations and lines connecting them - without digging up any streets just yet. Your job is to build a computer-based environment in which they can experiment with locations of subway stations and compare the distances between stations along various routes. You'll be able to reuse bits of your old code (e.g. linked lists and dragable objects), play with a new data structure (the graph), and design "friendly" user interfaces for the city planners.
A subway station together with its connecting lines is an example of a data structure called a graph. Unlike the tree (see exercise 34), there is no privileged "root" node, nor are there rules requiring that the nodes be organised in a hierarchy (with "parent"/"child" relationships). Rather a general graph is simply a network of nodes and connecting links. You can use a graph to model ng graph nodes model the subway stations and links model the lines that connect stations. So in BETA you could have separate SubwayNode and SubwayLink patterns as well as a SubwayGraph pattern to model the whole system. Then SubwayGraph has two attributes whose values are lists of all the SubwayNodes and all the SubwayLinks, respectively. You'll also want to be sure that each node "knows" about its connecting links and that each link "knows" about the two nodes at its endpoints. You might consider reusing the old LinkedList pattern to represent lists of nodes and links.
We have to scan a map of enever the user clicks in this window, a new subway station is created with a single character name (starting with A, then B, etc.). A text object is placed in the window at the point of the mouse click displaying that name. If the user subsequently clicks on the name, the station can be dragged to a new location.
Particularly during experimentation with early versions of the system, it might be a good idea to have a menu item which refreshes the window. Another approach would be to implement a first version of this part of the application in a plain window, i.e. with no map on the background.
Designers of subway systems know that certain routes are more heavily used than others. For example, on a Saturday morning there's always lots of traffic between Gellerup and the market at Ingerslevs Boulevard. If there were stations at those two points, then the subway designer might want to highlight the shortest route between them and be sure that it's direct enough. To support such experimentation, you need to implement the calculation and display of the shortest path between two stations chosen by the user. The user would select two nodes which are the start and end nodes respectively. Then, with a single menu selection, the shortest route between those nodes is highlighted in the window. (For example, the links along the route could be redrawn with thicker lines.)
How do you compute the shortest path between two nodes in a graph? Here's a textual description of one possible algorithm: The idea is to let each node in the graph calculate the total distance of the shortest route to it from the start node. Then, starting at the end node, you can work your way back to the start node highlighting each link along the shortest path. So there's two steps.
Step 1: Let's first consider how nodes calculate their shortest distance. It's a recursive, object-oriented algorithm. At any given time during the algorithm, each node has a current shortest distance (initially -1 indicating that no calculations have been performed). The start node can immediately improve its current shortest distance to 0 to indicate that the optimal route between a node and itself has 0 length. Now the start node communicates with each of its neighbours along their connecting links. Each neighbour sees whether it can improve on its current value by using the value sent from the start node together with the distance along the connecting link. If this results is a smaller value for the shortest distance to the neighbour node, then it decreases its current shortest distance and starts the same process up with its neighbours. On the other hand, if this does not result in an improved shortest distance, then the neighbour does nothing and does not "pass the baton" along to its neighbours. (Despite the fact that nodes can be visited more than once, you should convince yourself that this recursive algorithm does in fact stop eventually, no matter how complex the graph is.)
Notes:
Step 2: Now that each node knows the shortest distance from it to the start node and each also knows which incoming link is first along that shortest path (to the start node), it's a simple matter to highlight the shortest path. Just starting at the end node, find the preferred link and highlight it. Then, "pass the baton" (recursively) to the node at the other end of the preferred link. If there is no preferred link, then stop. You should now be at the start node (which will never have a preferred link).
(Note that both of these algorithms are object-oriented and recursive. They are object-oriented because the work is done in procedure attributes that belong locally to each node with the node "handing off" control (i.e. message passing) to the neighbour nodes. They are recursive because these procedures call themselves.)
| Teaching Package | © 1991-2004 Mjølner Informatics |
[Modified: Friday October 20th 2000 at 13:18]
|