Build Graph given a SuccessorsFunction and a set of nodes

Question

I would like to build a Guava ImmutableGraph given a set of nodes (starting points) and a SuccessorsFunction. The graph would contain all the nodes reachable from any of the starting node and all the edges seen on the way thanks to the SuccessorsFunction. (E.g., given starting node {a} and successors a → b and b → c, the resulting graph should be {(a, b), (b, c)}.)

I see how I can obtain a Traverser to explore the reachable nodes in a certain order, given starting nodes and a SuccessorsFunction, but it does not meet my needs as I want to obtain a graph, not just the nodes.

It is not very hard to define an algorithm that does this, but it’s subtle enough to deserve trying to re-use an existing solution. I would be surprised if it didn’t exist already in the library. Does it? Or is this requirement not sensible?

I didn’t find this in the related wiki page.

Answer 1

Guava doesn't have this feature built in, so you'll need a custom solution that does some sort of graph traversal (like breadth-first traversal), like the following code snippet.

public static <N> ImmutableGraph<N> buildGraphWithBreadthFirstTraversal(
    Iterable<N> startingNodes, SuccessorsFunction<N> successorsFunction) {
  MutableGraph<N> result = GraphBuilder.directed().allowsSelfLoops(true).build();
  startingNodes.forEach(result::addNode);
  Queue<N> nodesRemaining = Queues.newArrayDeque(startingNodes);
  while (!nodesRemaining.isEmpty()) {
    N next = nodesRemaining.remove();
    for (N successor : successorsFunction.successors(next)) {
      if (!result.edges().contains(EndpointPair.ordered(next, successor))) {
        nodesRemaining.add(successor);
        result.putEdge(next, successor);
      }
    }
  }
  return ImmutableGraph.copyOf(result);
}

Here is a basic JUnit 5 unit test that confirms the code works when given a starting node and a successorsFunction that together form a cycle of 1 -> 2 -> 4 -> 1.

@Test
void succeedsOnTraversalWithCycle() {
  var result =
      MoreGraphs.buildGraphWithBreadthFirstTraversal(
          ImmutableList.of(1),
          node -> {
            int nextNode = node * 2;
            return nextNode <= 4 ? ImmutableList.of(nextNode) : ImmutableList.of(1);
          });

  assertThat(result)
      .isEqualTo(
          GraphBuilder.directed()
              .allowsSelfLoops(true)
              .immutable()
              .putEdge(1, 2)
              .putEdge(2, 4)
              .putEdge(4, 1)
              .build());
}