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;
018:
019: import org.geotools.graph.structure.Graph;
020: import org.geotools.graph.structure.Graphable;
021:
022: /**
023: * Defines an algorithm in which to traverse the components of a graph.
024: * A graph iterator operates by repeatedly returing graph components to the
025: * caller. The order in which to return the components is specific to the
026: * iterator. However, <B>most</B> iterators follow the following conventions:<BR>
027: * <BR>
028: * <UL>
029: * <LI>Components are visited only once</LI>
030: * <LI>The next component to be returned is determined by the components that
031: * have been previously visited
032: * </UL>
033: * The following is an example of a GraphIterator. It returns nodes of a graph
034: * in a standard <B>Depth First Search</B> order, starting from a specified node.
035: * The nodes have been numbered to correspond to the iteration pattern. <BR>
036: * <BR>
037: * <IMG src="doc-files/dfs.gif"/>
038: * * indicates source of traversal<BR>
039: * <BR>
040: * <BR>
041: * In order to analyze the traversal, the following terms are defined:<BR>
042: * <BR>
043: * The <B>Next Set</B> of a traversal is the set of components that will be
044: * visited in a later stage of the traversal.<BR>
045: * The <B>Branch Set</B> of an component <B>e</B> is defined as the set of
046: * components that can be visited in a later stage of the traversal as a direct
047: * result of visiting <B>e</B>.
048: * <BR>
049: * <BR>
050: * In most traversals, the two sets are related. The Next Set is built by
051: * analyzing the Branch Set of the component being visited in the current stage
052: * of the traversal. Revisiting the above example, a Depth First Search
053: * Traversal operates as follows:<BR>
054: * <BR>
055: * <UL>
056: * <LI>Each node is visited only once.</LI>
057: * <LI>The Next Set is organized as a <B>Last In First Out</B> Queue (Stack).</LI>
058: * <LI>At each stage, every node in the Branch Set that has not yet been visited
059: * is added to the Next Set.
060: * </UL>
061: * As well it is assumed that nodes related to a node are sorted in
062: * alphabetic order.
063: * <BR>
064: * <BR>
065: * The following table summarizes the stages of the traversal:<BR>
066: * <BR>
067: * <TABLE border="1" style="font-family:Arial;font-size:10pt;" width="80%">
068: * <TH>Stage</TH>
069: * <TH>Visited Node</TH>
070: * <TH>Branch Set </TH>
071: * <TH>Next Set</TH>
072: * <TH>Comment</TH>
073: * <TR align="center">
074: * <TD align="center" width="10%">0</TD>
075: * <TD width="10%"> </TD>
076: * <TD width="10%"> </TD>
077: * <TD width="10%">{A}</TD>
078: * <TD width="40%" align="left"> Initial stage, iteration starts explicitly from A</TD>
079: * </TR>
080: * <TR align="center">
081: * <TD>1</TD><TD>A</TD><TD>{B,F}</TD><TD>{F,B}</TD>
082: * <TD align="left"> Related nodes added to <B>Next Set</B> in LIFO order.</TD>
083: * </TR>
084: * <TR align="center">
085: * <TD>2</TD><TD>F</TD><TD>{A,B}</TD><TD>{B,B}</TD>
086: * <TD align="left"> A already visited so not added to <B>Next Set</B><BR>
087: * B not yet visited so added to queue.</TD>
088: * </TR>
089: * <TR align="center">
090: * <TD>3</TD><TD>B</TD><TD>{A,C,D,E,F}</TD><TD>{B,E,D,C}</TD>
091: * <TD align="left"> A,F already visited so not added to <B>Next Set</B></TD>
092: * </TR>
093: * <TR align="center">
094: * <TD>4</TD><TD>B</TD><TD> </TD><TD>{E,D,C}</TD>
095: * <TD align="left"> B already visited so ignore and move to next stage</TD>
096: * </TR>
097: * <TR align="center">
098: * <TD>5</TD><TD>E</TD><TD>{B}</TD><TD>{D,C}</TD>
099: * <TD align="left"> </TD>
100: * </TR>
101: * <TR align="center">
102: * <TD>6</TD><TD>D</TD><TD>{B,C}</TD><TD>{C,C}</TD>
103: * <TD align="left"> </TD>
104: * </TR>
105: * <TR align="center">
106: * <TD>7</TD><TD>C</TD><TD>{B,D}</TD><TD>{C}</TD>
107: * <TD align="left"> </TD>
108: * </TR>
109: * <TR align="center">
110: * <TD>8</TD><TD align="center">C</TD><TD> </TD><TD>{ }</TD>
111: * <TD align="left"> C already visited so ignore and move to next stage</TD>
112: * </TR>
113: * <TR align="center">
114: * <TD>9</TD><TD> </TD><TD> </TD><TD>{ }</TD>
115: * <TD align="left"> Next set empty, iteration complete.</TD>
116: * </TR>
117: * </TABLE><BR>
118: * <BR>
119: * At any stage of a travesal a branch may be <B>killed</B>.When a branch is
120: * killed at a stage of an iteration, no elements in the current <B>Branch Set</B>
121: * are added to the <B>Next Set</B>. This is illustrated by revisiting the
122: * Depth First Search Iteration, but this time killing the branch at node B.
123: * The following table summarizes the stages of the traversal:<BR>
124: * <BR>
125: * <TABLE border="1" style="font-family:Arial;font-size:10pt;" width="80%">
126: * <TH>Stage</TH>
127: * <TH>Visited Node</TH>
128: * <TH>Branch Set </TH>
129: * <TH>Next Set</TH>
130: * <TH>Comment</TH>
131: * <TR align="center">
132: * <TD align="center" width="10%">0</TD>
133: * <TD width="10%"> </TD>
134: * <TD width="10%"> </TD>
135: * <TD width="10%">{A}</TD>
136: * <TD width="40%" align="left"> Initial stage, iteration starts explicitly from A</TD>
137: * </TR>
138: * <TR align="center">
139: * <TD>1</TD><TD>A</TD><TD>{B,F}</TD><TD>{F,B}</TD>
140: * <TD align="left"> Related nodes added to <B>Next Set</B> in LIFO order.</TD>
141: * </TR>
142: * <TR align="center">
143: * <TD>2</TD><TD>F</TD><TD>{A,B}</TD><TD>{B,B}</TD>
144: * <TD align="left"> A already visited so not added to <B>Next Set</B><BR>
145: * B not yet visited so added to queue.</TD>
146: * </TR>
147: * <TR align="center">
148: * <TD>3</TD><TD>B</TD><TD>{A,C,D,E,F}</TD><TD>{B}</TD>
149: * <TD align="left"> <B>Branch Killed.</B> No nodes added to <B>Next Set</B></TD>
150: * </TR>
151: * <TR align="center">
152: * <TD>4</TD><TD>B</TD><TD> </TD><TD>{ }</TD>
153: * <TD align="left"> B already visited so ignore and move to next stage</TD>
154: * </TR>
155: * <TR align="center">
156: * <TD>9</TD><TD> </TD><TD> </TD><TD>{ }</TD>
157: * <TD align="left"> Next set empty, iteration complete.</TD>
158: * </TR>
159: * </TABLE><BR>
160: * In this example, killing the branch at node B results in nodes C, D, and E
161: * never being visited.<BR>
162: *
163: * @see GraphWalker
164: * @see GraphTraversal
165: * @author Justin Deoliveira, Refractions Research Inc, jdeolive@refractions.net
166: *
167: * @source $URL: http://svn.geotools.org/geotools/tags/2.4.1/modules/extension/graph/src/main/java/org/geotools/graph/traverse/GraphIterator.java $
168: */
169: public interface GraphIterator {
170:
171: /**
172: * Sets the traversal for the iterator.
173: *
174: * @param traversal The traversal requesting components from the iterator.
175: */
176: public void setTraversal(GraphTraversal traversal);
177:
178: /**
179: * Returns the traversal for the iterator.
180: *
181: * @return The traversal requesting components from the iterator.
182: */
183: public GraphTraversal getTraversal();
184:
185: /**
186: * Signals to the itereator that iteration is about to begin. This often
187: * results in the creation/initialization of any internal data structures
188: * used by the iterator.
189: *
190: * @param graph The graph being whose components are being iterated over.
191: * @todo DOCUMENT ME!
192: */
193: public void init(Graph graph, GraphTraversal traversal);
194:
195: /**
196: * Returns the next graph component in the iteration. To signal to the caller
197: * that the iteration is complete, null should be returned.
198: *
199: * @return The next component in the iteration, or null if iteration is
200: * complete.
201: * @todo DOCUMENT ME!
202: *
203: */
204: public Graphable next(GraphTraversal traversal);
205:
206: /**
207: * Signals to the iterator that iteration should continue from the current
208: * component in the traversal.
209: *
210: * @param current The current component of the traversal.
211: * @todo DOCUMENT ME!
212: */
213: public void cont(Graphable current, GraphTraversal traversal);
214:
215: /**
216: * Signals the iterator to kill the branch at the current component.
217: *
218: * @param current The current component of the traversal.
219: * @todo DOCUMENT ME!
220: */
221: public void killBranch(Graphable current, GraphTraversal traversal);
222: }
|