Homework 8: Graph Algorithms Solution

Graph Algorithms




For this assignment, you will be coding 4 di erent graph algorithms. WARNING: This homework has quite a few les in it, so you should make sure to read ALL of the documentation given to you, including this pdf as well as all of the javadocs before asking a question.




Graph Representations




For this assignment, you will be using two di erent representations of graphs, the adjacency list and adjacency matrix. The adjacency list will be used for Dijkstra’s, Prim’s and Kruskal’s. The adjacency matrix will be used for DFS.




Generally, an adjacency matrix is better for when the graph is dense (many edges), and an adjacency list is better for when the graph is sparse (fewer edges). Also, it’s worth noting from here on out, the time complexities will have two inputs, jV j to mean the number of vertices, and jEj to mean the number of edges. Although it is true that a simple graph can have at most jEj jV j(jV j 1) = O(jV j2) edges,




2




other than this, there isn’t really any relationship between jV j and jEj.




Keep in mind that the way that the graph is stored/represented will a ect the time complexity of the algorithm. For example, for Dijkstra’s algorithm, if an adjacency matrix is used, the time complexity is O(jV j2) while if an adjacency list with a priority queue is used, it is instead O(jEj + jV j log jV j).




Depth First Search




Depth-First Search is a search algorithm that visits all the vertices in a certain branch before moving onto another branch. DFS depends on a Stack based data structure to work. Your implementation of DFS MUST be recursive to receive credit. You will be using an adjacency matrix for your implementation of DFS.










1
Homework 8: Graph Algorithms Due: See T-Square










One important property of DFS is that you can gure out if the graph is connected or not by running either of the algorithms. This can be done by seeing if all of the vertices have been visited on termination of the algorithm. For your implementation, if the graph is disconnected, the list of vertices will not contain all of the vertices in the graph.




You will be modifying the passed in list, adding the vertices in the order that you visit them, and you will return whether the graph is connected or not.




Single-Source Shortest Path (Dijkstra’s Algorithm)




The next algorithm is Dijkstra’s algorithm. This algorithm nds the shortest path from one vertex to all of the other vertices in the graph. This algorithm only works for non-negative edge weights, so you will have to account for this in your algorithm in accordance with the javadocs. This algorithm will be implemented using an adjacency list along with a priority queue.




Minimal Spanning Trees (MST)




The last two algorithms are Prim’s and Kruskal’s algorithms to nd the minimal spanning tree (MST) of the graph. An MST is a tree that uses only edges from the original graph that connects all of the vertices in the graph.




Prim’s Algorithm begins at an arbitrary vertex and visits an adjacent vertex using the cheapest edge from that vertex. This algorithm will naturally partition the vertices into those that have been visited and those that have been not, and the algorithm will continually add the edge that adds a new vertex with the cheapest cost to the visited portion.




Kruskal’s Algorithm takes in all of the edges of the graph and continually adds the cheapest to the MST as long as that edge does not form a cycle. This means that as the algorithm progresses, there will be multiple disconnected components that will eventually come together if the original graph is connected. To handle cycle detection and these disconnected components, you will be using a disjoint-set/union- nd data structure that we have provided for you.




If the original graph is disconnected, these algorithms should instead return a minimal spanning forest (MSF), described in the javadocs. You may assume that the passed in graph has a unique MST/MSF and that the graph is undirected, so the starting vertex for Prim’s algorithm does not matter. You will be implementing both of these algorithms using an adjacency list.




Disjoint Set Data Structure (Union-Find)




For Kruskal’s algorithm, you will be using the DisjointSet class implementation that we have provided to maintain which components are connected. This data structure has two primary functions, union and find. The idea here is that each disconnected component is maintained as a tree. So, the DisjointSet class maintains these disconnected components.




If you want to check and see whether two pieces of data are within the same component (they are connected), then you merely have to check whether the roots of their components are the same. The find method nds the root of the component’s tree.




If you add an edge to the MST in Kruskal’s, then it will cause two previously disconnected components to become a single component. The union method does this for you, merging the two trees representing the two components.






















2
Homework 8: Graph Algorithms Due: See T-Square










Grading




Here is the grading breakdown for the assignment. There are various deductions not listed that are incurred when breaking the rules listed in this PDF, and in other various circumstances.




Methods:






DFS
15pts




Dijkstra’s
25pts




