Class Traverser.Traversal<N>

java.lang.Object
com.google.common.graph.Traverser.Traversal<N>
Enclosing class:
Traverser<N>

private abstract static class Traverser.Traversal<N> extends Object
Abstracts away the difference between traversing a graph vs. a tree. For a tree, we just take the next element from the next non-empty iterator; for graph, we need to loop through the next non-empty iterator to find first unvisited node.
  • Field Details

  • Constructor Details

  • Method Details

    • inGraph

      static <N> Traverser.Traversal<N> inGraph(SuccessorsFunction<N> graph)
    • inTree

      static <N> Traverser.Traversal<N> inTree(SuccessorsFunction<N> tree)
    • breadthFirst

      final Iterator<N> breadthFirst(Iterator<? extends N> startNodes)
    • preOrder

      final Iterator<N> preOrder(Iterator<? extends N> startNodes)
    • topDown

      private Iterator<N> topDown(Iterator<? extends N> startNodes, Traverser.InsertionOrder order)
      In top-down traversal, an ancestor node is always traversed before any of its descendant nodes. The traversal order among descendant nodes (particularly aunts and nieces) are determined by the InsertionOrder parameter: nieces are placed at the FRONT before aunts for pre-order; while in BFS they are placed at the BACK after aunts.
    • postOrder

      final Iterator<N> postOrder(Iterator<? extends N> startNodes)
    • visitNext

      @CheckForNull abstract N visitNext(Deque<Iterator<? extends N>> horizon)
      Visits the next node from the top iterator of horizon and returns the visited node. Null is returned to indicate reaching the end of the top iterator.

      For example, if horizon is [[a, b], [c, d], [e]], visitNext() will return [a, b, null, c, d, null, e, null] sequentially, encoding the topological structure. (Note, however, that the callers of visitNext() often insert additional iterators into horizon between calls to visitNext(). This causes them to receive additional values interleaved with those shown above.)