CSE373 Summer 2017: 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.


Due Dates, Turn-In, and Rules

Pair-Programming Opportunity: For this assignment, you may (optioanlly) work with a partner through pair-programming, where you write all your code together as two people at one keyboard. Switch off regularly to spend equal time in the roles of the “driver” (who’s typing) and the “navigator” (suggesting what to type). Working on any part of the code separately would be a violation of academic integrity and considered cheating. Because you must be in the same physical space throughout working on this assignment, choose partnerships and plan schedules accordingly, and start early! Should you choose to partner up, only one of you will turn in the assignment. Also fill out this catalyst survey: https://catalyst.uw.edu/webq/survey/ldegreef/337761.
Beyond working with a partner, all the usual collaboration policies apply.

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 5:00PM Friday August 4, 2017

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, what did you think of the experience? At minimum, what was one thing you benefitted from or liked it, and what was one you didn't?
  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 and fill out the catalyst survey.

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