CSE373 Winter 2014: Homework 5 - Graphs and Shortest Paths

For this assignment, you will develop a graph representation and use it to implement Dijkstra's algorithm for finding shortest paths. Unlike previous assignments, you will use some classes in the Java standard libraries, gaining valuable experience reading documentation and understanding provided APIs. Also, part of the grade for your code will depend on you "protecting the graph abstraction" leveraging copy-in-copy-out and immutability as we discussed (or will discuss) in class.

Outline

• Due Dates, Turn-In, and Rules
• Provided Files
• Programming, Part 1
• Programming, Part 2
• Write-Up Questions
• Above and Beyond
• What to Turn In

Due Dates, Turn-In, and Rules

Different for this assignment: You may use anything in the Java standard collections (or anything else in the standard library) for any part of this assignment. Take a look at the Java API as you are thinking about your solutions. At the very least, look at the Collection and List interfaces to see what operations are allowable on them and what classes implement those interfaces.

Partner Selection Due 11:00PM Thursday February 27, 2014

Assignment Due 11:00PM Thursday March 6, 2014

For this assignment, you may work with one partner. If you do so, the two of you will turn in only one assignment and, except in extraordinary situations, receive the same grade (and, if applicable, have the same number of late days applied). Working with a partner is optional; it is fine to complete the assignment by yourself.

If you choose to work with a partner, one of you must complete this web form before the partner-selection due date. If you choose to work alone, do not complete the form. If you make a mistake filling out the form, email the course staff.

If you choose to work with a partner, you may divide the work however you wish, but both partners must understand and be responsible for everything that is submitted. Beyond working with a partner, all the usual collaboration policies apply.

Read What to Turn In before you submit — poor submissions may lose points.

Turn in your assignment here

Provided Files

Download these files into a new directory:

• Graph.java -- Graph interface. Do not modify.
• Vertex.java -- Vertex class
• Edge.java -- Edge class
• MyGraph.java -- Implementation of the Graph interface: you will need to fill in code here
• Path.java -- Class with two fields for returning the result of a shortest-path computation. Do not modify.
• FindPaths.java -- A client of the graph interface: Needs small additions
• vertext.txt and edge.txt -- an example graph in the correct input format

Programming, Part 1

In this part of the assignment, you will implement a graph representation that you will use in Part 2. Add code to the provided-but-incomplete MyGraph class to implement the Graph interface. Do not change the arguments to the constructor of MyGraph and do not add other constructors. Otherwise, you are free to add things to the Vertex, Edge, and MyGraph classes, but please do not remove code already there and do not modify Graph.java. You may also create other classes if you find it helpful.

As always, your code should be correct (implement a graph) and efficient (in particular, good asymptotic complexity for the requested operations), so choose a good graph representation for computing shortest paths in Part 2.

We will also grade your graph representation on how well it protects its abstraction from bad clients. In particular this means:

• The constructor should check that the arguments make sense and throw an appropriate exception otherwise. You can define your own exceptions by making classes like the exception classes we have provided you in previous homeworks. Here is what we mean by make sense:
  • The edges should involve only vertices with labels that are in the vertices of the graph. That is, there should be no edge from or to a vertex labeled A if there is no vertex with label A.
  • Edge weights should not be negative.
  • Do not throw an exception if the collection of vertices has repeats in it: If two vertices in the collection have the same label, just ignore the second one encountered as redundant information.
  • Do throw an exception if the collection of edges has the same directed edge more than once with a different weight. Remember in a directed graph an edge from A to B is not the same as an edge from B to A. Do not throw an exception if an edge appears redundantly with the same weight; just ignore the redundant edge information.
• As discussed in class, it should not be possible for clients of a graph to break the abstraction by adding edges, making illegal weights, etc. So the code most have enough copy-in-copy-out and immutability to prevent clients from doing such things.

Other useful information:

• The Vertex and Edge classes have already defined an appropriate equals method (and, therefore, as we discussed in class, they also define hashCode appropriately). If you need to decide if two Vertex objects are "the same", you probably want to use the equals method and not ==.
• You will likely want some sort of Map in your program so you can easily and efficiently look up information stored about some Vertex. (This would be much more efficient than, for example, having a Vertex[] and iterating through it every time you needed to look for a particular Vertex.)
• 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.

Programming, Part 2

