Computer Science 211
Data Structures

You may work in groups of two or three on this assignment. Groups must be formed by Tuesday, December 8, 2009.

The datasets we will work with come from the Clinched Highway Mapping (CHM) Project (http://cmap.m-plex.com/), managed by Timothy Reichard. This site allows travelers to keep track of a plot the highways they have traveled. It started with the U.S. Interstate highway system, but has since been expanded to encompass the entire U.S. Highway system, several state highway systems, and some highway systems in Canada and Europe.

The CHM data consists of a set of points and latitute/longitude coordinates for each highway. We will use a pre-processed form of this data. For each highway system we will work with, the data has been combined into a single file that will allow much easier construction of a graph representation of that system. The first line of this file contains two integer values: the number of places represented in the file (often intersections, sometimes "shaping points" used to make the routing more accurate), and the number of connections between those places (roads). In your graph representation, these will be the numbers of vertices and edges, respectively. The next section of the file specifies the places (vertices), one line per line. Each line contains a string for the place name, and two doubles for the latitude and longitude, in degrees, of the point. The last section describes the connections, again one per line. Here, each line has two place sequence numbers (according to the order each was listed in the place/vertex listing), followed by a string which describes the road (usually a route number) connecting these places.

Two data sets are provided initially. One is relatively small: it is the Provincial Highway system for the Yukon Territory (canyt.gra). The second is much larger: the State Highway system for New York (usany.gra). Additional systems will be processed and made available soon.

Your tasks are to read the data for a highway system and to be able to do some operations on that data: list the places, list the connections/roads, and compute the shortest path between a pair of places. For the list of places and the shortest path, your program should be able to print the information to the screen or write it to a file suitable for plotting with Google Maps.

To get you started, a class to manage latitude/longitude pairs (LatLng) is provided in its entirety. Also provided is a skeleton of the main driver class (Mapping) that takes care of prompting for commands. The bulk of your work will be to fill in the missing methods in that class. This will include the construction of your graph representation and the computation of shortest paths.

The files to be plotted on maps should contain a list of points, one per line, containing the label and coordinates:

@YT1:BC/YT@YT1:BC/YT (59.999726,-132.11699)
@YT1:+X01 (60.006453,-132.125874)
...

Details about how to display your plottable output files in my Google Maps application will be made available soon.

Here are some things to keep in mind as you design and implement your solution.

• Think carefully about how to construct the graph. Is a matrix-based or list-based implementation more appropriate? Directed or undirected edges? What information needs to be stored with a vertex and with an edge? Keep in mind that vertex labels must be immutable.
• You will need to determine the lengths of the road segments. The provided LatLng class includes a method to do this.
• You should use a variant of Dijkstra's Algorithm to compute shortest paths. We will discuss the algorithm in fairly abstract terms in class, and an implementation for a similar data set is provided as one of our textbook's examples. Neither of these is exactly what you need, but you should use the textbook's code as a model. Keep in mind that your graph structure will likely have different types of labels and that you can stop processing when you find the shortest path to the requested destination rather than calculating the shortest path to all other places. You will also need to make sure that you can efficiently print/write the computed route in the proper order.
• There are bound to be a lot of clarifications, hints, corrections, etc., as you work through this assignment. These will be announced in class and by email, as appropriate.
• If you're stuck, ask! Hopefully this was your approach all semester, but especially for this one it will be helpful to talk through your intended approach.

When you're finished, please submit by email to jteresco AT mtholyoke.edu, your well-documented source code for all Java classes required to run your program. Indicate clearly in the comment at the top of your program the names of all group members, and which group members made which contributions to the functionality each file. Also be sure to acknowledge the startup code or any example code (like the book's Dijkstra' Algorithm implementation) that you make use of.

This lab assignment is graded out of 30 points. As in all labs, you will be graded on design, documentation, style, and correctness. Be sure to document your program with appropriate comments (use Javadoc!), including your name and a general description at the top of the file, a description of each method with pre and postconditions where appropriate. Also use comments and descriptive variable names to clarify sections of the code which may not be clear to someone trying to understand it.

The program design grade will be based on the design choices you make in your implementation. The program style grade will be based on code formatting and approriate use of Java naming conventions. The program documentation grade is, of course, based on the comments you provide (including Javadoc and pre and postconditions as appropriate). The program correctness grade is based on how well your program meets the functionality requirements. All group members will be assigned the same grade.