Page 1 ACO201 – Data Structures and Algorithms
London Tube 1.
The rapid transit system in London is called the Underground or simply “the Tube”. It is made up of a network of 270 stations and 11 Lines that connect these stations. Some of the stations are served by just one line but others are connected to several. Trains run on the lines in both directions. For passengers to plan their route, a unique schematic transport map was developed by Henry Beck in 1931. While not geographically accurate, it provides a clear diagram of the system. The lines are shown as the colored, solid lines. They connect stations which are drawn as a single or connected set of white circles or a little colored notch on the line. A name appears near each station. A white circle represents an interchange station that connects two or more lines. Bond Street is on the Central and Jubilee lines. Connected white circles represent a larger interchange station that connects more lines. Paddington is on the Bakerloo, Hammersmith & City, Circle and District lines. The colored notches show that Lancaster Gate and Marble Arch are only on the Central line. Page 2 2. The Underground as a Graph Clearly, this system can be represented with the Graph ADT. The vertices are the stations, and the edges are the connections between the stations on a given line. Since we can travel in both directions, this is an undirected graph. Also, the graph can have parallel edges (Victoria to St. James’s Park is served by the Circle and District lines) and cycles (Tottenham Court Road, Holborn, Covent Garden, Leister Square is a cycle over multiple lines, or the whole Circle line is a cycle by itself). If we build a graph that represents the network, we can do some useful things such as finding routes from one station to another. For example, to get from Stratford (on the right side of the map) to Westminster (in the center, above the Thames river), I could: • Take the Central line from Stratford to Liverpool Street • Switch to the Circle line at Liverpool Street • Take the Circle line from Liverpool Street to Westminster How could we compute this? We have several algorithms that can find paths from one vertex to another. We start by doing a traversal starting from our origin vertex. We have two such algorithms: Depth First Search (DFS) and Breadth First Search (BFS). DFS would find a route but it may have many more stops that we need to make. BFS seems like a better choice. It will find the path to the destination with the fewest edges. Once we have completed a search, we can use the resulting forest of discovered edges to build our shortest path. Notes: We are not considering the distances between station in this problem so we are measuring our path length simply by the number of stops. Also, our algorithm has not been optimized to prefer staying on one line rather than transferring to another line so we may not get the best practical route. 3. The Current Program The program has already been started for you. The Graph ADT and its dependent classes are provided as well as the basic London Tube application. Here is a sample execution of that app (input in green): London Tube – E. Eckert Where are you starting (done to quit)? Tottenham Court Road Where are you going (done to quit)? Queensway Instructions: Take the Central line from Tottenham Court Road to Oxford Circus Take the Central line from Oxford Circus to Bond Street Take the Central line from Bond Street to Marble Arch Take the Central line from Marble Arch to Lancaster Gate Take the Central line from Lancaster Gate to Queensway Where are you starting (done to quit)? Baker Street Where are you going (done to quit)? Marble Arch Instructions: Take the Bakerloo line from Baker Street to Regent’s Park Take the Bakerloo line from Regent’s Park to Oxford Circus Take the Central line from Oxford Circus to Bond Street Take the Central line from Bond Street to Marble Arch Where are you starting (done to quit)? done Page 3 4. Your Improved Program There are several issues with the current application. The portion of the system represented by the application is severely limited. It currently knows about the Central Line from Tottenham Court Road to Notting Hill Gate and the Bakerloo Line from Oxford Circus to Baker Street. That is only two lines and ten stations. Also, the instructions are rather tedious as they list all of the stops you should skip. Expand the Network: You are to add your name to the main program and add additional stations and lines to the network by completing the following items below. Follow the Capitalization, spacing and punctuation for the stations as they appear on the map. • Expand the Central line to include all the stations from Stratford to Notting Hill Gate • Expand the Bakerloo line from Queen’s Park to Elephant & Castle • Add the complete Circle Line • Feel free to add more stations and lines if you like. Identify Line Changes: Notice that there are line changes buried in the instructions. For example: Take the Bakerloo line from Regent’s Park to Oxford Circus Take the Central line from Oxford Circus to Bond Street A casual rider might miss this important detail. Add a line to the instructions when the line changes: Take the Bakerloo line from Regent’s Park to Oxford Circus Switch to the Central line at Oxford Circus Take the Central line from Oxford Circus to Bond Street Simplify the Instructions: There is really no need to list every station along the route. Instead, the instructions could be summarized for the rider. See the improved instructions below: London Tube – E. Eckert Where are you starting (done to quit)? Tottenham Court Road Where are you going (done to quit)? Queensway Instructions: Take the Central line from Tottenham Court Road to Queensway Where are you starting (done to quit)? Baker Street Where are you going (done to quit)? Marble Arch Instructions: Take the Bakerloo line from Baker Street to Oxford Circus Switch to the Central line at Oxford Circus Take the Central line from Oxford Circus to Marble Arch Where are you starting (done to quit)? Stratford Where are you going (done to quit)? Queen’s Park Instructions: Take the Central line from Stratford to Liverpool Street Switch to the Circle line at Liverpool Street Take the Circle line from Liverpool Street to Paddington Switch to the Bakerloo line at Paddington Take the Bakerloo line from Paddington to Queen’s Park Where are you starting (done to quit)? Done Minor Improvement (Extra Credit): Currently, the user must enter the name of the station exactly as printed on the map (e.g. “St. James’s Park”). Allow stations to be entered without regard to capitalization, spaces or punctuation. “St jamesspark” should also work. Page 4 5. Tiered Grading Your grade depends on how many of the application improvements you choose to complete. • Basic Level (for a maximum grade of 70%): Add your name and expand the network as described above. It is much easier than you think. Read the code and understand what you must do. • Intermediate Level (for a maximum grade of 80%): Identify the Line Changes as described above. • Advanced Level (for a maximum grade of 100%): Simplify the Instructions as described above. It is trickier than you might think. Make sure your solution works for the simplest routes (2 stations, 1 line), longer routes (multiple stations, 1 line) and complex routes (many stations, 2+ lines). • Extra Credit (for an additional 10%): Add the Minor Improvement as described above. This extra credit is only available to those students who reach the Intermediate level or above. 6. Notes • You must start with the source files provided with the assignment. • Turn in only your modified source files: LondonTube.java and london.txt. If you feel the need to change any other source files, clear it with me first! I will not accept any other modified source files without this prior discussion. • Make sure your class is not in a package (that is, it is in the default package). • You will need to download the file london.txt and put it at the Project level within Eclipse. 7. Required Main Class LondonTube, provided 8. Required Input A series of pairs of legal Station names, followed by “done”. 9. Required Output Your console output should look like the examples provided above.
本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！
E-mail: email@example.com 微信:itcsdx