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 junit.framework.TestCase;
020:
021: import org.geotools.graph.GraphTestUtil;
022: import org.geotools.graph.build.GraphBuilder;
023: import org.geotools.graph.build.basic.BasicGraphBuilder;
024: import org.geotools.graph.structure.Graph;
025: import org.geotools.graph.structure.GraphVisitor;
026: import org.geotools.graph.structure.Graphable;
027: import org.geotools.graph.structure.Node;
028: import org.geotools.graph.traverse.GraphTraversal;
029: import org.geotools.graph.traverse.basic.BasicGraphTraversal;
030: import org.geotools.graph.traverse.basic.CountingWalker;
031:
032: public class NoBifurcationIteratorTest extends TestCase {
033:
034: private GraphBuilder m_builder;
035:
036: public NoBifurcationIteratorTest(String name) {
037: super (name);
038: }
039:
040: protected void setUp() throws Exception {
041: super .setUp();
042:
043: m_builder = createBuilder();
044: }
045:
046: /**
047: * Create a simple graph which has no bifurcations and do a normal traversal.
048: * <BR>
049: * <BR>
050: * Expected: 1. Every node should be visited.
051: * 2. Nodes should be visited in order.
052: */
053: public void test_0() {
054: int nnodes = 100;
055: Node[] ends = GraphTestUtil.buildNoBifurcations(builder(),
056: nnodes);
057:
058: CountingWalker walker = new CountingWalker() {
059: public int visit(Graphable element, GraphTraversal traversal) {
060: super .visit(element, traversal);
061: element.setCount(getCount() - 1);
062:
063: //nodes should be visited in order
064: assertTrue(element.getID() == getCount() - 1);
065: return (GraphTraversal.CONTINUE);
066: }
067: };
068:
069: NoBifurcationIterator iterator = createIterator();
070: iterator.setSource(ends[0]);
071:
072: BasicGraphTraversal traversal = new BasicGraphTraversal(
073: builder().getGraph(), walker, iterator);
074: traversal.init();
075: traversal.traverse();
076:
077: //every node should have been visited
078: assertTrue(walker.getCount() == builder().getGraph().getNodes()
079: .size());
080: }
081:
082: /**
083: * Create a simple graph which has no bifurcations and do a traversal
084: * suspending at some intermediate node. Then continue traversal.
085: *
086: * Expected: After suspend:
087: * 1. Every node of with an id greater than the id of the suspending
088: * node should not be visited.
089: * After continue:
090: * 1. First node visited after continue should have id =
091: * id + suspend node + 1
092: * 2. Every node should be visited.
093: *
094: */
095: public void test_1() {
096: int nnodes = 100;
097: Node[] ends = GraphTestUtil.buildNoBifurcations(builder(),
098: nnodes);
099: final int suspend = 50;
100: ;
101:
102: CountingWalker walker = new CountingWalker() {
103: private int m_mode = 0;
104:
105: public int visit(Graphable element, GraphTraversal traversal) {
106: super .visit(element, traversal);
107: if (m_mode == 0) {
108: //check for stopping node
109: if (element.getID() == suspend) {
110: m_mode++;
111: return (GraphTraversal.SUSPEND);
112: }
113: } else if (m_mode == 1) {
114: //check first node after continue
115: assertTrue(element.getID() == suspend + 1);
116: m_mode++;
117: }
118: return (GraphTraversal.CONTINUE);
119: }
120: };
121:
122: NoBifurcationIterator iterator = createIterator();
123: iterator.setSource(ends[0]);
124:
125: BasicGraphTraversal traversal = new BasicGraphTraversal(
126: builder().getGraph(), walker, iterator);
127: traversal.init();
128: traversal.traverse();
129:
130: //stopping node should be visited and nodes with greater id should not
131: GraphVisitor visitor = new GraphVisitor() {
132: public int visit(Graphable component) {
133: if (component.getID() <= suspend)
134: assertTrue(component.isVisited());
135: else
136: assertTrue(!component.isVisited());
137: return (0);
138: }
139: };
140: builder().getGraph().visitNodes(visitor);
141: assertTrue(walker.getCount() == nnodes - suspend + 1);
142:
143: traversal.traverse();
144:
145: //every node should now be visited
146: visitor = new GraphVisitor() {
147: public int visit(Graphable component) {
148: assertTrue(component.isVisited());
149: return (0);
150: }
151: };
152: builder().getGraph().visitNodes(visitor);
153: assertTrue(walker.getCount() == nnodes);
154: }
155:
156: /**
157: * Create a simple graph which has no bifurcations and do a kill branch at
158: * some intermediate node. Then continue the traversal.
159: *
160: * Expected: After kill:
161: * 1. Every node of with an id greater than the id of the killing
162: * node should not be visited.
163: * After continue:
164: * 2. No more nodes should be visited.
165: *
166: */
167: public void test_2() {
168: int nnodes = 100;
169: Node[] ends = GraphTestUtil.buildNoBifurcations(builder(), 100);
170: final int kill = 50;
171:
172: CountingWalker walker = new CountingWalker() {
173: private int m_mode = 0;
174:
175: public int visit(Graphable element, GraphTraversal traversal) {
176: super .visit(element, traversal);
177: if (m_mode == 0) {
178: //check for stopping node
179: if (element.getID() == kill) {
180: m_mode++;
181: return (GraphTraversal.KILL_BRANCH);
182: }
183: } else if (m_mode == 1) {
184: //should never get here
185: assertTrue(false);
186: }
187: return (GraphTraversal.CONTINUE);
188: }
189: };
190:
191: NoBifurcationIterator iterator = createIterator();
192: iterator.setSource(ends[0]);
193:
194: BasicGraphTraversal traversal = new BasicGraphTraversal(
195: builder().getGraph(), walker, iterator);
196: traversal.init();
197: traversal.traverse();
198:
199: //kill node should be visited and nodes with greater id should not
200: GraphVisitor visitor = new GraphVisitor() {
201: public int visit(Graphable component) {
202: if (component.getID() <= kill)
203: assertTrue(component.isVisited());
204: else
205: assertTrue(!component.isVisited());
206: return (0);
207: }
208: };
209: builder().getGraph().visitNodes(visitor);
210: assertTrue(walker.getCount() == nnodes - kill + 1);
211:
212: //continue, no more nodes should be visited
213: traversal.traverse();
214: }
215:
216: /**
217: * Create a simple graph with a single bifurcation and do a full traversal.
218: *
219: * Exepected: 1. The traversal should stop at the bifurcating node.
220: * 2. Every node after the bifurcating node should not be visited.
221: */
222: public void test_3() {
223: int nnodes = 100;
224: final int bif = 50;
225: Node[] ends = GraphTestUtil.buildSingleBifurcation(builder(),
226: nnodes, bif);
227:
228: CountingWalker walker = new CountingWalker();
229: NoBifurcationIterator iterator = createIterator();
230: iterator.setSource(ends[0]);
231:
232: BasicGraphTraversal traversal = new BasicGraphTraversal(
233: builder().getGraph(), walker, iterator);
234: traversal.init();
235: traversal.traverse();
236:
237: GraphVisitor visitor = new GraphVisitor() {
238: public int visit(Graphable component) {
239: if (component.getID() < bif) {
240: assertTrue(component.isVisited());
241: } else if (component.getID() >= bif) {
242: assertTrue(!component.isVisited());
243: }
244:
245: return (0);
246: }
247: };
248: builder().getGraph().visitNodes(visitor);
249: assertTrue(walker.getCount() == nnodes - bif);
250: }
251:
252: /**
253: * Create a graph that contains a cycle and do a full traversal.<BR>
254: * <BR>
255: * Expected: 1. All nodes visited.
256: */
257: public void test_4() {
258: int nnodes = 100;
259: GraphTestUtil.buildCircular(builder(), nnodes);
260: GraphVisitor visitor = new GraphVisitor() {
261: public int visit(Graphable component) {
262: if (component.getID() == 50)
263: return (Graph.PASS_AND_CONTINUE);
264: return (Graph.FAIL_QUERY);
265: }
266: };
267: Node source = (Node) builder().getGraph().queryNodes(visitor)
268: .get(0);
269:
270: CountingWalker walker = new CountingWalker();
271: NoBifurcationIterator iterator = createIterator();
272: iterator.setSource(source);
273:
274: BasicGraphTraversal traversal = new BasicGraphTraversal(
275: builder().getGraph(), walker, iterator);
276: traversal.init();
277: traversal.traverse();
278:
279: //ensure all nodes visisited
280: visitor = new GraphVisitor() {
281: public int visit(Graphable component) {
282: assertTrue(component.isVisited());
283: return (0);
284: }
285: };
286:
287: builder().getGraph().visitNodes(visitor);
288:
289: assertTrue(walker.getCount() == nnodes);
290: }
291:
292: protected GraphBuilder createBuilder() {
293: return (new BasicGraphBuilder());
294: }
295:
296: protected GraphBuilder builder() {
297: return (m_builder);
298: }
299:
300: protected NoBifurcationIterator createIterator() {
301: return (new NoBifurcationIterator());
302: }
303: }
|