Method subgraphHasCycle

guava/src/com/google/common/graph/Graphs.java:101–140

Performs a traversal of the nodes reachable from {@code startNode}. If we ever reach a node we've already visited (following only outgoing edges and without reusing edges), we know there's a cycle in the graph.

(
      Graph<N> graph, Map<Object, NodeVisitState> visitedNodes, N startNode)

   * there's a cycle in the graph.
   */
  private static <N> boolean subgraphHasCycle(
      Graph<N> graph, Map<Object, NodeVisitState> visitedNodes, N startNode) {
    Deque<NodeAndRemainingSuccessors<N>> stack = new ArrayDeque<>();
    stack.addLast(new NodeAndRemainingSuccessors<>(startNode));

    while (!stack.isEmpty()) {
      // To peek at the top two items, we need to temporarily remove one.
      NodeAndRemainingSuccessors<N> top = stack.removeLast();
      NodeAndRemainingSuccessors<N> prev = stack.peekLast();
      stack.addLast(top);

      N node = top.node;
      N previousNode = prev == null ? null : prev.node;
      if (top.remainingSuccessors == null) {
        NodeVisitState state = visitedNodes.get(node);
        if (state == NodeVisitState.COMPLETE) {
          stack.removeLast();
          continue;
        }
        if (state == NodeVisitState.PENDING) {
          return true;
        }

        visitedNodes.put(node, NodeVisitState.PENDING);
        top.remainingSuccessors = new ArrayDeque<>(graph.successors(node));
      }

      if (!top.remainingSuccessors.isEmpty()) {
        N nextNode = top.remainingSuccessors.remove();
        if (canTraverseWithoutReusingEdge(graph, nextNode, previousNode)) {
          stack.addLast(new NodeAndRemainingSuccessors<>(nextNode));
          continue;
        }
      }

      stack.removeLast();
      visitedNodes.put(node, NodeVisitState.COMPLETE);
    }
    return false;
  }

  private static final class NodeAndRemainingSuccessors<N> {
    final N node;