Prim’s
20pts




Kruskal’s
15pts




Other:






Checkstyle
10pts




E ciency
15pts




Total:
100pts










A note on JUnits




We have provided a very basic set of tests for your code, in GraphAlgorithmsStudentTests.java. These tests do not guarantee the correctness of your code (by any measure), nor does it guarantee you any grade. You may additionally post your own set of tests for others to use on the Georgia Tech GitHub as a gist. Do NOT post your tests on the public GitHub. There will be a link to the Georgia Tech GitHub as well as a list of JUnits other students have posted on the class Piazza.




If you need help on running JUnits, there is a guide, available on T-Square under Resources, to help you run JUnits on the command line or in IntelliJ.




Visualizations of Graphs




The directed graph used in the student tests is:







1 4 6



















2 3 5 7







The undirected graph used in the student tests is:







7

A B




5
8



3



C




F
2
D
E
6








1











3
Homework 8: Graph Algorithms Due: See T-Square










Style and Formatting




It is important that your code is not only functional but is also written clearly and with good style. We will be checking your code against a style checker that we are providing. It is located in T-Square, under Resources, along with instructions on how to use it. We will take o a point for every style error that occurs. If you feel like what you wrote is in accordance with good style but still sets o the style checker please email Grayson Bianco (gbianco6@gatech.edu) with the subject header of \CheckStyle XML".




Javadocs




Javadoc any helper methods you create in a style similar to the existing Javadocs. Like the existing Javadocs, the Javadocs for your helper method(s) must describe well what the method does, what each parameter means (if any), and what the returned value is (if any). If a method is overridden or implemented from a superclass or an interface, you may use @Override instead of writing Javadocs.




Exceptions




When throwing exceptions, you must include a message by passing in a String as a parameter. The mes-sage must be useful and tell the user what went wrong. \Error", \BAD THING HAPPENED", and \fail" are not good messages. The name of the exception itself is not a good message.




For example:




throw new PDFReadException("Did not read PDF, will lose points.");




throw new IllegalArgumentException("Cannot insert null data into data structure.");




Generics




If available, use the generic type of the class; do not use the raw type of the class. For example, use new LinkedList<Integer() instead of new LinkedList(). Using the raw type of the class will result in a penalty.




Forbidden Statements




You may not use these in your code at any time in CS 1332.




break may only be used in switch-case statements




continue package




System.arraycopy() clone()




assert()




Arrays class Array class Objects class Stack class




Collections class







4
Homework 8: Graph Algorithms Due: See T-Square










Collection.toArray()




Re ection APIs




Inner, nested, or anonymous classes




Debug print statements are ne, but nothing should be printed when we run them. We expect clean runs - printing to the console when we’re grading will result in a penalty. If you use these, we will take o points.




Provided




The following le(s) have been provided to you. There are several, but you will only edit one of them.




GraphAlgs.java



This is the class in which you will implement the di erent graph algorithms. Feel free to add private static helper methods but do not add any new public methods, new classes, instance variables, or static variables.




GraphAlgsStudentTests.java



This is the test class that contains a set of tests covering the basic operations on the GraphAlgs class. It is not intended to be exhaustive and does not guarantee any type of grade. Write your own tests to ensure you cover all edge cases.




GraphAdjList.java



This class represents a graph represented using an adjacency list. It will be used for Dijkstra’s, Prim’s, and Kruskal’s algorithms. Do not alter this le.




Vertex.java



This class represents a vertex in the graph. Do not modify this le.




Edge.java



This class represents an edge in the graph. It contains the vertices connected to this edge and its weight. It is used in conjunction with GraphAdjList. Do not modify this le.




DisjointSet.java



This class represents a union- nd data structure to be used for Kruskal’s algorithm, consisting of the operations nd and union. Do not modify this le.




DisjointSetNode.java



This class represents a node for DisjointSet.java. Do not modify this le.




GraphAdjMatrix.java



This class represents a graph represented using an adjacency matrix. It will be used for DFS. Do not alter this le.




Deliverables




You must submit all of the following le(s). Please make sure the lename matches the lename(s) below. Be sure you receive the con rmation email from T-Square, and then download your uploaded les to a new folder, copy over the interfaces, recompile, and run. It is your responsibility to re-test your submission and discover editing oddities, upload issues, etc.




GraphAlgs.java






5