Modifier and Type	Class and Description
private static enum	Traverser.InsertionOrder Poor man's method reference for `Deque::addFirst` and `Deque::addLast`.
private abstract static class	Traverser.Traversal<N> Abstracts away the difference between traversing a graph vs. a tree.

Modifier and Type	Field and Description
private final SuccessorsFunction<N>	successorFunction

Access	Constructor and Description
private	Traverser(SuccessorsFunction<N> successorFunction)

Method Summary

Modifier and Type	Method and Description
public final Iterable<N>	breadthFirst(N startNode) Returns an unmodifiable `Iterable` over the nodes reachable from `startNode`, in the order of a breadth-first traversal.
public final 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.
public final 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.
public final 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.
public final 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.
public final 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.
public static <N> Traverser<N>	forGraph(SuccessorsFunction<N> `SuccessorsFunction` representing a general graph that may have cycles. graph) Creates a new traverser for the given general `graph`.
public static <N> Traverser<N>	forTree(SuccessorsFunction<N> `SuccessorsFunction` representing a directed acyclic graph that has at most one path between any two nodes 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.
pack-priv abstract Traverser.Traversal<N>	newTraversal()
private ImmutableSet<N>	validate(Iterable<? extends N> startNodes)

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

successorFunction	back to summary
private final SuccessorsFunction<N> successorFunction

Constructor Detail

Traverser	back to summary
private Traverser(SuccessorsFunction<N> successorFunction)

Method Detail

breadthFirst back to summary

breadthFirst	back to summary
public final Iterable<N> breadthFirst(N startNode) Returns an unmodifiable `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. Exceptions IllegalArgumentException: if `startNode` is not an element of the graph

public final Iterable<N> breadthFirst(N startNode)

Returns an unmodifiable 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.

Exceptions

IllegalArgumentException:: if startNode is not an element of the graph

breadthFirst back to summary

breadthFirst	back to summary
public final 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. This is equivalent to a breadth-first traversal of a graph with an additional root node whose successors are the listed `startNodes`. Exceptions IllegalArgumentException: if any of `startNodes` is not an element of the graph Since 24.1 See Also `breadthFirst(Object)`

public final 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. This is equivalent to a breadth-first traversal of a graph with an additional root node whose successors are the listed startNodes.

Exceptions

IllegalArgumentException:: if any of startNodes is not an element of the graph

Since

24.1

See Also

breadthFirst(Object)

depthFirstPostOrder back to summary

depthFirstPostOrder	back to summary
public final 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. "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. Exceptions IllegalArgumentException: if `startNode` is not an element of the graph

public final 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. "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.

Iterables.limit(
    Traverser.forGraph(graph).depthFirstPostOrder(node), maxNumberOfNodes);

See Wikipedia for more info.

Exceptions

IllegalArgumentException:: if startNode is not an element of the graph

depthFirstPostOrder back to summary

depthFirstPostOrder	back to summary
public final 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. This is equivalent to a depth-first post-order traversal of a graph with an additional root node whose successors are the listed `startNodes`. Exceptions IllegalArgumentException: if any of `startNodes` is not an element of the graph Since 24.1 See Also `depthFirstPostOrder(Object)`

public final 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. This is equivalent to a depth-first post-order traversal of a graph with an additional root node whose successors are the listed startNodes.

Exceptions

IllegalArgumentException:: if any of startNodes is not an element of the graph

Since

24.1

See Also

depthFirstPostOrder(Object)

depthFirstPreOrder back to summary

depthFirstPreOrder	back to summary
public final 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. "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. Exceptions IllegalArgumentException: if `startNode` is not an element of the graph

public final 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. "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.

Iterables.limit(
    Traverser.forGraph(graph).depthFirstPreOrder(node), maxNumberOfNodes);

See Wikipedia for more info.

Exceptions

IllegalArgumentException:: if startNode is not an element of the graph

depthFirstPreOrder back to summary

depthFirstPreOrder	back to summary
public final 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. This is equivalent to a depth-first pre-order traversal of a graph with an additional root node whose successors are the listed `startNodes`. Exceptions IllegalArgumentException: if any of `startNodes` is not an element of the graph Since 24.1 See Also `depthFirstPreOrder(Object)`

public final 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. This is equivalent to a depth-first pre-order traversal of a graph with an additional root node whose successors are the listed startNodes.

Exceptions

IllegalArgumentException:: if any of startNodes is not an element of the graph

Since

24.1

See Also

depthFirstPreOrder(Object)

forGraph back to summary

forGraph	back to summary
public static <N> Traverser<N> forGraph(SuccessorsFunction<N> graph) Creates a new traverser for the given general `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 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()` and `hashCode()` 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<N> `SuccessorsFunction` representing a general graph that may have cycles.

public static <N> Traverser<N> forGraph(SuccessorsFunction<N> graph)

Creates a new traverser for the given general 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

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() and hashCode() 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<N>: SuccessorsFunction representing a general graph that may have cycles.

forTree back to summary

forTree	back to summary
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 (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: 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, 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)));` Parameters tree:SuccessorsFunction<N> `SuccessorsFunction` representing a directed acyclic graph that has at most one path between any two nodes

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 (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:

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, 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)));

Parameters

tree:SuccessorsFunction<N>: SuccessorsFunction representing a directed acyclic graph that has at most one path between any two nodes

newTraversal	back to summary
pack-priv abstract Traverser.Traversal<N> newTraversal()

validate	back to summary
private ImmutableSet<N> validate(Iterable<? extends N> startNodes) Annotations @SuppressWarnings:CheckReturnValue

com.google.common.graph back to summary

private sealed Enum Traverser.InsertionOrder

Class Inheritance

extends Enum<Traverser.InsertionOrder>

