Class Traverser.Traversal<N>

  • Enclosing class:
    Traverser<N>

    private abstract static class Traverser.Traversal<N>
    extends java.lang.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.
    • Method Detail

      • breadthFirst

        final java.util.Iterator<N> breadthFirst​(java.util.Iterator<? extends N> startNodes)
      • preOrder

        final java.util.Iterator<N> preOrder​(java.util.Iterator<? extends N> startNodes)
      • topDown

        private java.util.Iterator<N> topDown​(java.util.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 java.util.Iterator<N> postOrder​(java.util.Iterator<? extends N> startNodes)
      • visitNext

        @CheckForNull
        abstract N visitNext​(java.util.Deque<java.util.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.)