CSE373 Data Structures Sp07, Homework 6 & 7

Electronic Turn-in of code due: 11am Wednesday, 5/30/07 using this link.
Printout of code due: At the beginning of class, Wednesday, 5/30/07
No late assignments will be accepted.

This assignment will be equal to 1.5 assignments in weight, although it will only have one due date. In the assignment, you will develop a graph implementation and then use it to implement at least one graph algorithm. In particular, you will implement (at least) Dijkstra’s algorithm for finding the shortest path.

For this assignment, (if you wish, not required) you may work with one partner for the programming portion of the assignment. If you plan on working pairs: one partner MUST send email containing the names and email addresses of both partners to Anna by 11:59pm Wednesday May 23^rd .

Part I. Graph Representations (recommended due date Wednesday 5/23/07)

In this part of the assignment you will implement a graph representation to be used later in Part II.

The assignment has several files provided:

• Graph.java - Graph interface.
• AbstractGraph.java - Abstract (incomplete) implementation of the Graph interface.
• AdjListGraph.java - Graph implementation using an adjacency list. Fill in the remaining code.
• Edge.java - Edge class. Fill in the opposite method.
• Vertex.java - Vertex class.

Fill in the remaining code for AdjListGraph.java, and Edge.java. Your code should be efficient and must have the minimal big-Oh possible for the given implementation.

Part II. Graph Algorithms

In this part of the assignment, you will use the graph representation you created in Part I 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 undirected edge as a pair of directed 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 Part I as a starting point.

Extra Credit

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

• Improve your implementation of Dijkstra’s by using a priority queue. For this, you could modify your code from previous homework or start from scratch. One modification you will need to make to your priority queue code from the previous homework is for Dijkstra's algorithm, we need to be able to find items in the priority queue and update their priorities. The simplest implementation of this can just do a sequential scan to locate an item, then adjust the priority, and move the item to its proper place in the heap. A more complex implementation would allow items in the priority queue to be accessed in constant time. 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. (Please turn these in as individual files, not zipped together. Your TAs thank you!)
• 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, 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.)

In addition, if you worked with a partner, 1) only one partner needs to submit the code electronically and make a printout. 2) Be sure that both partners’ names are listed in all files. 3) Include in your readme.txt file a description of how you developed and tested your code. If you divided it into pieces, describe that. If you worked on everything together, describe the actual process used – how long you talked about what, how long and in what order you wrote and tested the code. Be sure to describe at least one good thing and one bad thing about the process of working together.