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 Summary

Constructors

Constructor and Description
DepthFirstIterator()

Method Summary

Modifier and Type	Method and Description
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)