Class Traverser<N>
 java.lang.Object

 com.google.common.graph.Traverser<N>

 Type Parameters:
N
 Node parameter type
@Beta @DoNotMock("Call forGraph or forTree, passing a lambda or a Graph with the desired edges (built with GraphBuilder)") public abstract class Traverser<N> extends Object
An object that can traverse the nodes that are reachable from a specified (set of) start node(s) using a specifiedSuccessorsFunction
.There are two entry points for creating a
Traverser
:forTree(SuccessorsFunction)
andforGraph(SuccessorsFunction)
. You should choose one based on your answers to the following questions: Is there only one path to any node that's reachable from any start node? (If so, the graph to be traversed is a tree or forest even if it is a subgraph of a graph which is neither.)
 Are the node objects' implementations of
equals()
/hashCode()
recursive?
If your answers are:
 (1) "no" and (2) "no", use
forGraph(SuccessorsFunction)
.  (1) "yes" and (2) "yes", use
forTree(SuccessorsFunction)
.  (1) "yes" and (2) "no", you can use either, but
forTree()
will be more efficient.  (1) "no" and (2) "yes", neither will work, but if you transform your node
objects into a nonrecursive form, you can use
forGraph()
.
 Since:
 23.1
 Author:
 Jens Nyman


Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description Iterable<N>
breadthFirst(Iterable<? extends N> startNodes)
Returns an unmodifiableIterable
over the nodes reachable from any of thestartNodes
, in the order of a breadthfirst traversal.Iterable<N>
breadthFirst(N startNode)
Returns an unmodifiableIterable
over the nodes reachable fromstartNode
, in the order of a breadthfirst traversal.Iterable<N>
depthFirstPostOrder(Iterable<? extends N> startNodes)
Returns an unmodifiableIterable
over the nodes reachable from any of thestartNodes
, in the order of a depthfirst postorder traversal.Iterable<N>
depthFirstPostOrder(N startNode)
Returns an unmodifiableIterable
over the nodes reachable fromstartNode
, in the order of a depthfirst postorder traversal.Iterable<N>
depthFirstPreOrder(Iterable<? extends N> startNodes)
Returns an unmodifiableIterable
over the nodes reachable from any of thestartNodes
, in the order of a depthfirst preorder traversal.Iterable<N>
depthFirstPreOrder(N startNode)
Returns an unmodifiableIterable
over the nodes reachable fromstartNode
, in the order of a depthfirst preorder traversal.static <N> Traverser<N>
forGraph(SuccessorsFunction<N> graph)
Creates a new traverser for the given generalgraph
.static <N> Traverser<N>
forTree(SuccessorsFunction<N> tree)
Creates a new traverser for a directed acyclic graph that has at most one path from the start node(s) to any node reachable from the start node(s), and has no paths from any start node to any other start node, such as a tree or forest.



Method Detail

forGraph
public static <N> Traverser<N> forGraph(SuccessorsFunction<N> graph)
Creates a new traverser for the given generalgraph
.Traversers created using this method are guaranteed to visit each node reachable from the start node(s) at most once.
If you know that no node in
graph
is reachable by more than one path from the start node(s), consider usingforTree(SuccessorsFunction)
instead.Performance notes
 Traversals require O(n) time (where n is the number of nodes reachable from
the start node), assuming that the node objects have O(1)
equals()
andhashCode()
implementations. (See the notes on element objects for more information.)  While traversing, the traverser will use O(n) space (where n is the number of nodes that have thus far been visited), plus O(H) space (where H is the number of nodes that have been seen but not yet visited, that is, the "horizon").
 Parameters:
graph
SuccessorsFunction
representing a general graph that may have cycles.
 Traversals require O(n) time (where n is the number of nodes reachable from
the start node), assuming that the node objects have O(1)

