001: /*
002: * GeoTools - OpenSource mapping toolkit
003: * http://geotools.org
004: * (C) 2002-2006, GeoTools Project Managment Committee (PMC)
005: * (C) 2002, Refractions Reserach Inc.
006: *
007: * This library is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU Lesser General Public
009: * License as published by the Free Software Foundation;
010: * version 2.1 of the License.
011: *
012: * This library is distributed in the hope that it will be useful,
013: * but WITHOUT ANY WARRANTY; without even the implied warranty of
014: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
015: * Lesser General Public License for more details.
016: */
017: package org.geotools.graph.traverse.standard;
018:
019: import java.util.Iterator;
020:
021: import org.geotools.graph.structure.Graph;
022: import org.geotools.graph.structure.GraphVisitor;
023: import org.geotools.graph.structure.Graphable;
024: import org.geotools.graph.structure.Node;
025: import org.geotools.graph.traverse.GraphTraversal;
026: import org.geotools.graph.traverse.basic.AbstractGraphIterator;
027: import org.geotools.graph.util.FIFOQueue;
028: import org.geotools.graph.util.Queue;
029:
030: /**
031: * Iterates over the nodes of a graph in <B>Breadth First Topological Sort</B>
032: * pattern. The following is an illustration of the iteration.<BR>
033: * <IMG src="doc-files/breadth_topo.gif"><BR>
034: * <BR>
035: * Initially all nodes of degree less than two are <B>active</B>
036: * (ready to be visited). As nodes are visited, a node can become active
037: * when all but one of its related nodes have been visited (
038: * degree = counter + 1). When a node becomes active it is placed into the
039: * <B>active node queue</B> (queue of nodes to be visited).
040: * The Breadth First Topological iterator places
041: * nodes into the queue in <B>First In First Out</B> order.<BR>
042: * <BR>
043: * To determine when a node is to become active the iterator uses the counter
044: * associated with each node. If these counters are modified by an entity
045: * other then the iterator, the iteration may be affected in undefined ways.
046: *
047: * @author Justin Deoliveira, Refractions Research Inc, jdeolive@refractions.net
048: *
049: * @source $URL: http://svn.geotools.org/geotools/tags/2.4.1/modules/extension/graph/src/main/java/org/geotools/graph/traverse/standard/BreadthFirstTopologicalIterator.java $
050: */
051: public class BreadthFirstTopologicalIterator extends
052: AbstractGraphIterator {
053:
054: /** Queue of active nodes **/
055: private Queue m_queue;
056:
057: /**
058: * Creates the active queue, and populates it with all nodes of degree less
059: * than 2. Counters of all nodes are also reset to 0.
060: *
061: * @see org.geotools.graph.traverse.GraphIterator#init(Graph)
062: */
063: public void init(Graph graph, GraphTraversal traversal) {
064: //create queue
065: m_queue = buildQueue(graph);
066:
067: //initialize nodes
068: graph.visitNodes(new GraphVisitor() {
069: public int visit(Graphable component) {
070: Node node = (Node) component;
071:
072: //reset counter to zero
073: node.setCount(0);
074:
075: if (node.getDegree() < 2)
076: m_queue.enq(node);
077:
078: return (0);
079: }
080: });
081: }
082:
083: /**
084: * Returns the next node in the active node queue.
085: *
086: * @see org.geotools.graph.traverse.GraphIterator#next()
087: */
088: public Graphable next(GraphTraversal traversal) {
089: return (!m_queue.isEmpty() ? (Graphable) m_queue.deq() : null);
090: }
091:
092: /**
093: * Continues the iteration by incrementing the counters of any unvisited
094: * nodes related to the current node. If any related nodes have counters
095: * equal to degree of that node - 1, it is placed into the active queue.
096: *
097: * @see org.geotools.graph.traverse.GraphIterator#cont(Graphable)
098: */
099: public void cont(Graphable current, GraphTraversal traversal) {
100: //increment the count of all adjacent nodes by one
101: // if the result count is 1 less than the degree, place it into the queue
102: for (Iterator itr = current.getRelated(); itr.hasNext();) {
103: Node related = (Node) itr.next();
104: if (!traversal.isVisited(related)) {
105: related.setCount(related.getCount() + 1);
106: if (related.getDegree() - 1 == related.getCount())
107: m_queue.enq(related);
108: }
109: }
110: }
111:
112: /**
113: * Kills the current branch of the traversal by not incremening the counters
114: * of any related nodes.
115: *
116: * @see org.geotools.graph.traverse.GraphIterator#killBranch(Graphable)
117: */
118: public void killBranch(Graphable current, GraphTraversal traversal) {
119: //do nothing
120: }
121:
122: /**
123: * Builds the active node queue.
124: *
125: * @param graph The Graph whose components are being iterated over.
126: *
127: * @return A first in first out queue
128: */
129: protected Queue buildQueue(Graph graph) {
130: return (new FIFOQueue(graph.getNodes().size()));
131: }
132: }
|