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.Map;
020: import java.util.StringTokenizer;
021:
022: import junit.framework.TestCase;
023:
024: import org.geotools.graph.GraphTestUtil;
025: import org.geotools.graph.build.GraphBuilder;
026: import org.geotools.graph.build.basic.BasicGraphBuilder;
027: import org.geotools.graph.structure.Edge;
028: import org.geotools.graph.structure.GraphVisitor;
029: import org.geotools.graph.structure.Graphable;
030: import org.geotools.graph.structure.Node;
031: import org.geotools.graph.traverse.GraphTraversal;
032: import org.geotools.graph.traverse.basic.BasicGraphTraversal;
033: import org.geotools.graph.traverse.basic.CountingWalker;
034:
035: public class DijkstraIteratorTest extends TestCase {
036:
037: public GraphBuilder m_builder;
038:
039: public DijkstraIteratorTest(String name) {
040: super (name);
041: }
042:
043: protected void setUp() throws Exception {
044: super .setUp();
045:
046: m_builder = createBuilder();
047: }
048:
049: /**
050: * Create a graph with no bifurcations and start a full traversal from start
051: * node. <BR>
052: * <BR>
053: * Expected: 1. Every node should be visited in order.
054: * 2. Every node should have a cost associated with == id
055: * 3. Every node should havea parent with id node id + 1
056: *
057: */
058: public void test_0() {
059: int nnodes = 100;
060: Node[] ends = GraphTestUtil.buildNoBifurcations(builder(),
061: nnodes);
062:
063: CountingWalker walker = new CountingWalker();
064:
065: final DijkstraIterator iterator = createIterator();
066: iterator.setSource(ends[0]);
067:
068: BasicGraphTraversal traversal = new BasicGraphTraversal(
069: builder().getGraph(), walker, iterator);
070: traversal.init();
071: traversal.traverse();
072:
073: GraphVisitor visitor = new GraphVisitor() {
074: public int visit(Graphable component) {
075: assertTrue(component.isVisited());
076: assertTrue(iterator.getCost(component) == (double) component
077: .getID());
078: if (component.getID() == 0)
079: assertNull(iterator.getParent(component));
080: else
081: assertTrue(iterator.getParent(component).getID() == component
082: .getID() - 1);
083:
084: return 0;
085: }
086: };
087: builder().getGraph().visitNodes(visitor);
088:
089: assertTrue(walker.getCount() == nnodes);
090: }
091:
092: /**
093: * Create a graph with no bifurcations and start a traversal from start
094: * node, then suspend, and resume. <BR>
095: * <BR>
096: * Expected: After supsend:
097: * 1. Nodes from 0 to suspend node should be visted, others not.
098: *
099: * After resume:
100: * 1. Next node visited should have id suspend node id + 1
101: * 2. Every node should have a cost associated with it == id
102: * 3. Every node should have a parent with id node id + 1
103: */
104: public void test_1() {
105: int nnodes = 100;
106: Node[] ends = GraphTestUtil.buildNoBifurcations(builder(),
107: nnodes);
108: final int suspend = 50;
109:
110: CountingWalker walker = new CountingWalker() {
111: int m_mode = 0;
112:
113: public int visit(Graphable element, GraphTraversal traversal) {
114: super .visit(element, traversal);
115: if (m_mode == 0) {
116: if (element.getID() == suspend) {
117: m_mode++;
118: return (GraphTraversal.SUSPEND);
119: }
120: } else if (m_mode == 1) {
121: assertTrue(element.getID() == suspend + 1);
122: m_mode++;
123: }
124: return (GraphTraversal.CONTINUE);
125: }
126: };
127:
128: final DijkstraIterator iterator = createIterator();
129: iterator.setSource(ends[0]);
130:
131: BasicGraphTraversal traversal = new BasicGraphTraversal(
132: builder().getGraph(), walker, iterator);
133: traversal.init();
134: traversal.traverse();
135:
136: GraphVisitor visitor = new GraphVisitor() {
137: public int visit(Graphable component) {
138: if (component.getID() <= suspend)
139: assertTrue(component.isVisited());
140: else
141: assertTrue(!component.isVisited());
142: return 0;
143: }
144: };
145: builder().getGraph().visitNodes(visitor);
146: assertTrue(walker.getCount() == nnodes - suspend + 1);
147:
148: //resume
149: traversal.traverse();
150:
151: visitor = new GraphVisitor() {
152: public int visit(Graphable component) {
153: assertTrue(component.isVisited());
154: assertTrue(iterator.getCost(component) == (double) component
155: .getID());
156: if (component.getID() == 0)
157: assertNull(iterator.getParent(component));
158: else
159: assertTrue(iterator.getParent(component).getID() == component
160: .getID() - 1);
161:
162: return 0;
163: }
164: };
165: builder().getGraph().visitNodes(visitor);
166: assertTrue(walker.getCount() == nnodes);
167: }
168:
169: /**
170: * Create a graph with no bifurcations and start a traversal from start
171: * node, then kill branch, and resume. <BR>
172: * <BR>
173: * Expected: After kill branch:
174: * 1. Traversal ends
175: * After resume:
176: * 2. No more nodes visited.
177: */
178: public void test_2() {
179: int nnodes = 100;
180: Node[] ends = GraphTestUtil.buildNoBifurcations(builder(),
181: nnodes);
182: final int kill = 50;
183:
184: CountingWalker walker = new CountingWalker() {
185: int m_mode = 0;
186:
187: public int visit(Graphable element, GraphTraversal traversal) {
188: super .visit(element, traversal);
189: if (m_mode == 0) {
190: if (element.getID() == kill) {
191: m_mode++;
192: return (GraphTraversal.KILL_BRANCH);
193: }
194: }
195:
196: return (GraphTraversal.CONTINUE);
197: }
198: };
199:
200: final DijkstraIterator iterator = createIterator();
201: iterator.setSource(ends[0]);
202:
203: BasicGraphTraversal traversal = new BasicGraphTraversal(
204: builder().getGraph(), walker, iterator);
205: traversal.init();
206: traversal.traverse();
207:
208: GraphVisitor visitor = new GraphVisitor() {
209: public int visit(Graphable component) {
210: if (component.getID() <= kill)
211: assertTrue(component.isVisited());
212: else
213: assertTrue(!component.isVisited());
214:
215: return 0;
216: }
217: };
218: builder().getGraph().visitNodes(visitor);
219: assertTrue(walker.getCount() == nnodes - kill + 1);
220:
221: //resume
222: traversal.traverse();
223: builder().getGraph().visitNodes(visitor);
224: assertTrue(walker.getCount() == nnodes - kill + 1);
225: }
226:
227: /**
228: * Create a balanced binary tree and do a normal traversal starting at root.
229: * <BR>
230: * <BR>
231: * Expected: 1. Every node should be visited.
232: * 2. The dijsktra parent of each node should be the same as
233: * the parent of the tree.
234: * 3. The cost of each node should be equal to its depth.
235: */
236: public void test_3() {
237: int k = 4;
238: Object[] obj = GraphTestUtil.buildPerfectBinaryTree(builder(),
239: k);
240: final Node root = (Node) obj[0];
241:
242: CountingWalker walker = new CountingWalker();
243: final DijkstraIterator iterator = createIterator();
244: iterator.setSource((Node) obj[0]);
245:
246: BasicGraphTraversal traversal = new BasicGraphTraversal(
247: builder().getGraph(), walker, iterator);
248: traversal.init();
249: traversal.traverse();
250:
251: GraphVisitor visitor = new GraphVisitor() {
252: public int visit(Graphable component) {
253: assertTrue(component.isVisited());
254: String id = component.getObject().toString();
255: StringTokenizer st = new StringTokenizer(id, ".");
256:
257: assertTrue(iterator.getCost(component) == (double) st
258: .countTokens() - 1);
259: if (component != root) {
260: String parentid = id.substring(0, id.length() - 2);
261: assertTrue(iterator.getParent(component)
262: .getObject().toString().equals(parentid));
263: }
264:
265: return 0;
266: }
267: };
268: builder().getGraph().visitNodes(visitor);
269: assertTrue(walker.getCount() == Math.pow(2, k + 1) - 1);
270: }
271:
272: /**
273: * Create a balanced binary tree and do a normal traversal starting at root
274: * and then suspend at right right child of root, then resume
275: * <BR>
276: * <BR>
277: * Expected: After suspend:
278: * 1. Not every node should be visited
279: * After resume:
280: * 1. Every node should be visited.
281: */
282: public void test_4() {
283: int k = 4;
284: Object[] obj = GraphTestUtil.buildPerfectBinaryTree(builder(),
285: k);
286: Map id2node = (Map) obj[1];
287:
288: final Node root = (Node) obj[0];
289: final Node lc = (Node) id2node.get(root.getObject().toString()
290: + ".0");
291: final Node rc = (Node) id2node.get(root.getObject().toString()
292: + ".1");
293:
294: CountingWalker walker = new CountingWalker() {
295: private int m_mode = 0;
296:
297: public int visit(Graphable element, GraphTraversal traversal) {
298: super .visit(element, traversal);
299: if (m_mode == 0) {
300: if (element == rc) {
301: m_mode++;
302: return (GraphTraversal.SUSPEND);
303: }
304: }
305: return (GraphTraversal.CONTINUE);
306: }
307: };
308:
309: final DijkstraIterator iterator = createIterator();
310: iterator.setSource((Node) obj[0]);
311:
312: BasicGraphTraversal traversal = new BasicGraphTraversal(
313: builder().getGraph(), walker, iterator);
314: traversal.init();
315: traversal.traverse();
316:
317: GraphVisitor visitor = new GraphVisitor() {
318: public int visit(Graphable component) {
319: if (component != root && component != lc
320: && component != rc)
321: assertTrue(!component.isVisited());
322:
323: return 0;
324: }
325: };
326: builder().getGraph().visitNodes(visitor);
327:
328: //resume
329: traversal.traverse();
330:
331: visitor = new GraphVisitor() {
332: public int visit(Graphable component) {
333: assertTrue(component.isVisited());
334: return (0);
335: }
336: };
337: builder().getGraph().visitNodes(visitor);
338: assertTrue(walker.getCount() == Math.pow(2, k + 1) - 1);
339: }
340:
341: /**
342: * Create a balanced binary tree and do a normal traversal starting at root
343: * and then kill at right right child of root, then resume
344: * <BR>
345: * <BR>
346: * Expected: 1. Every node in left subtree should be visited
347: * 2. Every node in right substree (minus right child of root)
348: * should not be visited
349: *
350: */
351: public void test_5() {
352: int k = 4;
353: Object[] obj = GraphTestUtil.buildPerfectBinaryTree(builder(),
354: k);
355: Map id2node = (Map) obj[1];
356:
357: final Node root = (Node) obj[0];
358: final Node lc = (Node) id2node.get(root.getObject().toString()
359: + ".0");
360: final Node rc = (Node) id2node.get(root.getObject().toString()
361: + ".1");
362:
363: CountingWalker walker = new CountingWalker() {
364: private int m_mode = 0;
365:
366: public int visit(Graphable element, GraphTraversal traversal) {
367: super .visit(element, traversal);
368: if (m_mode == 0) {
369: if (element == rc) {
370: m_mode++;
371: return (GraphTraversal.KILL_BRANCH);
372: }
373: }
374: return (GraphTraversal.CONTINUE);
375: }
376: };
377:
378: final DijkstraIterator iterator = createIterator();
379: iterator.setSource((Node) obj[0]);
380:
381: BasicGraphTraversal traversal = new BasicGraphTraversal(
382: builder().getGraph(), walker, iterator);
383: traversal.init();
384: traversal.traverse();
385:
386: GraphVisitor visitor = new GraphVisitor() {
387: public int visit(Graphable component) {
388: if (component == root || component == lc
389: || component == rc)
390: assertTrue(component.isVisited());
391: else {
392: String id = component.getObject().toString();
393: if (id.startsWith("0.1."))
394: assertTrue(!component.isVisited());
395: else
396: assertTrue(component.isVisited());
397: }
398:
399: return 0;
400: }
401: };
402: builder().getGraph().visitNodes(visitor);
403:
404: assertTrue(walker.getCount() == Math.pow(2, k) + 1);
405: }
406:
407: /**
408: * Create a circular graph and perform a full traversal. <BR>
409: * <BR>
410: * Expected : 1. For nodes with id < (total # of nodes) / 2:
411: * a. parent should be node with id - 1
412: * b. cost == id
413: * 2. For nodes with id > (total # of nodes) / 2;
414: * a. parent should be node with id + 1
415: * b. cost == total # of nodes - id
416: *
417: */
418: public void test_6() {
419: int nnodes = 100;
420: Node[] ends = GraphTestUtil.buildCircular(builder(), nnodes);
421:
422: CountingWalker walker = new CountingWalker();
423:
424: final DijkstraIterator iterator = createIterator();
425: iterator.setSource(ends[0]);
426:
427: BasicGraphTraversal traversal = new BasicGraphTraversal(
428: builder().getGraph(), walker, iterator);
429: traversal.init();
430: traversal.traverse();
431:
432: GraphVisitor visitor = new GraphVisitor() {
433: public int visit(Graphable component) {
434: Graphable parent = iterator.getParent(component);
435: if (component.getID() < 50 && component.getID() > 0) {
436: assertTrue(iterator.getCost(component) == (double) component
437: .getID());
438: assertTrue(parent.getID() == component.getID() - 1);
439: } else if (component.getID() > 50
440: && component.getID() < 99) {
441: assertTrue(iterator.getCost(component) == (double) 100
442: - component.getID());
443: assertTrue(parent.getID() == component.getID() + 1);
444: } else if (component.getID() == 0) {
445: assertTrue(parent == null);
446: assertTrue(iterator.getCost(component) == 0d);
447: } else if (component.getID() == 99) {
448: assertTrue(parent.getID() == 0);
449: assertTrue(iterator.getCost(component) == 1d);
450: }
451:
452: return (0);
453: }
454: };
455:
456: builder().getGraph().visitNodes(visitor);
457: assertTrue(walker.getCount() == nnodes);
458: }
459:
460: protected DijkstraIterator createIterator() {
461: return (new DijkstraIterator(
462: new DijkstraIterator.EdgeWeighter() {
463: public double getWeight(Edge e) {
464:
465: return (1);
466: }
467:
468: }));
469: }
470:
471: protected GraphBuilder createBuilder() {
472: return (new BasicGraphBuilder());
473: }
474:
475: protected GraphBuilder builder() {
476: return (m_builder);
477: }
478: }
|