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 java.util.Iterator;
20:
21: import org.geotools.graph.structure.DirectedGraphable;
22: import org.geotools.graph.structure.DirectedNode;
23: import org.geotools.graph.structure.Graph;
24: import org.geotools.graph.structure.GraphVisitor;
25: import org.geotools.graph.structure.Graphable;
26: import org.geotools.graph.traverse.GraphTraversal;
27: import org.geotools.graph.traverse.basic.AbstractGraphIterator;
28: import org.geotools.graph.util.FIFOQueue;
29: import org.geotools.graph.util.Queue;
30:
31: /**
32: * @source $URL: http://svn.geotools.org/geotools/tags/2.4.1/modules/extension/graph/src/main/java/org/geotools/graph/traverse/standard/DirectedBreadthFirstTopologicalIterator.java $
33: */
34: public class DirectedBreadthFirstTopologicalIterator extends
35: AbstractGraphIterator {
36:
37: private Queue m_queue;
38:
39: public void init(Graph graph, GraphTraversal traversal) {
40: //create queue
41: m_queue = buildQueue(graph);
42:
43: //initialize nodes
44: graph.visitNodes(new GraphVisitor() {
45: public int visit(Graphable component) {
46: DirectedNode node = (DirectedNode) component;
47:
48: node.setVisited(false);
49: node.setCount(0);
50:
51: if (node.getInDegree() == 0)
52: m_queue.enq(node);
53:
54: return (0);
55: }
56: });
57: }
58:
59: public Graphable next(GraphTraversal traversal) {
60: return (!m_queue.isEmpty() ? (Graphable) m_queue.deq() : null);
61: }
62:
63: public void cont(Graphable current, GraphTraversal traversal) {
64: //increment the count of all adjacent nodes by one
65: // if the result count equal to the degree, place it into the queue
66: DirectedGraphable directed = (DirectedGraphable) current;
67: for (Iterator itr = directed.getOutRelated(); itr.hasNext();) {
68: DirectedNode related = (DirectedNode) itr.next();
69: if (!traversal.isVisited(related)) {
70: related.setCount(related.getCount() + 1);
71: if (related.getInDegree() == related.getCount())
72: m_queue.enq(related);
73: }
74: }
75: }
76:
77: public void killBranch(Graphable current, GraphTraversal traversal) {
78: //do nothing
79: }
80:
81: protected Queue buildQueue(Graph graph) {
82: return (new FIFOQueue(graph.getNodes().size()));
83: }
84: }
|