In this assignment you will be modifying your Dijkstra's algorithm implementation from your previous programming assignment to construct a rudimentary bus/subway trip planner. Some rudimentary data regarding TTC bus, streetcar and subway routes will be made available for you to test your program. A basic text interface system is provided for you.
You will modify your Dijkstra's single-source shortest path algorithm from assignment 3 (or as described in CLRS) to support queries on a much more complicated graph structure. The TTCGraph extends the graph data structures you developed in assignment 3 to store information about when and where busses (or other transit vehicles) transit. Each edge represents a particular route joining two consecutive stops (since many routes may run between two locations, this is a multigraph). We have provided code to parse input files and generate some of the graph structure; you will need to complete the weight function which will give how long a customer needs to wait for the next bus/train/etc. and transit to the next stop. Your modified Dijkstra algorithm will use this dynamic weight function to try to find a shortest route between two given locations in the loaded transit network.
The /u/csc263h/summer/pub/p4/data directory on CDF contains a number of files describing the lists of stops and stop times for several actual TTC routes (routes 1 through 4 represent the subway and SRT routes). These data are parsed from the ../rawdata files, which were downloaded directly from the TTC website. Though some of the data files contain accurate data, many routes contain estimated data and a reduced number of stops to help simplify your testing process.
This assignment is somewhat open-ended: you are free to improve this code in any way you wish. A few marks will be devoted to design improvements or extra features. You will include a short report (in a report.txt file) describing how you implemented the missing TODO portions of code, and any extra features you chose to implement. Your report must not be more than one page (66 lines by 80 columns!). The bulk of the marks will be for completeness and correctness of the TODO portions, with extra marks devoted to any extra features you successfully implement.
For more details, including exact specifications of the
methods that you should implement, see the starter code.
You must complete the portions marked
by comments that start with: "// TODO:",
however, you may also make any other modifications to the code
that you wish!
Be sure to describe any additional features you implement in
your report.
Starter code (here is all the starter code in one big .tar.gz file):
Since we are providing some starter code in the form of a .jar
file, you'll need either to add this file to your classpath (i.e.,
use a command like "javac -cp .:MinPriorityQueue.jar:Graph.jar:AVL.jar *.java"
to compile and give the same option to java to run)
or unpack each .jar using a command like
"jar xf MinPriorityQueue.jar" (run for each .jar file).
The Javadoc documentation files are also available online:
You can use these Javadoc references to lookup details about the classes and each of the methods these classes support. (If you haven't used Javadoc before, it's basically the header comments for each method, which is everything you need to know to use a binary class.)
Submission Instructions