Package com.google.common.graph

Class Traverser.TreeTraverser<N>

  • Enclosing class:
    Traverser<N>
    private static final class Traverser.TreeTraverser<N>
extends Traverser<N>

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method 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 checkThatNodeIsInTree​(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.

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • Method Detail

      • breadthFirst

        public java.lang.Iterable<N> breadthFirst​(N startNode)
        Description copied from class: Traverser
        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.

        Specified by:
        breadthFirst in class Traverser<N>

      • breadthFirst

        public java.lang.Iterable<N> breadthFirst​(java.lang.Iterable<? extends N> startNodes)
        Description copied from class: Traverser
        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.
        Specified by:
        breadthFirst in class Traverser<N>
        See Also:
        Traverser.breadthFirst(Object)

      • depthFirstPreOrder

        public java.lang.Iterable<N> depthFirstPreOrder​(N startNode)
        Description copied from class: Traverser
        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.

        Specified by:
        depthFirstPreOrder in class Traverser<N>

      • depthFirstPreOrder

        public java.lang.Iterable<N> depthFirstPreOrder​(java.lang.Iterable<? extends N> startNodes)
        Description copied from class: Traverser
        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.
        Specified by:
        depthFirstPreOrder in class Traverser<N>
        See Also:
        Traverser.depthFirstPreOrder(Object)

      • depthFirstPostOrder

        public java.lang.Iterable<N> depthFirstPostOrder​(N startNode)
        Description copied from class: Traverser
        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.

        Specified by:
        depthFirstPostOrder in class Traverser<N>

      • depthFirstPostOrder

        public java.lang.Iterable<N> depthFirstPostOrder​(java.lang.Iterable<? extends N> startNodes)
        Description copied from class: Traverser
        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.
        Specified by:
        depthFirstPostOrder in class Traverser<N>
        See Also:
        Traverser.depthFirstPostOrder(Object)

      • checkThatNodeIsInTree

        private void checkThatNodeIsInTree​(N startNode)