org.geotools.graph.traverse.standard
Class DepthFirstIterator

Object
  extended by AbstractGraphIterator
      extended by SourceGraphIterator
          extended by BreadthFirstIterator
              extended by 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 Summary
DepthFirstIterator()
           
 
Method Summary
protected  Queue buildQueue(Graph graph)
          Builds the node queue for the Iteration.
 
Methods inherited from class BreadthFirstIterator
cont, getQueue, init, killBranch, next, setSource
 
Methods inherited from class SourceGraphIterator
getSource
 
Methods inherited from class AbstractGraphIterator
getGraph, getTraversal, getWalker, setTraversal
 
Methods inherited from class Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

DepthFirstIterator

public DepthFirstIterator()
Method Detail

buildQueue

protected Queue 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)


Copyright © 1996-2014 Geotools. All Rights Reserved.