Undirected Graph Neighborhood Count

Geoffrey Challen // 2021.10.0

Create a method count. count accepts two parameters: a UnweightedGraph<Int> from cs1.graphs, and an Int. You should return the count of the number of nodes in the graph where the number of 2-hop neighbors of that node is at least as large as the passed Int. If the passed Int is less than or equal to zero, throw an IllegalArgumentException.

What is a 2-hop neighbor? Consider the node B in the following simple unweighted undirected graph:

A - B - C - D - E

B has 4 1-hop neighbors: A, F, C, and H, nodes that are reachable in 1 hop from B. B has 6 2-hop neighbors: A, F, C, H, J, and D, nodes that are reachable in 2 hops from B.

To solve this problem you'll need to write a recursive helper method that you can run starting at each node in the graph, which you can enumerate using the nodes properly of the graph as described below. Your recursive method will need to keep track of two things as it explores the graph: a set of nodes that have already been visited, to avoid backtracking, and the distance from the start node. Your base case can be either reaching a node you have already visited, or reaching 2 hops from the start, at which point you should stop exploring.

Note that your count will probably be off by one, since you'll probably end up including the start node in your calculation. Be sure to keep that in mind.

This problem is tricky to set up, so we've provided some starter code to get you going. Good luck, and have fun!

For reference, cs1.graphs.UnweightedGraph is declared somewhat like this:

And cs1.graphs.GraphNode is declared somewhat like this: