Построить граф с помощью функции Successors и набора узлов - PullRequest
Новая
       26

Построить граф с помощью функции Successors и набора узлов

1 голос
/ 05 октября 2019

Я бы хотел построить гуаву ImmutableGraph с учетом набора узлов (начальных точек) и SuccessorsFunction. График будет содержать все узлы, достижимые из любого начального узла, и все ребра, видимые на пути благодаря SuccessorsFunction. (Например, учитывая начальный узел {a} и преемники a → b и b → c, результирующий граф должен быть {(a, b), (b, c)}.)

Я вижу, как можно получить Traverser исследовать достижимые узлы в определенном порядке, учитывая начальные узлы и SuccessorsFunction, но это не отвечает моим потребностям, так как я хочу получить график, а не только узлы.

Это не оченьТрудно определить алгоритм, который делает это, но он достаточно тонок, чтобы заслуживать попытки повторно использовать существующее решение. Я был бы удивлен, если бы это не существовало уже в библиотеке. Является ли? Или это требование не имеет смысла?

Я не нашел его на соответствующей странице wiki .

1 Ответ

1 голос
/ 18 октября 2019

Guava не имеет этой встроенной функции, поэтому вам понадобится специальное решение, которое выполняет какой-то обход графика (например, обход в ширину), например, следующий фрагмент кода. 

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

Вот базовый модульный тест JUnit 5, который подтверждает, что код работает при задании начального узла и successorsFunction, которые вместе образуют цикл 1 -> 2 -> 4 -> 1. 

@Test
void succeedsOnTraversalWithCycle() {
  ImmutableGraph<Integer> graph =
      buildGraphWithBreadthFirstTraversal(
          ImmutableList.of(1),
          node -> node <= 2 ? ImmutableList.of(node * 2) : ImmutableList.of(1));

  assertThat(graph.nodes()).containsExactlyInAnyOrder(1, 2, 4);
  assertThat(graph.edges())
      .containsExactlyInAnyOrder(
          EndpointPair.ordered(1, 2),
          EndpointPair.ordered(2, 4));
}
...