public class Graph_2_Tester { private static final ArrayList tests = new ArrayList(); public static void main(String[] args) { constructorTests(); deleteEdgeTest(); deleteVertexTest(); degreeTest(); // maxDegreeTest(); // minDegreeTest(); // averageDegreeTest(); // degreeSequenceTest(); TestResult.reportTestResults(tests); } public static void constructorTests() { String[] vertices = {"A", "B", "C", "D"}; Graph g = new StringGraph(vertices); tests.add(new TestResult("Constructor 1", 4, g.numberOfVertices())); tests.add(new TestResult("Constructor 2", 0, g.numberOfEdges())); tests.add(new TestResult("Constructor 3", 4, g.capacity())); tests.add(new TestResult("Constructor 4", true, g.vertexExists("A"))); tests.add(new TestResult("Constructor 5", true, g.vertexExists("B"))); tests.add(new TestResult("Constructor 6", true, g.vertexExists("C"))); tests.add(new TestResult("Constructor 7", true, g.vertexExists("D"))); vertices = new String[]{"A", "B", "C", "D"}; String[][] edges = {{"A", "C"}, {"C", "D"}, {"D", "A"}}; g = new StringGraph(vertices, edges); tests.add(new TestResult("Constructor 8", 4, g.numberOfVertices())); tests.add(new TestResult("Constructor 9", 3, g.numberOfEdges())); tests.add(new TestResult("Constructor 10", 4, g.capacity())); tests.add(new TestResult("Constructor 11", true, g.vertexExists("A"))); tests.add(new TestResult("Constructor 12", true, g.vertexExists("B"))); tests.add(new TestResult("Constructor 13", true, g.vertexExists("C"))); tests.add(new TestResult("Constructor 14", true, g.vertexExists("D"))); tests.add(new TestResult("Constructor 15", true, g.edgeExists("A", "C"))); tests.add(new TestResult("Constructor 16", true, g.edgeExists("C", "A"))); tests.add(new TestResult("Constructor 17", true, g.edgeExists("C", "D"))); tests.add(new TestResult("Constructor 18", true, g.edgeExists("D", "C"))); tests.add(new TestResult("Constructor 19", true, g.edgeExists("D", "A"))); tests.add(new TestResult("Constructor 20", true, g.edgeExists("A", "D"))); } public static void deleteEdgeTest() { String[] vertices = new String[]{"A", "B", "C", "D"}; String[][] edges = {{"A", "C"}, {"C", "D"}, {"D", "A"}}; Graph g = new StringGraph(vertices, edges); g.deleteEdge("A", "C"); tests.add(new TestResult("Delete Edge 1", false, g.edgeExists("A", "C"))); tests.add(new TestResult("Delete Edge 2", 4, g.numberOfVertices())); tests.add(new TestResult("Delete Edge 3", 2, g.numberOfEdges())); tests.add(new TestResult("Delete Edge 4", true, g.vertexExists("A"))); tests.add(new TestResult("Delete Edge 5", true, g.vertexExists("C"))); } public static void deleteVertexTest() { String[] vertices = new String[]{"A", "B", "C", "D"}; String[][] edges = {{"A", "C"}, {"C", "D"}, {"D", "A"}}; Graph g = new StringGraph(vertices, edges); g.deleteVertex("A"); tests.add(new TestResult("Delete Vertex 1", false, g.vertexExists("A"))); tests.add(new TestResult("Delete Vertex 2", 3, g.numberOfVertices())); tests.add(new TestResult("Delete Vertex 3", 1, g.numberOfEdges())); tests.add(new TestResult("Delete Vertex 4", true, g.edgeExists("D", "C"))); } public static void degreeTest(){ /* B\ /E | \ / | | A---D | G | / \ | C/ \F */ Graph g = new StringGraph(new String[]{"A", "B", "C", "D", "E", "F", "G"}); g.addEdges(new String[][]{{"A", "B"}, {"B", "C"}, {"C", "A"}}); g.addEdges(new String[][]{{"D", "E"}, {"E", "F"}, {"F", "D"}}); g.addEdge("A", "D"); tests.add(new TestResult("Degree 1", 3, g.degree("A"))); tests.add(new TestResult("Degree 2", 2, g.degree("B"))); tests.add(new TestResult("Degree 3", 2, g.degree("C"))); tests.add(new TestResult("Degree 4", 3, g.degree("D"))); tests.add(new TestResult("Degree 5", 2, g.degree("E"))); tests.add(new TestResult("Degree 6", 2, g.degree("F"))); tests.add(new TestResult("Degree 7", 0, g.degree("G"))); tests.add(new TestResult("Max Degree 1", 3, g.maxDegree())); tests.add(new TestResult("Min Degree 1", 0, g.minDegree())); tests.add(new TestResult("Average Degree 1", 2.0, g.averageDegree())); tests.add(new TestResult("Degree sequence 1", new int[]{3,3,2,2,2,2,0}, g.degreeSequence())); } }

--------Separate File-----------

public interface Graph { static final int DEFAULT_CAPACITY = 1; int numberOfVertices(); /** * Returns the number of edges in this graph (the "size" of this graph). * * @return the number of edges in this graph */ int numberOfEdges(); /** * Creates and returns a new array of Strings containing the vertices of * this graph. The length of the returned array equals the number of * vertices. The order of the vertices is unspecified. * * @return a String array containing the vertex labels */ String[] getVertices(); /** * Creates and returns a new 2D array of strings containing the edges of * this graph. The size of the returned array is m x 2. In other words, * there is one row for each edge. The order of the edges is unspecified * and the order of the vertices in each edge is also unspecified. * For example, a graph with the three edges * {"A", "B"}, {"C", "A"}, and {"F", "D"} may return: * * { * {"A", "B"}, {"C", "A"}, {"F", "D"} } * * @return an m x 2 array in which each row represents and edge in this * graph. */ String[][] getEdges(); /** * Returns the number of vertices that can be added to this graph before * the array of vertices needs to be increased. * * @return the number of vertices that can be added to this graph before the * array of vertices needs to be increased. */ int capacity(); /** * Resizes the array of labels and the adjacency matrix to a new capacity. * If the new capacity is larger than the current capacity, the capacity is * increased. Note: In future assignment the capacity may also be made * smaller. * newCapacity. * * @param newCapacity The new capacity */ void resize(int newCapacity); /** * Determines if a vertex with the given label exists. * * @param vertex the label of a vertex. * @return true of the vertex exist, false if it does not exist. */ boolean vertexExists(String vertex); /** * Adds a new vertex to this graph. * * @param vertex the new vertex to be added * @throws GraphException if the specified vertex already exists. */ void addVertex(String vertex) throws GraphException; /** * Adds one or more vertices to this graph. * * @param vertices the vertices to be added */ void addVertices(String[] vertices); /** * Determines if an edge with the given end vertices exists. * * @param vertex1 the label of one end of the edge * @param vertex2 the label of the other end of the edge * @return true edge {vertex1, vertex2} is in this graph, returns false if * the edge is not in this graph * @throws GraphException if either vertex1 or vertex2 is not in this graph. */ boolean edgeExists(String vertex1, String vertex2) throws GraphException; /** * Adds a new edge. * * @param vertex1 the label of one end of the new edge * @param vertex2 the label of the other end of the new edge * @throws GraphException if the edge already exists or if either end vertex * does not exist. */ void addEdge(String vertex1, String vertex2) throws GraphException; /** * Adds multiple edges. Each row i in the edges parameter represents the * pair of vertices edges[i][0] and edges[i][1] for a new edge. * * @param edges a 2 x w array of vertices, w ≥ 0 */ void addEdges(String[][] edges); /** * Returns a string representation of this Graph. * * @return a string representation of this Graph. */ @Override String toString(); // ========================================================================= // The following methods are added in assignment part 2 /** * Deletes a vertex and all of its incident edges. * * @param vertex the vertex to be deleted * @throws GraphException if vertex does not exist. */ void deleteVertex(String vertex) throws GraphException; /** * Deletes an edge. * * @param vertex1 one end vertex of the edge * @param vertex2 the other end vertex of the edge * @throws GraphException if the edge does not exist or if either end vertex * does not exist. */ void deleteEdge(String vertex1, String vertex2) throws GraphException; /** * Returns the degree of a vertex * * @param vertex the vertex of interest * @return the degree of the given vertex * @throws GraphException if the vertex does not exist. */ int degree(String vertex) throws GraphException; /** * Returns the maximum degree of the graph * * @return the maximum degree */ int maxDegree(); /** * Returns the minimum degree of the graph. * * @return the minimum degree */ int minDegree(); /** * Returns the average degree of the graph * * @return the average degree */ double averageDegree(); /** * Return the degree sequence for this graph. The degree sequence is a * sequence consisting of the degree of each vertex, sorted from largest to * smallest. * * @return an int array containing the degrees of all vertices, sorted from * largest degree to smallest degree. */ int[] degreeSequence(); }

Homework 04 - Graph Part 2 (15 points) Note: Homework assignments HW 03, HW 04, HW 07, HW 13, and HW 15 are all related. Each of these assignments builds on the previous assignment. For this assignment additional methods have been added to the Graph interface. You are to revise your StringGraph class from Part 1 of the Graph assignment to implement these additional methods. Details 1. Your class must still be named StringGraph. 2. It must implement the new Graph interface. 3. Your class should not have a main method. 4. You will need to use your GraphException class from part 1. 5. Your StringGraph class should use the same instance variables as in part 1. 6. Your class must include the two new constructors described in avgdoc for this assignment. 7. Your class must implement all the methods specified in the Graph interface. See the JavaDoc comments for a description of each method. 8. Your class must include the @Override annotation for each interface methods i implements. 9. The documentation for the StringGraph class again includes some additional methods that not required by the Graph interface. These are included as hints about methods you may wish to include in your class. You are not required to include these additional methods. You are only required to implement the methods specified in the Graph interface. Tester Program You are being provided with a new Tester program, called Graph_2_Tester.java. If your StringGraph class is working correctly the tester will print a message indicating that all tests were passed, otherwise error messages will be printed. The tester from part 1. Graph_1_Tester.java, should still report no errors. What to Turn In Compress the entire folder created by NetBeans into a single zip file and submit that zip file through Blackboard. Your project should include the following files: a. Graph.java - You should download this file and use it as-is. Make no changes to this file. Note that this is not the same file that was used in part 1. b. Graph_2_Tester.java - You should download this file and use it as-is. Make no changes to this file. c. TestResult.java - You should download this file and use it as-is. Make no changes to this file. d. GraphException.java - This is your file. e. StringGraph.java - This is your file. import java. uti1.ArrayList; import java.util.Arrays; F* Used with the tester progran. * Holds results of a single result. public class Testresult f private String message; private String expectedMsg; private string receivedMsg; private boolean passed; public TestResult(String nessage, String expected, String recelved) \{ this . nessage = message; this. expectedMsg = expected; this. recelvedisg = recelved; \} passed = expected. equals(recelved); public TestResult(String nessage, String[] expected, String[] recelved) f this .nessage = message; expectedMsg = Arrays, tostring(expected); recelvedisg = Arrays. tostring(recelved); \} passed = Arrays. equals (expected, recelved ); public TestResult(String nessage, String[][] expected, string[][] received) \{ this.nessage = message; If (expected. length 1= received. length) \{ expectedisg ="20 array has length "+ expected.length; recelvedisg = "20 array has length "+ recelved.length; passed = false; \} return; for (Int r=0;r