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.Graphable;
023: import org.geotools.graph.traverse.GraphTraversal;
024: import org.geotools.graph.traverse.basic.SourceGraphIterator;
025: import org.geotools.graph.util.FIFOQueue;
026: import org.geotools.graph.util.Queue;
027:
028: /**
029: * Iterates over the nodes of a graph in a <B>Breadth First Search</B> pattern
030: * starting from a specified node. The following illustrates the iteration
031: * order. <BR>
032: * <BR>
033: * <IMG src="doc-files/bfs.gif"/><BR>
034: * <BR>
035: * The iteration operates by maintaning a node queue of <B>active</B> nodes.
036: * An <B>active</B> node is a node that will returned at a later stage of the i
037: * teration. The node queue for a Breadth First iteration is implemented as a
038: * <B>First In First Out</B> queue.
039: * A node is placed in the the node queue if it has not been visited, and
040: * it is adjacent to a a node that has been visited. The node queue intially
041: * contains only the source node of the traversal.
042: *
043: * @author Justin Deoliveira, Refractions Research Inc, jdeolive@refractions.net
044: *
045: * @source $URL: http://svn.geotools.org/geotools/tags/2.4.1/modules/extension/graph/src/main/java/org/geotools/graph/traverse/standard/BreadthFirstIterator.java $
046: */
047: public class BreadthFirstIterator extends SourceGraphIterator {
048:
049: /** Contains all nodes to be returned **/
050: private Queue m_active;
051:
052: /**
053: * Sets the source of the traversal and places it in the node queue. The first
054: * call to this method will result in the internal node queue being built.
055: * Subsequent calls to the method clear the node queue and reset the iteration.
056: *
057: * @see SourceGraphIterator#setSource(Graphable)
058: */
059: public void setSource(Graphable source) {
060: super .setSource(source);
061:
062: //set source of traversal, creating queue if necessary
063: if (m_active == null)
064: m_active = buildQueue(getGraph());
065: else if (m_active.isEmpty())
066: m_active.clear();
067:
068: m_active.enq(getSource());
069: }
070:
071: /**
072: * Does nothing.
073: *
074: * @see org.geotools.graph.traverse.GraphIterator#init(Graph)
075: */
076: public void init(Graph graph, GraphTraversal traversal) {
077: //do nothing
078: }
079:
080: /**
081: * Returns the next node from the node queue that has not yet been visited. It
082: * is possible for the node queue to contain duplicate entries. To prevent
083: * the iteration returning the same node multiple times, the visited flag is
084: * checked on nodes coming out of the queue. If the flag is set, the node
085: * is ignored, not returned, and the next node in the queue is returned. This
086: * is however tranparent to the caller.
087: *
088: * @see org.geotools.graph.traverse.GraphIterator#next()
089: */
090: public Graphable next(GraphTraversal traversal) {
091: while (!m_active.isEmpty()) {
092: Graphable next = (Graphable) m_active.deq();
093: if (!traversal.isVisited(next))
094: return (next);
095: }
096: return (null);
097: }
098:
099: /**
100: * Looks for nodes adjacent to the current node to place into the node queue.
101: * An adjacent node is only placed into the node queue if its visited flag
102: * is unset.
103: *
104: * @see org.geotools.graph.traverse.GraphIterator#cont(Graphable)
105: */
106: public void cont(Graphable current, GraphTraversal traversal) {
107: for (Iterator itr = current.getRelated(); itr.hasNext();) {
108: Graphable related = (Graphable) itr.next();
109: if (!traversal.isVisited(related)) {
110: m_active.enq(related);
111: }
112: }
113: }
114:
115: /**
116: * Kills the current branch by not looking for any adjacent nodes to place
117: * into the node queue.
118: *
119: * @see org.geotools.graph.traverse.GraphIterator#killBranch(Graphable)
120: */
121: public void killBranch(Graphable current, GraphTraversal traversal) {
122: //do not look for any adjacent nodes to place into the active queue
123: }
124:
125: /**
126: * Builds the node queue for the iteration.
127: *
128: * @param graph The graph being iterated over.
129: *
130: * @return A First In First Out queue.
131: */
132: protected Queue buildQueue(Graph graph) {
133: return (new FIFOQueue(graph.getNodes().size()));
134: }
135:
136: /**
137: * Returns the node queue.
138: *
139: * @return The node queue.
140: */
141: protected Queue getQueue() {
142: return (m_active);
143: }
144:
145: }
|