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.
Download these files into a new directory:
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.
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
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: