Refer to attached file
Com S 311 Programming Assignment 2 200 Points Due: July 2, 11:59PM Late Submission Due: July 3, 11:59PM(25% Penalty) 1 Introduction In this assignment, you will implement BFS algorithm to compute certain graph properties. Note that the description of a programming assignment is not a linear narrative and may require multiple readings before things start to click. You are encouraged to consult the instructor and Teaching Assistants for any questions/clarifications regarding the assignment. You are allowed to use Java’s inbuilt data structures (such as hashMap, hashSet, etc). However, you not allowed to use any external libraries/packages. Your code must strictly adhere to the specifications. The names of methods and classes must be exactly as specified. The return types of the methods must be exactly as specified. For each method/constructor the types and order of parameters must be exactly as specified. Otherwise, you will lose a significant portion of points (even if your program is correct). All your classes must use what Java refers to as the default package, that is, they must not specify a package. Your grade will depend on adherence to specifications, correctness of the methods/programs, and efficiency of the methods/programs. If your programs do not compile, you will receive zero credit. 2 Graph Processor Given an unweighted (directed/undirected) graph G = (V, E), let s(u, v) denote the length of the shortest path between u and v. If there is no path from u to v, then s(u, v) is defined as 2n where n is the number of vertices in G. Diameter of G is max u,v∈V s(u, v). In other words, for (strongly) connected graphs, the diameter is the smallest number d such that there is a path of length ≤ d between any pair of vertices. For graphs that are not (strongly) connected diameter is 2n. Given a vertex x ∈ V , centrality of x is the number of shortest paths that go through x. More precisely centrality(x) is the size of the following set: {〈u, v〉|u, v ∈ V, at least one shortest path from u to v goes through x}. Design a class named GraphProcessor. This class will have the following constructor. GraphProcessor(String graphData) The argument graphData holds the absolute path of a file that stores a directed graph. This file will be of the following format: The first line indicates number of vertices. Each subsequent line lists a directed edge of the graph. The vertices of this graph are represented as strings. For example, the contents of the file may look like the following: 4 Ames Minneapolis 1 Minneapolis Chicago Chicago Ames Ames Omaha Omaha Chicago This class must also have the following methods. These methods should be public, and imple- mented out side the constructor. outDegree(String v) Returns the out degree of v. bfsPath(String u, string v) Returns the BFS path from u to v. This method returns an array list of strings that represents the BFS path from u to v. Note that this method must return an array list of Strings. The first vertex in the path must be u and the last vertex must be v. If there is no path from u to v, then this method returns an empty list. The return type is ArrayList
. diameter() Returns the diameter of the graph. centrality(String v) Returns the centrality of the vertex v. Any other methods that you write must be private. Only the above listed methods must be public. You may write additional classes. 3 What to Submit • GraphProcessor.java • Any additional classes that you created. You must include any additional helper classes that you designed. Please include only source .java files, do not include any .class files nor other unnecessary files or folders. Please remember to use the default package for all java classes. Place all the files that need to be submitted in a folder (without any sub-folders) and zip that folder. Name of the folder must be YouNetID-PA2. Submit the .zip file. Only zip files please. 2