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 a <B>Depth First Search</B> pattern
25: * starting from a specified node. The following illustrates the iteration order.
26: * <BR>
27: * <BR>
28: * <IMG src="doc-files/dfs.gif"/><BR>
29: * <BR>
30: * The iteration operates by maintaning a node queue of <B>active</B> nodes.
31: * An <B>active</B> node is a node that will returned at a later stage of the i
32: * teration. The node queue for a Depth First iteration is implemented as a
33: * <B>Last In First Out</B> queue (a Stack).
34: * A node is placed in the the node queue if it has not been visited, and
35: * it is adjacent to a a node that has been visited. The node queue intially
36: * contains only the source node of the traversal.
37: *
38: * @author Justin Deoliveira, Refractions Research Inc, jdeolive@refractions.net
39: *
40: * @source $URL: http://svn.geotools.org/geotools/tags/2.4.1/modules/extension/graph/src/main/java/org/geotools/graph/traverse/standard/DepthFirstIterator.java $
41: */
42: public class DepthFirstIterator extends BreadthFirstIterator {
43:
44: /**
45: * Builds the node queue for the Iteration.
46: *
47: * @param graph The graph of the iteration.
48: *
49: * @return A Last In First Out queue (Stack)
50: */
51: protected Queue buildQueue(Graph graph) {
52: return (new Stack(graph.getNodes().size()));
53: }
54:
55: }
|