Modifier and Type | Class and Description |
---|---|
private class |
Traverser.GraphTraverser.BreadthFirstIterator |
private class |
Traverser.GraphTraverser.DepthFirstIterator |
Modifier and Type | Field and Description |
---|---|
private SuccessorsFunction<N> |
graph |
Constructor and Description |
---|
GraphTraverser(SuccessorsFunction<N> graph) |
Modifier and Type | Method and Description |
---|---|
java.lang.Iterable<N> |
breadthFirst(java.lang.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. |
java.lang.Iterable<N> |
breadthFirst(N startNode)
Returns an unmodifiable
Iterable over the nodes reachable from startNode , in
the order of a breadth-first traversal. |
private void |
checkThatNodeIsInGraph(N startNode) |
java.lang.Iterable<N> |
depthFirstPostOrder(java.lang.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. |
java.lang.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. |
java.lang.Iterable<N> |
depthFirstPreOrder(java.lang.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. |
java.lang.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. |
private final SuccessorsFunction<N> graph
GraphTraverser(SuccessorsFunction<N> graph)
public java.lang.Iterable<N> breadthFirst(N startNode)
Traverser
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.
breadthFirst
in class Traverser<N>
public java.lang.Iterable<N> breadthFirst(java.lang.Iterable<? extends N> startNodes)
Traverser
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
.breadthFirst
in class Traverser<N>
Traverser.breadthFirst(Object)
public java.lang.Iterable<N> depthFirstPreOrder(N startNode)
Traverser
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.
depthFirstPreOrder
in class Traverser<N>
public java.lang.Iterable<N> depthFirstPreOrder(java.lang.Iterable<? extends N> startNodes)
Traverser
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
.depthFirstPreOrder
in class Traverser<N>
Traverser.depthFirstPreOrder(Object)
public java.lang.Iterable<N> depthFirstPostOrder(N startNode)
Traverser
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.
depthFirstPostOrder
in class Traverser<N>
public java.lang.Iterable<N> depthFirstPostOrder(java.lang.Iterable<? extends N> startNodes)
Traverser
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
.depthFirstPostOrder
in class Traverser<N>
Traverser.depthFirstPostOrder(Object)
private void checkThatNodeIsInGraph(N startNode)