Problem Set 4: Graphs and Testing

Repository link: https://github.com/CSE-116/ProblemSet-4

To submit your project, run problem.Zipper, which will create a zip file containing the problem set, and submit it to Autolab.

Specification

For this problem set, you will complete public static methods in the problem.ProblemSet4 class. Each method takes a Graph<T> and is generic over the node type T. The graph uses only bidirectional edges (see Graph.addBidirectionalEdge). Method signatures appear in the starter code.

• countEdges (Testing: 5 points, Implementation: 5 points): In the problem.ProblemSet4 class, complete the countEdges method, which takes a Graph as a parameter and returns an int. This method returns the number of edges in the input graph. Each undirected edge between two distinct nodes counts once (the adjacency list stores each edge twice, once per endpoint)
  • Note that this method takes a type parameter along with a graph matching the type parameter. This method will work regardless of the type of the values stored in the graph. This will be true for all methods in this problem set
• maxDegree (Testing: 5 points, Implementation: 5 points): In the problem.ProblemSet4 class, complete the maxDegree method, which takes a Graph as a parameter and returns an int. This method returns the maximum degree among all nodes (Degree of a node is the number of neighbors of that node)
  • An empty graph has maximum degree of 0
• isConnected (Testing: 5 points, Implementation: 5 points): In the problem.ProblemSet4 class, complete the isConnected method, which takes a Graph as a parameter and returns a boolean. This method returns true if the input graph is connected, and false otherwise
  • A graph is connected if there exists a path connecting every pair of nodes in the graph. In other words, if you start at any node you can travel to all other nodes in the graph by following edges
  • A graph with no nodes is connected
  • A graph with only isolated nodes (no edges) is connected if and only if it has at most one node
• numberOfConnectedComponents (Testing: 5 points, Implementation: 5 points): In the problem.ProblemSet4 class, complete the numberOfConnectedComponents method, which takes a Graph as a parameter and returns an int. This method returns the number of connected components in the graph
  • The empty graph has 0 components
  • Each isolated node (degree 0) is its own component
• detectCycle (Testing: 5 points, Implementation: 5 points): In the problem.ProblemSet4 class, complete the detectCycle method, which takes a Graph as a parameter and returns a boolean. This method returns true if the graph contains at least one cycle, and false otherwise
  • Hint: You can build a BFS tree by running BFS on a graph and creating a new graph that contains only the edges that were used to discover new nodes. If the input was already a tree (no cycles), then the input graph and the BFS tree will have all the same edges
  • Caution: The input graph does not have to be connected
  • If any connected component contains a cycle, return true
  • A graph with no nodes has no cycles

Testing Requirements

Write tests for the methods in the specification in the tests.TestProblemSet4 class. You are encouraged to write tests before you implement each method. If a test fails, use the debugger to find and fix your bug.

• countEdges
  • Write tests for the countEdges method. Test that the proper value is returned in a variety of cases
  • Use the provided Graph class to construct a graph. The number of times you call addBidirectionalEdge should be the expected number of edges
  • For all methods, you are testing methods that take a Graph that takes a type parameter. You may choose any type when you create your graphs (eg. Using whatever is simplest, like Integer, is fine). Since nodes are stored as keys in a HashMap, your Graph cannot contain duplicate node values
• maxDegree
  • Write tests for the maxDegree method. Test that the proper value is returned in a variety of cases
• isConnected
  • Write tests for the isConnected method. Test that the proper value is returned in a variety of cases
  • The addNode method in the Graph class is public in this version of the code in case you want to add nodes with no edges while creating disconnected graphs
• numberOfConnectedComponents
  • Write tests for the numberOfConnectedComponents method. Test that the proper value is returned in a variety of cases
  • Use addNode when you need isolated nodes
• detectCycle
  • Write tests for the detectCycle method. Test that the proper value is returned in a variety of cases
  • Be sure to include test cases where the input graph is not connected

Programming Requirements

Implement the methods from the specification.

You are encouraged to complete the Testing Requirements before you begin implementation so you can run your tests as you implement each part.

Autolab Feedback

With testing now being required, feedback from Autolab will be given in several phases.

1. Running your tests on a correct solution
   • Your tests will be run against a solution that is known to be correct. If your tests do not pass this correct solution, there is an error somewhere in your tests that must be fixed before you can move on with the assignment. If your tests don't get past this check, you should re-read this document and make sure you implemented your tests and code according to the specification. You should also make sure that if there are multiple correct outputs to the input in your test cases that you accept any of the outputs as correct
   • Note: If you fail this phase, you will not be able to move on to the next phase
2. Checking your tests for feature coverage
   • The next phase is to check if your tests check for a variety of features defined by different inputs. You should write at least one test case for each feature to pass this phase
   • Passing this phase does not necessarily mean that your testing is completely thorough. Satisfying Autolab is the bare minimum testing requirement. Not all possible inputs are checked and it is sometimes possible to pass this phase with weak testing. If you are struggling to earn credit for code that you believe is correct, you should write more than the required tests
3. Running Autolab's tests on your submission
   • If your testing is thorough, and your code passes your tests, then you should pass this phase. If you pass your tests, but fail one of Autolab's tests, it is an indicator that you should write more tests to help expose your bug