C++ Homework for week 8. 



The goal of this assignment is to implement the FWI (section 8.3.1 in our text describes this algorithm in detail) all-pair shortest path algorithm on a graph representing the London Underground. This program will be developed over the next three weeks, that is weeks 8, 9 , and 10 to be demonstrated in weeks 9, 10, and 11.  

Data files are attached. They are text files for the London Underground and Montreal Metro. Java source code for parsing the text files, and a map of the London Underground 
 
 
• The file LondonUnderground describes the London Underground in a simple text format. First, all station names are listed, one per line. Then, all edges are listed, again one per line. The edge list is separated from the station list by an empty line. The precise format of the file is given below. The file GraphInput.java will help you write code to read in the contents of the above file and build an internal representation of the graph that the FWI algorithm will operate on.  
 
• Your task is to do the following: 
1. Week 8: Write code that reads the contents of a file specified by the user, builds an internal representation of the graph specified in the file, and computes the lengths of the shortest paths between any pair of vertices using the FWI algorithm. This means you have to write code to do the following: 
a. Read in a string from the user representing the name of a file containing the graph data. 
b. Open the file and read in the list of station names as strings and build the vertices of the graph. 
c. Read in the list of triples (name1, name2, line) as strings and build the edges of the graph. To help you with the parsing of each triple, the file GraphInput.java contains methods that will break up a string for the form "(name1, name2, line)" into its components. This java program writtem by Margaret Lamb, should be translated to C++. The third component of an edge is a string describing which line the edge is on. Note that you will not need this line information for this assignment.  
d. Once the internal representation of the graph is constructed, apply the FWI algorithm to compute a table that contains the length of the shortest paths between every pair of stations in the system. You can assume that the length of each edge is one. The shortest path between two stations is thus is given by the path that connects the two stations using the smallest number of edges. 
2. Week 9: After the computation of the shortest distances between all pairs of stations, your program should repeatedly prompt the user for pairs of station names until the user input indicates that no more shortest distances are required. After two station names have been input, your program should use the table constructed by the FWI algorithm to look up and output the length of the shortest path between the two stations. It should also retrieve a path that realizes this shortest path and print it out as well. For example, Given the source station Westminster and the destination station Clapham_Common the output could look something like this: 

The distance between Westminster and Clapham_Common is 7
From station Westminster go to station
St_James's_Park followed by
Victoria followed by
Pimlico followed by
Vauxhall followed by
Stockwell followed by
Clapham_North followed by
Clapham_Common 
 
Notice that you don't have to take the LINE travelled on into consideration, nor do you have to report transferring from one LINE to another. 
 
3. Week 10: You have an extra week to get everything done if you haven’t already finished by week 9. Alternately you can use week 10 for the challenge part of this assignment. An annoying short-coming of the current implementation is that transferring from one line to another is not taken into consideration. On the surface there does not seem to be a quick way to remedy this problem. Your challenge is to determine and implement a means to incorporate line transfers into the shortest path calculation. A reasonable weighting for a line transfer is a cost of k, that is, the time it takes to change lines is equivalent to the time it takes to travel from k stations. In my experience the value of k should be somewhere around 2 or 3.  
 
• Assumptions, remarks, and hints 
• The graph description file lists all stations using one line per station. Then all edges are listed using one line per edge. The list of edges is separated from the list of stations by an empty line. More precisely, the format of the file is as follows:
• s1
• s2
• .
• .
• .
• sn
•
• (s11, s12, l1)
• (s21, s22, l2)
• .
• .
• .
• (sm1, sm2, lm)
•  
• where the si and sij are station names and the li are the names of the lines that the edge is on. If the specified file is not in this format, your code should notify the user. 
• Note that the file describing the London Underground contains symmetric edges, that is, for every edge (s1, s2, l) in LondonUnderground, there also is an edge (s2, s1, l) in the file. This models the assumption that subway trains can always be used in both directions. 
• For this assignment, the length of a path will simply be the number of edges on the path, that is, the weight of every edge will be 1. 
• While you may want to test your code on simpler graphs initially, your final test runs should use the London Underground graph. 
• The data for the Underground was obtained from the map by Michelle Crane, a PhD student. The MontrealMetro file follows the same format as the LondonUnderground. It's a smaller system so it might be a good place to start when debugging your program. 
• For the FWI algorithm an adjacency matrix of the graph is appropriate. To quickly obtain a path an adjacency list of the graph is better. So use both representations in your program. Use a map on keys that are station names to quickly access the index in the adjacency matrix associated to a station name. Use the C++ map class for this. 

Posted: Fri - March 2, 2007 at 01:39 PM          

©