Homework 10, Due Monday, 4/29 by midnight pm via ICON

Introduction.
The file miles.dat contains basic geographic data on 128 cities in North America. This homework asks you to write a program that reads miles.dat and then efficiently responds to shortest path queries about the data. Specifically, miles.dat contains, for each city, the following pieces of information:

This is old data - from a 1949 Rand McNally mileage guide, so the population numbers are definitely out of date. The highway mileage may also be out of date, but the data serves our purposes quite nicely. Note that the data file specifies for each city, the distances to all cities before it in the file; this is sufficient to get pairwise distance between any pair of cities. Also note that latitudes and longitudes are specified without decimal points or N, S, E, W indicators: for example Youngstown, OH is at longitude 41.09972 N and latitude 80.64972 W and this is specified (approximately) as "[4110,8065]."

Building Graphs. From this data, we can build a variety of graphs depending on the specific application. For this homework, I want you to build a graph whose vertices are the 128 cities and whose edges connect pairs or cities that are at most 400 miles apart. If city x and city y are at most 400 miles apart, then you should associate with the edge between city x and city y the distance between these two cities. Also, each city has a few attributes such as its state, longitude and latitude, and population that you should store in the graph data structure. You should think about how to (slightly) modify the graph data structure discussed in class, to store this additional information.

Computing shortest paths. You program should contain a function, with the following header: 

	def shortestPath(graph, source, dest)
that computes and returns a shortest path from the vertex source to the vertex dest. We will be discussing Dijkstra's shortest path algorithm in class and I will also provide most of the code for this.

Outputing a kml file.
To visualize the shortest paths produced by your computations, you should write a function that takes our graph, a path in this graph, and produces a corresponding kml file that can be viewed in Google Maps or Microsoft LiveSearch Maps. Here is the tutorial I used to learn about kml files: kml Tutorial. Here is a sample kml file that I made using a little bit of the data from miles.dat and here is what you see when you view the kml file on Microsoft's LiveSearch Maps.

Things you should do.
To a larges extent, your program will be judged on the correctness of the following functions:

  1. def shortestPath(graph, source, dest)
    This function was described earlier.

  2. def writeVerticesKML(graph, filename)
    This function takes a graph and a filename and creates a KML file of the given name. The KML file should locate all the vertices of the graph on a map.

  3. def writePathKML(graph, path, filename)
    This function takes a graph, a path in the graph, and a filename and creates a KML file of the given name. The KML file should locate all the vertices of the graph on a map and in addition should also show the specified path.

What to submit.
A python progam called hw10.py along with a corresponding README file.