Homework 5 – Graphs
Due December 10th 11:59pm eastern
In class we talked about adjacency lists and used the integer labels of vertices as the location in the vertex array. If your graph is labeled with non-integer data then we need to adjust our data structure to handle that. For the adjacency list it is straightforward to use a HashMap instead of an array to keep track of the set of vertices. This allows any labels as long as they are hashable and we know that the average case runtime should be comparable to using an array.
Implement the graph ADT using an adjacency list that can handle generic labels. You should include the following methods.
● (10 points) addEdge(T x, T y)
○ creates the vertices if they don’t yet exist and connects them with a directed edge
from x to y
○ It is crucial that you finish this method and fully test it first. addEdge is needed to create the graphs, so you won’t be able to finish the other parts of this homework without it.
● (5 points) removeEdge(T x, T y)
● (3 points) isEdge(T x, T y)
● (5 points) neighbors(T x)
● (2 points) numVertices()
● (5 points) numEdges()
● (10 points) removeVertex(T x)
■ removes the vertex given and all edges connected to it in both directions
■ this means searching for all the edges that include this vertex
(10 points) Write a constructor for Graph that takes in filename of a .dot file in the local directory, reads its content, and creates the corresponding graph. You can learn more about the DOT graph description language here https://en.wikipedia.org/wiki/DOT_(graph_description_language). You can use graphviz to generate images from DOT files. Try this out here http://www.webgraphviz.com/. You can do all sorts of crazy stuff with graphviz, but we are going to stick to the most basic functionality with files in this form.
digraph {
A->B
A->C
B->D
}
digraph tells us it’s a directed graph. Then each line is an edge. The first line in this example defines the first two vertices by their labels A and B, and creates an edge between them. Whatever names are on either side of the arrow are the unique labels for that vertex, so the first and second edges refer to the same A.
(10 points) Write a toDotFile method that takes a filename for a .dot file and writes the current state of the graph object out to DOT file in the same format you read it in in the previous part. Now you can load up a graph from a file, change it using your Graph class, and save those changes for later. You can then take that DOT file and visualize it here http://www.webgraphviz.com/.
(10 points) Write a depth first search method like the one we looked at in class. You will have to make a few changes to adapt to the the generic typing and HashTable. It should print out the labels of vertices in the order in which they were visited.
(10 points) Write a breadth first search method like the one we looked at in class. You will have to make a few changes to adapt to the the generic typing and HashTable. It should print out the labels of vertices in the order in which they were visited.
(5 points) Write another depth first search method without using recursion. This requires only a small change to breadth first search so that it uses a Stack instead of a Queue.
(15 points) Coding style. We’re not out to get you if your code doesn’t look perfect, but keep these things in mind because we will be reading through the code in addition to running tests. If it’s a mess then this is where you will lose points.
● Readability. Good variable names and clean coding style. Can someone tell what your code does by reading it?
● Formatting. You should probably use an auto formatter. Misaligned code, lines that run too long, expressions smushed together, etc. are no good.
● Comments. Clarify complex bits of code where it isn’t as readable by itself. Labeling multiple if/else/cases.
● Descriptive method comments in Javadoc format (5% extra credit)
○ Javadoc comments are for people who will use your code and need a nice
reference for what the methods do.
○ In line comments are still needed as well. These are for people who will actually
be reading your code to understand what it does more easily.
Late policy
● Max 24 hours late
● 10 percent off for late submission
● No prorated penalty based on how late it is
● 5 minutes late is still 10 percent off
Questions/Clarifications?
Take them to piazza and do it sooner rather than later. Please post publicly (you can still be anonymous if you wish) to the whole class so everyone can see the answer and stay on the same page.
Reviews
There are no reviews yet.