forTree
public static <N> Traverser<N> forTree(SuccessorsFunction<N> tree)
Creates a new traverser for a directed acyclic graph that has at most one path from the start node(s) to any node reachable from the start node(s), and has no paths from any start node to any other start node, such as a tree or forest.forTree()
is especially useful (versusforGraph()
) in cases where the data structure being traversed is, in addition to being a tree/forest, also defined recursively. This is because theforTree()
based implementations don't keep track of visited nodes, and therefore don't need to call `equals()` or `hashCode()` on the node objects; this saves both time and space versus traversing the same graph usingforGraph()
.Providing a graph to be traversed for which there is more than one path from the start node(s) to any node may lead to:
 Traversal not terminating (if the graph has cycles)
 Nodes being visited multiple times (if multiple paths exist from any start node to any node reachable from any start node)
Performance notes
 Traversals require O(n) time (where n is the number of nodes reachable from the start node).
 While traversing, the traverser will use O(H) space (where H is the number of nodes that have been seen but not yet visited, that is, the "horizon").
Examples (all edges are directed facing downwards)
The graph below would be valid input with start nodes of
a, f, c
. However, ifb
were also a start node, then there would be multiple paths to reache
andh
.a b c / \ / \  / \ / \  d e f g   h
.
The graph below would be a valid input with start nodes of
a, f
. However, ifb
were a start node, there would be multiple paths tof
.a b / \ / \ / \ / \ c d e \ / \ / f
Note on binary trees
This method can be used to traverse over a binary tree. Given methods
leftChild(node)
andrightChild(node)
, this method can be called asTraverser.forTree(node > ImmutableList.of(leftChild(node), rightChild(node)));
 Parameters:
tree
SuccessorsFunction
representing a directed acyclic graph that has at most one path between any two nodes

breadthFirst
public final Iterable<N> breadthFirst(N startNode)
Returns an unmodifiableIterable
over the nodes reachable fromstartNode
, 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 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.
 Throws:
IllegalArgumentException
 ifstartNode
is not an element of the graph

breadthFirst
public final Iterable<N> breadthFirst(Iterable<? extends N> startNodes)
Returns an unmodifiableIterable
over the nodes reachable from any of thestartNodes
, in the order of a breadthfirst traversal. This is equivalent to a breadthfirst traversal of a graph with an additional root node whose successors are the listedstartNodes
. Throws:
IllegalArgumentException
 if any ofstartNodes
is not an element of the graph Since:
 24.1
 See Also:
breadthFirst(Object)

depthFirstPreOrder
public final Iterable<N> depthFirstPreOrder(N startNode)
Returns an unmodifiableIterable
over the nodes reachable fromstartNode
, in the order of a depthfirst preorder traversal. "Preorder" 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.
 Throws:
IllegalArgumentException
 ifstartNode
is not an element of the graph

depthFirstPreOrder
public final Iterable<N> depthFirstPreOrder(Iterable<? extends N> startNodes)
Returns an unmodifiableIterable
over the nodes reachable from any of thestartNodes
, in the order of a depthfirst preorder traversal. This is equivalent to a depthfirst preorder traversal of a graph with an additional root node whose successors are the listedstartNodes
. Throws:
IllegalArgumentException
 if any ofstartNodes
is not an element of the graph Since:
 24.1
 See Also:
depthFirstPreOrder(Object)

depthFirstPostOrder
public final Iterable<N> depthFirstPostOrder(N startNode)
Returns an unmodifiableIterable
over the nodes reachable fromstartNode
, in the order of a depthfirst postorder traversal. "Postorder" 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.
 Throws:
IllegalArgumentException
 ifstartNode
is not an element of the graph

depthFirstPostOrder
public final Iterable<N> depthFirstPostOrder(Iterable<? extends N> startNodes)
Returns an unmodifiableIterable
over the nodes reachable from any of thestartNodes
, in the order of a depthfirst postorder traversal. This is equivalent to a depthfirst postorder traversal of a graph with an additional root node whose successors are the listedstartNodes
. Throws:
IllegalArgumentException
 if any ofstartNodes
is not an element of the graph Since:
 24.1
 See Also:
depthFirstPostOrder(Object)

