T
 Node parameter typepublic final class Traverser<T>
extends java.lang.Object
Modifier and Type  Method and Description 

Stream<T> 
breadthFirst(T startNode)
Returns an unmodifiable
Iterable over the nodes reachable from startNode , in
the order of a breadthfirst traversal. 
Stream<T> 
depthFirstPostOrder(T startNode)
Returns an unmodifiable
Iterable over the nodes reachable from startNode , in
the order of a depthfirst postorder traversal. 
Stream<T> 
depthFirstPreOrder(T startNode)
Returns an unmodifiable
Iterable over the nodes reachable from startNode , in
the order of a depthfirst preorder traversal. 
static <T> Traverser<T> 
forGraph(Function<T,java.lang.Iterable<? extends T>> graph)
Creates a new traverser for the given general
graph . 
static <T> Traverser<T> 
forTree(Function<T,java.lang.Iterable<? extends T>> tree)
Creates a new traverser for a directed acyclic graph that has at most one path from the start
node to any node reachable from the start node, such as a tree.

public static final Traverser<java.io.File> FILES
public static <T> Traverser<T> forTree(Function<T,java.lang.Iterable<? extends T>> tree)
Providing graphs that don't conform to the above description may lead to:
#forGraph(SuccessorsFunction)
instead.
Performance notes
Examples
This is a valid input graph (all edges are directed facing downwards):
a b c
/ \ / \ 
/ \ / \ 
d e f g


h
This is not a valid input graph (all edges are directed facing downwards):
a b
/ \ / \
/ \ / \
c d e
\ /
\ /
f
because there are two paths from b
to f
(b>d>f
and b>e>f
).
Note on binary trees
This method can be used to traverse over a binary tree. Given methods leftChild(node)
and rightChild(node)
, this method can be called as
Traverser.forTree(node > ImmutableList.of(leftChild(node), rightChild(node)));
tree
 SuccessorsFunction
representing a directed acyclic graph that has at most
one path between any two nodespublic static <T> Traverser<T> forGraph(Function<T,java.lang.Iterable<? extends T>> graph)
graph
.
If graph
is known to be treeshaped, consider using #forTree(SuccessorsFunction)
instead.
Performance notes
equals()
and
hashCode()
implementations.
graph
 SuccessorsFunction
representing a general graph that may have cycles.public Stream<T> breadthFirst(T startNode)
Iterable
over the nodes reachable from startNode
, in
the order of a breadthfirst 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 order abcdef
(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.
java.lang.IllegalArgumentException
 if startNode
is not an element of the graphpublic Stream<T> depthFirstPreOrder(T startNode)
Iterable
over the nodes reachable from startNode
, in
the order of a depthfirst preorder traversal. "Preorder" implies that nodes appear in the
Iterable
in the order in which they are first visited.
Example: The following graph with startNode
a
would return nodes in
the order abecfd
(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.
java.lang.IllegalArgumentException
 if startNode
is not an element of the graphpublic Stream<T> depthFirstPostOrder(T startNode)
Iterable
over the nodes reachable from startNode
, in
the order of a depthfirst postorder traversal. "Postorder" implies that nodes appear in the
Iterable
in the order in which they are visited for the last time.
Example: The following graph with startNode
a
would return nodes in
the order fcebda
(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.
java.lang.IllegalArgumentException
 if startNode
is not an element of the graph