CSE 373 Data Structures 09wi, Homework 6 & 7

Electronic Turn-in due: 11:59pm Thursday, March 12, 2009.

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 Sean by 11:59pm Friday March 6^th.

Part I. Graph Representations (recommended due date Friday 3/6/09)

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

The assignment has these files provided:

• Graph.java - Graph interface.
• Vertex.java - Vertex class.
• Edge.java - Edge class.
• MyGraph.java - Implementation of Graph interface, you will need to fill in code here.

You are to add code to MyGraph.java that implements the Graph.java interface. Graph.java makes use of the Vertex.java and Edge.java classes provided, although you should feel free to add things to Vertex.java or Edge.java. Just don’t remove anything that is currently there. You should not modify Graph.java. Your code should be efficient and strive for the minimal big-Oh possible for the requested operations. Although a simple list of vertices and edges is sufficient to store all information about a graph, it may not be the most efficient method for answering questions about the graph (see part II.)

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. You may assume that graphs you are given will not contain negative cost edges.

What to Do

We have provided a driver program to read in input from the user:

• Paths.java – driver program that reads in vertex and edge files, creates a graph and prompts use for vertices to find shortest path between.

The format of the input files are 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 directed edge. The first line gives the starting vertex. The second line gives the ending vertex (the one being pointed to). 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).

You may assume that every node name that appears in a path (edge) also appears in the vertex list. Note that since data files are expected to represent directed graphs, the existence of an edge from a to b does not guarantee the existence of an edge from b to a (unless both edges exist in the data file), nor does it guarantee that the weight of the edge from a to b is the same as the weight of the edge from b to a. You may assume that negative weight edges will not be present in input files you are given.

Two sample data files are available representing information about airports and the cost of a flight between them. File vertex.txt contains a list of 3-letter airport codes, each of which represents a vertex in a directed graph. File edge.txt contains information about the directed edges in the graph.

• When the program begins execution, it reads the two data files and creates a representation of the graph.
  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 loops repeatedly and allows 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 (cheapest) such path, including the vertex names on the path and the total length (cost). 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 (cheapest) paths in the graph.
  
  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 your graph implementation from Part I as a starting point. Feel free to add or extend the given vertex, edge, and MyGraphs classes (but don’t take anything out).

Extra Credit

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

• (2 points) 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.
• (4 points) 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.
• (1 point) 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.
• (3 points) 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:

• ALL of the files that make up your program. This includes Vertex.java as well as Graph.java. You should NOT change Graph.java however. (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 description of the worst case big-O running time of your implementations of:

• adjacentVertices?
• isAdjacent?
• Dijksta?
• Please use variables E and V in your answers and explain how you got the values you did.

• 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. 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.