Package org.geotools.graph.traverse.standard

Class DepthFirstIterator

Object
AbstractGraphIterator
SourceGraphIterator
BreadthFirstIterator
DepthFirstIterator
All Implemented Interfaces:
GraphIterator
Direct Known Subclasses:
DirectedDepthFirstIterator
public class DepthFirstIterator extends BreadthFirstIterator
Iterates over the nodes of a graph in a Depth First Search pattern starting from a specified node. The following illustrates the iteration order.



The iteration operates by maintaning a node queue of active nodes. An active node is a node that will returned at a later stage of the i teration. The node queue for a Depth First iteration is implemented as a Last In First Out queue (a Stack). A node is placed in the the node queue if it has not been visited, and it is adjacent to a a node that has been visited. The node queue intially contains only the source node of the traversal.
Author:
Justin Deoliveira, Refractions Research Inc, jdeolive@refractions.net

  • Constructor Details

    • DepthFirstIterator

      public DepthFirstIterator()

  • Method Details

    • buildQueue

      protected Queue<Graphable> buildQueue(Graph graph)
      Builds the node queue for the Iteration.
      Overrides:
      buildQueue in class BreadthFirstIterator
      Parameters:
      graph - The graph of the iteration.
      Returns:
      A Last In First Out queue (Stack)