org.geotools.graph.traverse.standard
Class DepthFirstIterator

java.lang.Object
  org.geotools.graph.traverse.basic.AbstractGraphIterator
      org.geotools.graph.traverse.basic.SourceGraphIterator
          org.geotools.graph.traverse.standard.BreadthFirstIterator
              org.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)