In this part of the assignment, you will use your graph from Part 1 to compute shortest paths. The MyGraph class has a method shortestPath you should implement to return the lowest-cost path from its first argument to its second argument. Return a Path object as follows:

• If there is no path, return null.
• If the start and end vertex are equal, return a path containing one vertex and a cost of 0.
• Otherwise, the path will contain at least two vertices -- the start and end vertices and any other vertices along the lowest-cost path. The vertices should be in the order they appear on the path.

Because you know the graph contains no negative-weight edges, Dijkstra's algorithm is what you should implement. Additional implementation notes:

• One convenient way to represent infinity is with Integer.MAX_VALUE.
• Using a priority queue is above-and-beyond. 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 definitely need to be careful to use equals instead of == to compare Vertex objects. The way the FindPaths class works (see below) is to create multiple Vertex objects for the same graph vertex as it reads input files. You may want to refer to your old notes on the equals method from CSE143. Remember that equals lets us compare 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.

The program in FindPaths.java is mostly provided to you. When the program begins execution, it reads two data files and creates a representation of the graph. It then prints out the graph's vertices and edges, which can be helpful for debugging to help ensure that the graph has been read and stored properly. Once the graph has been built, the program loops repeatedly and allows the user to ask shortest-path questions by entering two vertex names. The part you need to add is to take these vertex names, call shortestPath, and print out the result. Your output should be as follows:

• If the start and end vertices are X and Y, first print a line Shortest path from X to Y:
• If there is no path from the start to end vertex, print exactly one more line does not exist
• Else print exactly two more lines. On the first additional line, print the path with vertices separated by spaces. For example, you might print X Foo Bar Baz Y. (Do not print a period, that is just ending the sentence.) On the second additional line, print the cost of the path (i.e., just a single number).

The FindPaths code expects two input files in a particular format. The names of the files are passed as command-line arguments. The provided files vertex.txt and edge.txt have the right formate to serve as one (small) example data set where the vertices are 3-letter airport codes. Here is the file format:

• The file of vertices (the first argument to the program) has one line per vertex and each line contains a string with the name of a vertex.
• The file of edges (the second argument to the program) has three lines per directed edge (so lines 1-3 describe the first edge, lines 4-6 describe the second edge, etc.) The first line gives the source vertex. The second line gives the destination vertex. The third line is a string of digits that give the weight of the edge (this line should be converted to a number to be stored in the graph).

Note data files represent directed graphs, so if there is an edge from A to B there may or may not be an edge from B to A. Moreover, if there is an edge from A to B and an edge from B to A, the edges may or may not have the same weight.

Write-Up Questions

1. Describe the worst-case asymptotic running times of your methods adjacentVertices, edgeCost, and shortestPath. In your answers, use |E| for the number of edges and |V| for the number of vertices. Explain and justify your answers.
2. Describe how your code ensures the graph abstraction is protected. If your code makes extra copies of objects for (only) this purpose, explain why. If not, explain why it is not necessary.
3. Describe how you tested your code.
4. If you worked with a partner, describe how you worked together. If you divided up the tasks, explain how you did so. If you worked on parts together, describe the actual process. Discuss how much time you worked together and how you spent that time (planning, coding, testing, ...). Be sure to describe at least one good thing and one bad thing about the process of working with a partner.
5. If you did any above-and-beyond, describe what you did.

Above and Beyond

• Find an interesting real-world data set and convert it into the right format for your program. Describe in your write-up questions what the data is and what a shortest path means. Turn in your data set in the right format as two additional files.
• Improve your implementation of Dijkstra's algorithm by using a priority queue. Note that for Dijkstra's algorithm, we need to find items in the priority queue and update their priorities (the decreaseKey operation). We would like to find items in constant time (and then logarithmic time for changing the priority). 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, but be sure to indicate in your write-up that you did this.
• Extend MyGraph with a method for computing minimum spanning trees using one of the efficient algorithms discussed in class. Also write a driver program that reads in a graph and prints a minimum spanning tree. This driver will be much like FindPaths, but make a separate file and do not prompt the user for vertices or have a loop -- just print one minimum spanning tree. Explain in your write-up the format of what you print.

What to Turn In

If you work with a partner, only one partner should submit the files. Be sure to list both partners' names in your files.

You will turn in everything electronically. This should include all your code files, including the files provided to you (but you do not need to turn in vertex.txt and edge.txt). This should also include a file with your write-up; do not forget to turn in your write-up.