Package com.google.common.graph
Class Traverser.Traversal<N>
- java.lang.Object
-
- com.google.common.graph.Traverser.Traversal<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.
-
-
Field Summary
Fields Modifier and Type Field Description (package private) SuccessorsFunction<N>
successorFunction
-
Constructor Summary
Constructors Constructor Description Traversal(SuccessorsFunction<N> successorFunction)
-
Method Summary
All Methods Static Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description (package private) java.util.Iterator<N>
breadthFirst(java.util.Iterator<? extends N> startNodes)
(package private) static <N> Traverser.Traversal<N>
inGraph(SuccessorsFunction<N> graph)
(package private) static <N> Traverser.Traversal<N>
inTree(SuccessorsFunction<N> tree)
(package private) java.util.Iterator<N>
postOrder(java.util.Iterator<? extends N> startNodes)
(package private) java.util.Iterator<N>
preOrder(java.util.Iterator<? extends N> startNodes)
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.(package private) abstract N
visitNext(java.util.Deque<java.util.Iterator<? extends N>> horizon)
Visits the next node from the top iterator ofhorizon
and returns the visited node.
-
-
-
Field Detail
-
successorFunction
final SuccessorsFunction<N> successorFunction
-
-
Constructor Detail
-
Traversal
Traversal(SuccessorsFunction<N> successorFunction)
-
-
Method Detail
-
inGraph
static <N> Traverser.Traversal<N> inGraph(SuccessorsFunction<N> graph)
-
inTree
static <N> Traverser.Traversal<N> inTree(SuccessorsFunction<N> tree)
-
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 theInsertionOrder
parameter: nieces are placed at the FRONT before aunts for pre-order; while in BFS they are placed at the BACK after aunts.
-
visitNext
abstract N visitNext(java.util.Deque<java.util.Iterator<? extends N>> horizon)
Visits the next node from the top iterator ofhorizon
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 ofvisitNext()
often insert additional iterators intohorizon
between calls tovisitNext()
. This causes them to receive additional values interleaved with those shown above.)
-
-