N
- Node parameter type@Beta public abstract class Traverser<N> extends Object
SuccessorsFunction
.
There are two entry points for creating a Traverser
: forTree(SuccessorsFunction)
and forGraph(SuccessorsFunction)
. You should choose one
based on your answers to the following questions:
equals()
/hashCode()
recursive?
If your answers are:
forGraph(SuccessorsFunction)
.
forTree(SuccessorsFunction)
.
forTree()
will be more efficient.
forGraph()
.
Modifier and Type | Method and Description |
---|---|
abstract Iterable<N> |
breadthFirst(Iterable<? extends N> startNodes)
Returns an unmodifiable
Iterable over the nodes reachable from any of the startNodes , in the order of a breadth-first traversal. |
abstract Iterable<N> |
breadthFirst(N startNode)
Returns an unmodifiable
Iterable over the nodes reachable from startNode , in
the order of a breadth-first traversal. |
abstract Iterable<N> |
depthFirstPostOrder(Iterable<? extends N> startNodes)
Returns an unmodifiable
Iterable over the nodes reachable from any of the startNodes , in the order of a depth-first post-order traversal. |
abstract Iterable<N> |
depthFirstPostOrder(N startNode)
Returns an unmodifiable
Iterable over the nodes reachable from startNode , in
the order of a depth-first post-order traversal. |
abstract Iterable<N> |
depthFirstPreOrder(Iterable<? extends N> startNodes)
Returns an unmodifiable
Iterable over the nodes reachable from any of the startNodes , in the order of a depth-first pre-order traversal. |
abstract Iterable<N> |
depthFirstPreOrder(N startNode)
Returns an unmodifiable
Iterable over the nodes reachable from startNode , in
the order of a depth-first pre-order traversal. |
static <N> Traverser<N> |
forGraph(SuccessorsFunction<N> graph)
Creates a new traverser for the given general
graph . |
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.
|
public static <N> Traverser<N> forGraph(SuccessorsFunction<N> graph)
graph
.
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 using forTree(SuccessorsFunction)
instead.
Performance notes
equals()
and
hashCode()
implementations. (See the
notes on element objects for more information.)
graph
- SuccessorsFunction
representing a general graph that may have cycles.public static <N> Traverser<N> forTree(SuccessorsFunction<N> tree)
forTree()
is especially useful (versus forGraph()
) in cases where the data
structure being traversed is, in addition to being a tree/forest, also defined recursively.
This is because the forTree()
-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 using forGraph()
.
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:
Performance notes
Examples (all edges are directed facing downwards)
The graph below would be valid input with start nodes of a, f, c
. However, if b
were also a start node, then there would be multiple paths to reach e
and
h
.
a b c
/ \ / \ |
/ \ / \ |
d e f g
|
|
h
.
The graph below would be a valid input with start nodes of a, f
. However, if b
were a start node, there would be multiple paths to f
.
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)
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 abstract Iterable<N> breadthFirst(N startNode)
Iterable
over the nodes reachable from startNode
, 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 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.
IllegalArgumentException
- if startNode
is not an element of the graphpublic abstract Iterable<N> breadthFirst(Iterable<? extends N> startNodes)
Iterable
over the nodes reachable from any of the startNodes
, 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 listed startNodes
.IllegalArgumentException
- if any of startNodes
is not an element of the graphbreadthFirst(Object)
public abstract Iterable<N> depthFirstPreOrder(N startNode)
Iterable
over the nodes reachable from startNode
, in
the order of a depth-first pre-order traversal. "Pre-order" 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.
IllegalArgumentException
- if startNode
is not an element of the graphpublic abstract Iterable<N> depthFirstPreOrder(Iterable<? extends N> startNodes)
Iterable
over the nodes reachable from any of the startNodes
, 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 listed startNodes
.IllegalArgumentException
- if any of startNodes
is not an element of the graphdepthFirstPreOrder(Object)
public abstract Iterable<N> depthFirstPostOrder(N startNode)
Iterable
over the nodes reachable from startNode
, in
the order of a depth-first post-order traversal. "Post-order" 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.
IllegalArgumentException
- if startNode
is not an element of the graphpublic abstract Iterable<N> depthFirstPostOrder(Iterable<? extends N> startNodes)
Iterable
over the nodes reachable from any of the startNodes
, 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 listed startNodes
.IllegalArgumentException
- if any of startNodes
is not an element of the graphdepthFirstPostOrder(Object)
Copyright © 2010–2019. All rights reserved.