CSE373 Data Structures Wi07, Homework 7

Due online Saturday, 3/10/07, at 11 pm.
No late assignments will be accepted.

In this assignment we'll use the graph data structures from homework 6 to read a description of a graph and answer questions about it. In particular, you should use Dijkstra's algorithm to find shortest paths in the graph.

What to Do

Write a program that reads a description of an undirected graph with weighted edges, then answers questions about paths in that graph. More specifically, the program should operate as follows:

• The program should begin execution in a main method in a class named Paths. This program should accept two command line arguments: the name of a text file containing a list of vertices, and the name of a second text file giving the edges between these nodes. The files are specified as follows:
  • Nodes: This file has one line per vertex and each line contains a text string with the vertex name.
  • Edges: This file has three lines per edge. The first two lines give the node names at either end of the edge. The third line is a string of digits that give the distance (or weight) on that edge (this line should be converted to a number to be stored in the graph).
  Two sample data files are available representing information about airports and the distances between them. File vertex.txt contains a list of 3-letter airport codes, each of which represents a vertex in the graph. File edge.txt contains information about edges in the graph. Each edge is described by two lines that each contain an airport code, and a third line giving the distance between them. You may assume that every node name that appears in a path (edge) also appears in the vertex list.
• When the program begins execution, it should read the two data files and build an adjacency list representation of the graph that they represent. The data describes an undirected graph; in the adjacency list representation you should represent each path as a pair of edges, one in each direction between the two vertices.
  Although not required, you may find it useful to provide some way to print or display the graph at this point to ensure that it has been read and stored properly.
• Once the graph has been built, the program should loop repeatedly and allow the user to ask for information about paths in the graph. The user should enter two vertex names. If there is a path from the first to the second vertex, the program should describe the shortest such path, including the vertex names on the path and the total length. If there is no path, a descriptive message should be printed (i.e., if either name is not a vertex in the graph or if there is no path between the given vertices).
  Your program must use Dijkstra's algorithm to compute the shortest paths in the graph.
  You need to decide how the end of input is indicated and have the program quit gracefully when the end of input is reached.
  Examples: If the user enters SEA DEF, then the output might look like SEA ABC DEF 1234 if the shortest path from SEA to DEF runs through node ABC and has a total length of 1234.

You should use the graph implementation from the previous assignment as a starting point. You should also use your binary heap priority queue in your implementation of Dijkstra's algorithm. You may need to make some changes in the previous code, which is fine, but you shouldn't need to start over completely.

Extra Credit

A small amount of extra credit will be awarded for interesting extensions. Here are a few possibilities:

• A "location-aware" priority queue allowing items in the queue to be accessed in constant time. For Dijkstra's algorithm, we need to be able to find items in the priority queue and update their priorities. A simple sequential search of the queue is fine for small graphs, but for large graphs we would like to be able to find items in constant time so the total time needed to update a priority is a constant plus the log n time needed to reestablish the heap property in the queue. There are various ways to do this, including keeping a back-pointer from each vertex to its entry in the queue.
• Additional graph algorithms, in particular, given a vertex in the graph, compute a minimum spanning tree from that vertex and print a list of the edges in the MST in the order in which they are added to the tree.
• More/better/interesting data files. The supplied data files are quite minimal. Data describing more extensive graphs, other kinds of graphs, or graphs with additional information such as coordinates or locations on a map would be great.
• Graphical displays: Display the graph as a drawing; allow the user to select endpoints by clicking on the screen; highlight the path visually; etc.

What to Turn In

You should turn in the following electronically:

• The files that make up your program.
• A file readme.txt that contains the following:
  • A brief summary of how to operate your program, particularly if it has any extra features or unusual commands other than the basic ones described above. You should be sure to describe how to indicate the end of the input data.
  • A short description of any extra credit extensions included in your code or data files.
  • A brief summary of the data structures and algorithms you finally used. In particular, you should give a summary of the major design decisions you have made in creating your graph data structure in the previous assignment and this one, and any major changes that were needed as your design evolved to create the final program. This need not be long, but it should describe major decisions you made and any surprises you encountered that required changes as you developed the code.
• Any additional data or other files you developed to work with your program. (These should be described briefly in the readme.txt file.)