org.geotools.graph.traverse.standard
Class DepthFirstTopologicalIterator

Object
  extended by AbstractGraphIterator
      extended by BreadthFirstTopologicalIterator
          extended by DepthFirstTopologicalIterator
All Implemented Interfaces:
GraphIterator

public class DepthFirstTopologicalIterator
extends BreadthFirstTopologicalIterator

Iterates over the nodes of a graph in Depth First Topological Sort pattern. The following is an illustration of the iteration.


Initially all nodes of degree less than two are active (ready to be visited). As nodes are visited, a node can become active when all but one of its related nodes have been visited ( degree = counter + 1). When a node becomes active it is placed into the active node queue (queue of nodes to be visited). The Depth First Topological iterator places nodes into the queue in Last In First Out order (a Stack).

To determine when a node is to become active the iterator uses the counter associated with each node. If these counters are modified by an entity other then the iterator, the iteration may be affected in undefined ways.

Author:
Justin Deoliveira, Refractions Research Inc, jdeolive@refractions.net
Module:
modules/extension/graph (gt-graph.jar)

Constructor Summary
DepthFirstTopologicalIterator()
           
 
Method Summary
protected  Queue buildQueue(Graph graph)
          Builds the active node queue.
 
Methods inherited from class BreadthFirstTopologicalIterator
cont, init, killBranch, next
 
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

DepthFirstTopologicalIterator

public DepthFirstTopologicalIterator()
Method Detail

buildQueue

protected Queue buildQueue(Graph graph)
Builds the active node queue.

Overrides:
buildQueue in class BreadthFirstTopologicalIterator
Parameters:
graph - The Graph whose components are being iterated over.
Returns:
A last in first out queue (a stack)


Copyright © 1996-2009 Geotools. All Rights Reserved.