org.geotools.graph.traverse.standard
Class DepthFirstIterator

java.lang.Object
  extended byorg.geotools.graph.traverse.basic.AbstractGraphIterator
      extended byorg.geotools.graph.traverse.basic.SourceGraphIterator
          extended byorg.geotools.graph.traverse.standard.BreadthFirstIterator
              extended byorg.geotools.graph.traverse.standard.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 org.geotools.graph.traverse.standard.BreadthFirstIterator
cont, getQueue, init, killBranch, next, setSource
 
Methods inherited from class org.geotools.graph.traverse.basic.SourceGraphIterator
getSource
 
Methods inherited from class org.geotools.graph.traverse.basic.AbstractGraphIterator
getGraph, getTraversal, getWalker, setTraversal
 
Methods inherited from class java.lang.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 © GeoTools. All Rights Reserved.