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.structure.Node;
024: import org.geotools.graph.traverse.GraphIterator;
025: import org.geotools.graph.traverse.GraphTraversal;
026: import org.geotools.graph.traverse.basic.SourceGraphIterator;
027:
028: /**
029: * Iterates over the nodes of a graph starting from a specified node, stopping
030: * at a bifurcation. A <B>bifurcation</B> is defined as a node of degree > 2.
031: * The following figures illustrate examples of the iterator.<BR>
032: * <BR>
033: * <IMG src="doc-files/nobif_0.gif"/><BR>
034: * <BR>
035: * <BR>
036: * <BR>
037: * <IMG src="doc-files/nobif_1.gif"/><BR>
038: * <BR>
039: *
040: * @author Justin Deoliveira, Refractions Research Inc, jdeolive@refractions.net
041: *
042: * @source $URL: http://svn.geotools.org/geotools/tags/2.4.1/modules/extension/graph/src/main/java/org/geotools/graph/traverse/standard/NoBifurcationIterator.java $
043: */
044: public class NoBifurcationIterator extends SourceGraphIterator {
045:
046: /** the next node to be returned by the iterator **/
047: private Node m_next;
048:
049: /**
050: * Does nothing.
051: *
052: * @see GraphIterator#init(Graph)
053: */
054: public void init(Graph graph, GraphTraversal traversal) {
055: //do nothing
056: }
057:
058: /**
059: * Sets the source of the traversal. This must be a node of degree less than
060: * or equal to 2.
061: *
062: * @param source node of degree less than or equal 2
063: *
064: * @see SourceGraphIterator#setSource(Graphable)
065: * @throws IllegalStateException
066: */
067: public void setSource(Graphable source) {
068: //check that source node if of degree <= 2
069: if (((Node) source).getDegree() > 2) {
070: throw new IllegalStateException(
071: "Cannot start a no bifurcation traversal on a node that "
072: + "bifurcates.");
073: }
074: super .setSource(source);
075: m_next = (Node) getSource();
076: }
077:
078: /**
079: * The next node in the iteration is the first node found adjacent to the
080: * current node that is non visited and of degree less than 2.
081: *
082: * @see org.geotools.graph.traverse.GraphIterator#next()
083: */
084: public Graphable next(GraphTraversal traversal) {
085: return (m_next);
086: }
087:
088: /**
089: * Searches for the next node to be returned in the iteration. The next node
090: * is the first node (of two) related to the current node that is non visited
091: * and of degree <= 2.
092: *
093: * @see org.geotools.graph.traverse.GraphIterator#cont(Graphable)
094: */
095: public void cont(Graphable current, GraphTraversal traversal) {
096: //find a related node that is non visited and degree <= 2
097: Iterator itr = current.getRelated();
098: m_next = (Node) itr.next();
099: if (itr.hasNext()
100: && (traversal.isVisited(m_next) || m_next.getDegree() > 2))
101: m_next = (Node) itr.next();
102: if (traversal.isVisited(m_next) || m_next.getDegree() > 2)
103: m_next = null;
104: }
105:
106: /**
107: * Kills the current branch of the iteration by explicitly setting the next
108: * node to be returned to null. This call always ends the traversal.
109: *
110: * @see org.geotools.graph.traverse.GraphIterator#killBranch(Graphable)
111: */
112: public void killBranch(Graphable current, GraphTraversal traversal) {
113: m_next = null;
114: }
115: }
|