Class Traverser.TreeTraverser<N>
- java.lang.Object
-
- com.google.common.graph.Traverser<N>
-
- com.google.common.graph.Traverser.TreeTraverser<N>
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private class
Traverser.TreeTraverser.BreadthFirstIterator
private class
Traverser.TreeTraverser.DepthFirstPostOrderIterator
private class
Traverser.TreeTraverser.DepthFirstPreOrderIterator
-
Field Summary
Fields Modifier and Type Field Description private SuccessorsFunction<N>
tree
-
Constructor Summary
Constructors Constructor Description TreeTraverser(SuccessorsFunction<N> tree)
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description java.lang.Iterable<N>
breadthFirst(java.lang.Iterable<? extends N> startNodes)
Returns an unmodifiableIterable
over the nodes reachable from any of thestartNodes
, in the order of a breadth-first traversal.java.lang.Iterable<N>
breadthFirst(N startNode)
Returns an unmodifiableIterable
over the nodes reachable fromstartNode
, in the order of a breadth-first traversal.private void
checkThatNodeIsInTree(N startNode)
java.lang.Iterable<N>
depthFirstPostOrder(java.lang.Iterable<? extends N> startNodes)
Returns an unmodifiableIterable
over the nodes reachable from any of thestartNodes
, in the order of a depth-first post-order traversal.java.lang.Iterable<N>
depthFirstPostOrder(N startNode)
Returns an unmodifiableIterable
over the nodes reachable fromstartNode
, in the order of a depth-first post-order traversal.java.lang.Iterable<N>
depthFirstPreOrder(java.lang.Iterable<? extends N> startNodes)
Returns an unmodifiableIterable
over the nodes reachable from any of thestartNodes
, in the order of a depth-first pre-order traversal.java.lang.Iterable<N>
depthFirstPreOrder(N startNode)
Returns an unmodifiableIterable
over the nodes reachable fromstartNode
, in the order of a depth-first pre-order traversal.
-
-
-
Field Detail
-
tree
private final SuccessorsFunction<N> tree
-
-
Constructor Detail
-
TreeTraverser
TreeTraverser(SuccessorsFunction<N> tree)
-
-
Method Detail
-
breadthFirst
public java.lang.Iterable<N> breadthFirst(N startNode)
Description copied from class:Traverser
Returns an unmodifiableIterable
over the nodes reachable fromstartNode
, in the order of a breadth-first traversal. That is, all the nodes of depth 0 are returned, then depth 1, then 2, and so on.Example: The following graph with
startNode
a
would return nodes in the orderabcdef
(assuming successors are returned in alphabetical order).b ---- a ---- d | | | | e ---- c ---- f
The behavior of this method is undefined if the nodes, or the topology of the graph, change while iteration is in progress.
The returned
Iterable
can be iterated over multiple times. Every iterator will compute its next element on the fly. It is thus possible to limit the traversal to a certain number of nodes as follows:Iterables.limit(Traverser.forGraph(graph).breadthFirst(node), maxNumberOfNodes);
See Wikipedia for more info.
- Specified by:
breadthFirst
in classTraverser<N>
-
breadthFirst
public java.lang.Iterable<N> breadthFirst(java.lang.Iterable<? extends N> startNodes)
Description copied from class:Traverser
Returns an unmodifiableIterable
over the nodes reachable from any of thestartNodes
, in the order of a breadth-first traversal. This is equivalent to a breadth-first traversal of a graph with an additional root node whose successors are the listedstartNodes
.- Specified by:
breadthFirst
in classTraverser<N>
- See Also:
Traverser.breadthFirst(Object)
-
depthFirstPreOrder
public java.lang.Iterable<N> depthFirstPreOrder(N startNode)
Description copied from class:Traverser
Returns an unmodifiableIterable
over the nodes reachable fromstartNode
, in the order of a depth-first pre-order traversal. "Pre-order" implies that nodes appear in theIterable
in the order in which they are first visited.Example: The following graph with
startNode
a
would return nodes in the orderabecfd
(assuming successors are returned in alphabetical order).b ---- a ---- d | | | | e ---- c ---- f
The behavior of this method is undefined if the nodes, or the topology of the graph, change while iteration is in progress.
The returned
Iterable
can be iterated over multiple times. Every iterator will compute its next element on the fly. It is thus possible to limit the traversal to a certain number of nodes as follows:Iterables.limit( Traverser.forGraph(graph).depthFirstPreOrder(node), maxNumberOfNodes);
See Wikipedia for more info.
- Specified by:
depthFirstPreOrder
in classTraverser<N>
-
depthFirstPreOrder
public java.lang.Iterable<N> depthFirstPreOrder(java.lang.Iterable<? extends N> startNodes)
Description copied from class:Traverser
Returns an unmodifiableIterable
over the nodes reachable from any of thestartNodes
, in the order of a depth-first pre-order traversal. This is equivalent to a depth-first pre-order traversal of a graph with an additional root node whose successors are the listedstartNodes
.- Specified by:
depthFirstPreOrder
in classTraverser<N>
- See Also:
Traverser.depthFirstPreOrder(Object)
-
depthFirstPostOrder
public java.lang.Iterable<N> depthFirstPostOrder(N startNode)
Description copied from class:Traverser
Returns an unmodifiableIterable
over the nodes reachable fromstartNode
, in the order of a depth-first post-order traversal. "Post-order" implies that nodes appear in theIterable
in the order in which they are visited for the last time.Example: The following graph with
startNode
a
would return nodes in the orderfcebda
(assuming successors are returned in alphabetical order).b ---- a ---- d | | | | e ---- c ---- f
The behavior of this method is undefined if the nodes, or the topology of the graph, change while iteration is in progress.
The returned
Iterable
can be iterated over multiple times. Every iterator will compute its next element on the fly. It is thus possible to limit the traversal to a certain number of nodes as follows:Iterables.limit( Traverser.forGraph(graph).depthFirstPostOrder(node), maxNumberOfNodes);
See Wikipedia for more info.
- Specified by:
depthFirstPostOrder
in classTraverser<N>
-
depthFirstPostOrder
public java.lang.Iterable<N> depthFirstPostOrder(java.lang.Iterable<? extends N> startNodes)
Description copied from class:Traverser
Returns an unmodifiableIterable
over the nodes reachable from any of thestartNodes
, in the order of a depth-first post-order traversal. This is equivalent to a depth-first post-order traversal of a graph with an additional root node whose successors are the listedstartNodes
.- Specified by:
depthFirstPostOrder
in classTraverser<N>
- See Also:
Traverser.depthFirstPostOrder(Object)
-
checkThatNodeIsInTree
private void checkThatNodeIsInTree(N startNode)
-
-