01: /*
02: * GeoTools - OpenSource mapping toolkit
03: * http://geotools.org
04: * (C) 2002-2006, GeoTools Project Managment Committee (PMC)
05: * (C) 2002, Refractions Reserach Inc.
06: *
07: * This library is free software; you can redistribute it and/or
08: * modify it under the terms of the GNU Lesser General Public
09: * License as published by the Free Software Foundation;
10: * version 2.1 of the License.
11: *
12: * This library is distributed in the hope that it will be useful,
13: * but WITHOUT ANY WARRANTY; without even the implied warranty of
14: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15: * Lesser General Public License for more details.
16: */
17: package org.geotools.graph.traverse.standard;
18:
19: import org.geotools.graph.structure.Graph;
20: import org.geotools.graph.util.Queue;
21: import org.geotools.graph.util.Stack;
22:
23: /**
24: * Iterates over the nodes of a graph in <B>Depth First Topological Sort</B>
25: * pattern. The following is an illustration of the iteration.<BR>
26: * <IMG src="doc-files/depth_topo.gif"><BR>
27: * <BR>
28: * Initially all nodes of degree less than two are <B>active</B>
29: * (ready to be visited). As nodes are visited, a node can become active
30: * when all but one of its related nodes have been visited (
31: * degree = counter + 1). When a node becomes active it is placed into the
32: * <B>active node queue</B> (queue of nodes to be visited).
33: * The Depth First Topological iterator places
34: * nodes into the queue in <B>Last In First Out</B> order (a Stack).<BR>
35: * <BR>
36: * To determine when a node is to become active the iterator uses the counter
37: * associated with each node. If these counters are modified by an entity
38: * other then the iterator, the iteration may be affected in undefined ways.
39: *
40: * @author Justin Deoliveira, Refractions Research Inc, jdeolive@refractions.net
41: *
42: * @source $URL: http://svn.geotools.org/geotools/tags/2.4.1/modules/extension/graph/src/main/java/org/geotools/graph/traverse/standard/DepthFirstTopologicalIterator.java $
43: */
44: public class DepthFirstTopologicalIterator extends
45: BreadthFirstTopologicalIterator {
46:
47: /**
48: * Builds the active node queue.
49: *
50: * @param graph The Graph whose components are being iterated over.
51: *
52: * @return A last in first out queue (a stack)
53: */
54: protected Queue buildQueue(Graph graph) {
55: return (new Stack(graph.getNodes().size()));
56: }
57:
58: }
|