给定 SuccessorsFunction 和一组节点构建图

Question

我想构建一个 Guava ImmutableGraph given a set of nodes (starting points) and a SuccessorsFunction。由于SuccessorsFunction，该图将包含从任何起始节点可到达的所有节点以及在途中看到的所有边。（例如，给定起始节点 {a} 和后继节点 a → b 和 b → c，结果图应为 {(a, b), (b, c)}。）

我知道如何获得一个 Traverser 来按特定顺序探索可到达的节点，给定起始节点和一个 SuccessorsFunction，但它不符合我想要获得的需求图表，而不仅仅是节点。

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

我在相关 wiki 页面中没有找到这个。

Answer 1

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

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);
}

这是一个基本的 JUnit 5 单元测试，它确认代码在给定起始节点和 successorsFunction 时有效，它们一起形成 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());
}

给定 SuccessorsFunction 和一组节点构建图

Build Graph given a SuccessorsFunction and a set of nodes

graph-theory

guava