org.geotools.graph.traverse.standard
Class DepthFirstTopologicalIterator
Object
AbstractGraphIterator
BreadthFirstTopologicalIterator
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)
Methods inherited from class Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
DepthFirstTopologicalIterator
public DepthFirstTopologicalIterator()
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.