CSE 373 Winter 2017: Homework 4 - Graphs

Due: Wednesday, February 22nd, 11pm

Overview

Overview:

For this assignment, you will develop a graph representation. You will be using this graph representation for the next homework assignment to implement Dijkstra's algorithm for finding shortest paths.

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 in class.

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.

Provided Files

Provided Files:

Download these files into a new directory:

Functionality

Required Public Functionality

In this assignment, you will implement a graph representation that you will use in the next homework assignment. 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 the Graph.java interface. 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 next week. You do not know the sparsity or density of the Graph data you might represent with your graph.

Mutability: Unlike HW#3, you do have to worry about preserving the abstraction from your Client through returning aliases to internal objects. You do have to make objects immutable, or deep copy objects when returning them to the Client. In particular, this means:

Other useful information:

Style: For this assignment we will be grading similarly, but a little more strictly for things like style and efficiency than we did on HW #3. Make sure you are commenting your code, looking for redundancy, structural mistakes, formatting of your code, efficiency of your algorithms, and preserving the abstraction of your classes through encapsulated fields, private methods when appropriate, copying and immutability, and appropriate level of commenting on public functionality.

Feel free to add additional public functionality that you think would be useful for a client. There might be some redundant code between your public methods; it might help to make some private helper methods to clean up your code.

Write-Up

Write-Up Questions

  1. Describe the worst-case asymptotic running times of your methods adjacentVertices and edgeCost. 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 did the above-and-beyond, describe what you did.
Extra Credit

Extra Credit: 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, the source you got it from, and what a path in this graph data means. You'll also need to write some client code MyClient.java to parse your data into your graph. Turn in your client code MyClient.java, your data set in the right format as two additional files. my_vertices.txt and my_edges.txt

Turn-In

What to turn in:

Due: Wednesday, February 22nd, 11pm

You should submit a zip file to the Canvas dropbox with the name cse373_17wi_hw4.zip. This should not have a nested folder inside the zip. When you unzip the turned in zip file, it should only have the expected files.

The expected files are all the provided code files and any additional files you created: