CSE 373 Data Structures 11au, Homework 5

Electronic Turn-in due: 11pm Thursday, Dec 1, 2011.
Part I suggested deadline, Mon Nov 28, 2011
Partner Selection due by 11pm Wed Nov 23, 2011 (at the latest).

This assignment will be weighted slightly more than previous assignments (and you can expect it may take longer to do!). In the assignment, you will develop a graph representation 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 Svet by 11pm Wednesday Nov 23^rd at the very latest – it is strongly recommended that you select a partner much earlier!

Using Java Collections - it is o.k. to use things from the Java collections (or really any part of Java) for any part of this assignment. Take a look at the Java Collections API as you are thinking about your solutions. At the very least you may want to look at the Collection and List Interfaces to see what operations are allowable on them and what classes implement those interfaces.

Part I. Graph Representations (recommended due date Mon Nov 28, 2011)

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. – Do NOT modify this file.
• 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. You are free to add things to Vertex.java, Edge.java, or MyGraph.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 (like those described in part II.)

Graph Representation Notes:

· Unique vertex labels - It is fine to assume that vertices will have unique labels.

· Modifying files - You are free to add things to Vertex.java, Edge.java, or MyGraph.java, just don't remove anything that is currently there. You should not change the interface Graph.java.

· Public and Private Fields - Although in general we try to avoid creating public fields for classes, for this assignment we will allow public fields in the Vertex and Edge classes. If you add more fields to the vertex or edge classes, it will be allowable to make those fields public. Please do not change the settings on the current fields in those classes. Fields in other classes should not be made public.

· Equals and hashcode - For the most part you should be able to ignore the equals() and hashcode() methods that have been included in the Vertex and Edge classes. If you add more fields to the Vertex or Edge classes, it is o.k. to leave the equals method as is unless you need to modify it for your own reasons.

· Creating more data structures - In MyGraph we have set up two simple data members: myEdges and myVertices that are references to Collections. A collection of vertices and edges is really just the simplest way to represent a graph. It has all of the info you need, it just might not be good enough for answering some of the questions you have to answer for this assignment (isAdjacent? adjacentVertices?, shortestpath?) in the most efficient way. Feel free to add more data members and methods to MyGraph, as well as to Vertex and Edge. Also be sure to think about how you can make use of parts of the Java collection classes. For example, it seems likely that you will need a Map of some sort somewhere.

· Printing out Collections - As you are debugging your program you may find it useful to print out your data structures. There are toString methods for Edge and Vertex. Remember that things like ArrayLists and Sets can also be printed out with a single println.

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 will do this by filling in code for the shortestPath method in MyGraph.java. You may assume that graphs you are given will not contain negative cost edges. A description of the shortestPath method from MyGraph.java appears below:

/**
Returns the shortest path from a to b in the graph. Assumes positive edge weights. Uses Dijkstra's algorithm.
@param a the starting vertex
@param b the destination vertex
@param path a list in which the path will be stored, in order, the first being the start vertex and the last being the destination vertex. The list will be empty if no such path exists. NOTE: the list will be cleared of any previous data. path is not expected to contain any data needed by the method when the method is called. It is used to allow us to return multiple values from the function.
@return the length of the shortest path from a to b, -1 if no such path exists.
@throws IllegalArgumentException if a or b does not exist.
**/

public int shortestPath(Vertex a, Vertex b, List<Vertex> path) {

// YOUR CODE HERE

}

Graph Algorithms Notes:

· Representing Infinity - For Dijkstra's, one possibility for representing infinity is to use Integer.MAX_VALUE.

· Using a priority queue is extra credit - you are not required to use a priority queue for this assignment. Feel free to use any structure you would like to keep track of distances, and then search it to find the one with the smallest distance that is also unknown. You are welcome to use a priority queue, but are not required to do so.

· equals and multiple copies of Vertexes - You may want to refer to your old notes on the equals() method from cse 143. Remember that this allows us to do a comparison of values (e.g. do two Vertex objects have the same label) as opposed to just checking if two things refer to the exact same object. This is particularly important in this assignment because we have multiple copies of the same Vertex around. Each edge contains the two Vertices that are its end points. Take a look at Paths.java to see how new Vertex objects are created as the edge.txt and vertex.txt files are read in. If there are 3 edges that start or end at DEN, then there will be (at least) four copies of the Vertex DEN in your program. One for the vertex itself when read in from the text file, and one for each time it appears in an edge. Be sure you are aware of this! Note that == is not .equals().

Other Provided Files

Driver Program: 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.

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 will describe the shortest (cheapest) such path, including the vertex names on the path and the total length (cost). For example, if the user enters vertices SEA DEF, then the output might look like SEA ABC DEF 520 if the shortest path from SEA to DEF runs through vertex ABC and has a total length of 520.

You should modify Paths.java so that if there is no path between the two requested vertices, a descriptive message should be printed.

Input file format: You will need two input files, whose format is as follows:

• Vertices: 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 vertex name that appears in an 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 (although zero weight edges may exist).

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.

What to Do

1) Fill in the method bodies as described in Part I and Part II.

2) Make the slight modification to the provided driver program as requested.

3) Answer the write-up questions below.

**Note: You may use Java collection classes for this assignment.**

Write-up Questions:

Include the following in a file called readme.txt:

1) A description of the worst case big-O running time of your implementations of these methods:

· adjacentVertices

· isAdjacent

· shortestPath

Please use variables E and V in your answers and explain how you got the values you did.

2) A description of how you tested your code. Feel free to refer to included test code.

3) A short description of any extra credit extensions included in your code or data files. Be sure to include a brief summary of how to operate your program, if you have added new features.

4) Partners only: If you worked with a partner, 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. *

What to Turn In

You should turn in the following electronically:

• ALL of the files that make up your program. (Including at least: Graph.java, Vertex.java, Edge.java, MyGraph.java, Paths.java)You should NOT change Graph.java however. (Please turn these in as individual files, not zipped together. Your TAs thank you!)
• Any extra files you used to test your code.
• Your readme.txt file containing your write-up as described above.
• Any additional data or other files you developed to work with your program. (These should be described briefly in the readme.txt file.)
• If you did any extra credit, please put those files in a separate folder/zip file. Include all files needed to run any extra credit options in the zip file.
• If you worked with a partner, 1) only one partner needs to submit the code and writeup electronically. 2) Be sure that both partners’ names are listed in all files. Don’t forget to answer the partner questions in the readme file.

Above and Beyond

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

• (Easy) 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.
• (Harder) Improve your implementation of Dijkstra’s by using a priority queue. For this, you could modify code from the textbook or start from scratch. Note that 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 on average. A simple sequential search of the priority 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 priority queue. There are various ways to do this, including keeping a back-pointer from each vertex to its entry in the priority queue. (Note: If you implement this above and beyond, you are not required to also implement Dijkstra’s without a priority queue. You may submit the priority queue version as your only submission, be sure to mention it in your readme.txt.)
• (Harder) Find the unweighted shortest path. In other words, find the minimum number of edges that must be traversed from the start to the destination, ignoring the weight of each edge.
• (Harder) 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.
• (Harder) Other graph algorithms, check with the instructor first.
• (Harder) Graphical displays: Display the graph as a drawing; allow the user to select endpoints by clicking on the screen; highlight the path visually; etc.

I’m open to others ideas as well, please talk to me if you have other ideas!