CSE373 Fall 2015: Homework 4 - 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

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.

Assignment Due 11:00PM Wednesday November 18, 2015

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, 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:

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:

Other useful information:

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:

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

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:

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:

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

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.


Valid CSS! Valid XHTML 1.1