java.lang.Object
java.lang.Enum
com.google.common.graph.Traverser.InsertionOrder

Poor man's method reference for Deque::addFirst and Deque::addLast.

Field Summary

Modifier and Type	Field and Description
public static final Traverser.InsertionOrder	BACK
public static final Traverser.InsertionOrder	FRONT

Constructor Summary

Access	Constructor and Description
private	InsertionOrder()

Method Summary

Modifier and Type	Method and Description
pack-priv abstract <T> void	insertInto(Deque<T> deque, T value)
public static Traverser.InsertionOrder	valueOf(String name)
public static Traverser.InsertionOrder[]	values()

Inherited from java.lang.Enum:: clone compareTo describeConstable equals finalize getDeclaringClass hashCode name ordinal toString valueOf

Field Detail

BACK	back to summary
public static final Traverser.InsertionOrder BACK

FRONT	back to summary
public static final Traverser.InsertionOrder FRONT

Constructor Detail

InsertionOrder	back to summary
private InsertionOrder()

Method Detail

insertInto	back to summary
pack-priv abstract <T> void insertInto(Deque<T> deque, T value)

valueOf	back to summary
public static Traverser.InsertionOrder valueOf(String name)

values	back to summary
public static Traverser.InsertionOrder[] values()

com.google.common.graph back to summary

private abstract Class Traverser.Traversal<N>

Class Inheritance

extends Object

java.lang.Object
com.google.common.graph.Traverser.Traversal

Abstracts away the difference between traversing a graph vs. a tree. For a tree, we just take the next element from the next non-empty iterator; for graph, we need to loop through the next non-empty iterator to find first unvisited node.

Field Summary

Modifier and Type	Field and Description
pack-priv final SuccessorsFunction<N>	successorFunction

Constructor Summary

Access	Constructor and Description
pack-priv	Traversal(SuccessorsFunction<N> successorFunction)

Method Summary

Modifier and Type	Method and Description
pack-priv final Iterator<N>	breadthFirst(Iterator<? extends N> startNodes)
pack-priv static <N> Traverser.Traversal<N>	inGraph(SuccessorsFunction<N> graph)
pack-priv static <N> Traverser.Traversal<N>	inTree(SuccessorsFunction<N> tree)
pack-priv final Iterator<N>	postOrder(Iterator<? extends N> startNodes)
pack-priv final Iterator<N>	preOrder(Iterator<? extends N> startNodes)
private Iterator<N>	topDown(Iterator<? extends N> startNodes, Traverser.InsertionOrder order) In top-down traversal, an ancestor node is always traversed before any of its descendant nodes.
pack-priv abstract N	visitNext(Deque<Iterator<? extends N>> horizon) Visits the next node from the top iterator of `horizon` and returns the visited node.

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

successorFunction	back to summary
pack-priv final SuccessorsFunction<N> successorFunction

Constructor Detail

Traversal	back to summary
pack-priv Traversal(SuccessorsFunction<N> successorFunction)

Method Detail

breadthFirst	back to summary
pack-priv final Iterator<N> breadthFirst(Iterator<? extends N> startNodes)

inGraph	back to summary
pack-priv static <N> Traverser.Traversal<N> inGraph(SuccessorsFunction<N> graph)

inTree	back to summary
pack-priv static <N> Traverser.Traversal<N> inTree(SuccessorsFunction<N> tree)

postOrder	back to summary
pack-priv final Iterator<N> postOrder(Iterator<? extends N> startNodes)

preOrder	back to summary
pack-priv final Iterator<N> preOrder(Iterator<? extends N> startNodes)

topDown back to summary

topDown	back to summary
private Iterator<N> topDown(Iterator<? extends N> startNodes, Traverser.InsertionOrder order) In top-down traversal, an ancestor node is always traversed before any of its descendant nodes. The traversal order among descendant nodes (particularly aunts and nieces) are determined by the `InsertionOrder` parameter: nieces are placed at the FRONT before aunts for pre-order; while in BFS they are placed at the BACK after aunts.

private Iterator<N> topDown(Iterator<? extends N> startNodes, Traverser.InsertionOrder order)

In top-down traversal, an ancestor node is always traversed before any of its descendant nodes. The traversal order among descendant nodes (particularly aunts and nieces) are determined by the InsertionOrder parameter: nieces are placed at the FRONT before aunts for pre-order; while in BFS they are placed at the BACK after aunts.

visitNext back to summary

visitNext	back to summary
pack-priv abstract N visitNext(Deque<Iterator<? extends N>> horizon) Visits the next node from the top iterator of `horizon` and returns the visited node. Null is returned to indicate reaching the end of the top iterator. For example, if horizon is `[[a, b], [c, d], [e]]`, `visitNext()` will return `[a, b, null, c, d, null, e, null]` sequentially, encoding the topological structure. (Note, however, that the callers of `visitNext()` often insert additional iterators into `horizon` between calls to `visitNext()`. This causes them to receive additional values interleaved with those shown above.) Annotations @CheckForNull

pack-priv abstract N visitNext(Deque<Iterator<? extends N>> horizon)

Visits the next node from the top iterator of horizon and returns the visited node. Null is returned to indicate reaching the end of the top iterator.

For example, if horizon is [[a, b], [c, d], [e]], visitNext() will return [a, b, null, c, d, null, e, null] sequentially, encoding the topological structure. (Note, however, that the callers of visitNext() often insert additional iterators into horizon between calls to visitNext(). This causes them to receive additional values interleaved with those shown above.)

Annotations

@CheckForNull

public abstract Class Traverser<N>

Nested and Inner Type Summary

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail

private sealed Enum Traverser.InsertionOrder

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail

private abstract Class Traverser.Traversal<N>

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail