Traverser (Guava: Google Core Libraries for Java 29.0-jre API)

java.lang.Object
- com.google.common.graph.Traverser<N>

Type Parameters:

N - Node parameter type
```
@Beta
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 specified 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:
1. 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.)
2. 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 non-recursive form, you can use forGraph().
Since:

23.1

Author:

Jens Nyman

Method Summary

All Methods Static Methods Instance Methods Abstract Methods Concrete Methods
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.

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Method Detail
  - forGraph
```
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 representing a general graph that may have cycles.
  - 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 (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 representing a directed acyclic graph that has at most one path between any two nodes
  - breadthFirst
```
public abstract 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.
    Throws:
    
    IllegalArgumentException - if startNode is not an element of the graph
  - breadthFirst
```
public 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. This is equivalent to a breadth-first traversal of a graph with an additional root node whose successors are the listed startNodes.
    
    Throws:
    
    IllegalArgumentException - if any of startNodes is not an element of the graph
    
    Since:
    
    24.1
    
    See Also:
    
    breadthFirst(Object)
  - depthFirstPreOrder
```
public 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. "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.
    Throws:
    
    IllegalArgumentException - if startNode is not an element of the graph
  - depthFirstPreOrder
```
public 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. This is equivalent to a depth-first pre-order traversal of a graph with an additional root node whose successors are the listed startNodes.
    
    Throws:
    
    IllegalArgumentException - if any of startNodes is not an element of the graph
    
    Since:
    
    24.1
    
    See Also:
    
    depthFirstPreOrder(Object)
  - depthFirstPostOrder
```
public 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. "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.
    Throws:
    
    IllegalArgumentException - if startNode is not an element of the graph
  - depthFirstPostOrder
```
public 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. This is equivalent to a depth-first post-order traversal of a graph with an additional root node whose successors are the listed startNodes.
    
    Throws:
    
    IllegalArgumentException - if any of startNodes is not an element of the graph
    
    Since:
    
    24.1
    
    See Also:
    
    depthFirstPostOrder(Object)

Class Traverser<N>

Method Summary

Methods inherited from class java.lang.Object

Method Detail

forGraph

forTree

breadthFirst

breadthFirst

depthFirstPreOrder

depthFirstPreOrder

depthFirstPostOrder

depthFirstPostOrder