Assignment 4 Undirected, simple graph algorithms

Assignment 4—Programming Part
 Objectives • Understand undirected, simple graph algorithms and data structures • Implement adjacency matrix data structure to represent graphs • Implement DFS (Depth First Search) graph traversal algorithms • Implement connected component algorithm • Implement cycle detection algorithm • Understand and implement preorder and post order graph traversal numberings Instructions You are to implement, using the template the given template but otherwise from scratch, a java class Graph225 to practice designing, implementing and testing algorithms and data structures for undirected, simple graphs. Note: You are to use the attached template Graph225.java. Additional helper methods may be implemented. However: do not change the method signatures of the original methods or class names/package. No marks will be given if file/classes/method signatures are changed. Part 1: Adjacency matrix data structure class Design and implement a java class Graph with includes the following methods generate, read and write to initialize an adjacency matrix. Graph provides square, symmetric adjacency matrices, which represent simple, undirected graphs. An adjacency matrix M represents a graph G=(V,E) where V is a set of n vertices and E is a set of m edges. The size of the matrix is n where n is in the range 4 to 15 only. Thus, the rows and columns of the matrix are in the range of 0 to n1 representing vertices. The elements of the matrix are 1 if the edge exists in the graph and 0 otherwise. Since the graph is undirected, the matrix is symmetric and contains 2m 1’s. Method read(fn) updates the graph’s adjacency matrix by reading data from a file named fn (cf. for the file structure please refer to the sample input file testadjmat.txt). Method write(fn) writes the graph’s adjacency matrix representation into a file with name fn. Method generate(n, density) populates a graph G of size n, with random data. The value of the density parameter is 1, 2 or 3 specifying the density of G—the number of edges m of the graph where m is in the range 𝑛 to "("$%) ’ . Density 1 means 𝑚=𝑛+’" +=," +; density 2 means 𝑚=".; and density 3 means 𝑚="’−"%0=’"+. generate populates the adjacency matrix by randomly by generating m pairs of random numbers (row, col) where row and col are in the range of 0 to n1 (i.e., edge from vertex row to vertex col or vice versa. You may use your random number generator from the previous assignment or java library functions to generate random numbers.

Part 2: Reachability Design and implement a java method reach(G, v) from scratch to traverse graph G represented, starting at vertex v, using the depth first search graph traversal algorithm. reach returns a vector R of n elements where R[j] is 1 if vertex j can be reached from v and 0 otherwise. Adjacent vertices must be visited in strictly increasing order (for automated marking). Use a local vector variable to represent visited nodes. Part 3: Connected Components Design and implement a java method connectedComponents(G) that computes the number connected components of a graph G. connectedComponents returns the number of components of G and 1 if graph G is connected. Adjacent vertices must be visited in strictly increasing order (for automated marking). Use a vector to represent visited nodes. Part 4: Cycles Design and implement a java method hasCycle(G) that determines whether graph G contains at least one cycle. hasCycle returns true if G has a cycle and false otherwise. Adjacent vertices must be visited in strictly increasing order (for automated marking). Use a vector to represent visited nodes. Part 5: Preorder and postorder numbers Design and implement java methods preOrder(G) and postOrder(G) that compute the preorder and postorder numbers of the vertices in G represented. These methods return the preorder and postorder numbers for each vertex in G in a vector of n elements. Adjacent vertices must be visited in strictly increasing order (for automated marking). Use a vector to represent visited nodes. Part 6: Testing Develop a method test to test and exercise the algorithms and data structures developed for the first five parts of this assignment extensively. The output generated by this method must convince the marker that the algorithms and data structures are implemented as specified. For example: • Generate graphs of different sizes and densities • Test the algorithms for different graphs • Test your algorithms using the sample input file testadjmat.txt