给定一个SuccessorsFunction和一组节点的构建图

Question

我想在给定一组节点（起点）和一个ImmutableGraph的情况下构建一个Guava ImmutableGraph。该图将包含从任何起始节点可到达的所有节点以及由于SuccessorsFunction而在途中看到的所有边缘。 （例如，给定起始节点SuccessorsFunction以及后续节点SuccessorsFunction和{a}，结果图形应为a → b。）

我知道如何获得b → c以给定起始节点和{(a, b), (b, c)}的特定顺序探索可到达的节点，但是由于我想获取图形，而不仅是节点，所以它不能满足我的需求。

定义执行此操作的算法不是很困难，但是它足够细微，值得尝试重用现有解决方案。如果库中还不存在它，我会感到惊讶。可以？还是这个要求不合理？

我没有在相关的Traverser页面中找到它。

Answer 1

Guava没有内置此功能，因此您需要一个自定义解决方案，该解决方案可以进行某种图形遍历（如广度优先遍历），如以下代码片段。

Traverser

[这是基本的JUnit 5单元测试，当给定起始节点和形成SuccessorsFunction周期的wiki时，可确认代码有效。

public static <N> ImmutableGraph<N> buildGraphWithBreadthFirstTraversal(
    Iterable<N> startingNodes, SuccessorsFunction<N> successorsFunction) {
  ImmutableGraph.Builder<N> builder = GraphBuilder.directed().immutable();
  Queue<N> nodesRemaining = Queues.newArrayDeque(startingNodes);
  Set<N> visited = Sets.newHashSet(startingNodes);
  while (!nodesRemaining.isEmpty()) {
    N next = nodesRemaining.remove();
    for (N successor : successorsFunction.successors(next)) {
      if (!visited.contains(successor)) {
        nodesRemaining.add(successor);
        visited.add(successor);
        builder.putEdge(next, successor);
      }
    }
  }
  return builder.build();
}