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:
021: import junit.framework.TestCase;
022:
023: import org.geotools.graph.GraphTestUtil;
024: import org.geotools.graph.build.GraphBuilder;
025: import org.geotools.graph.build.basic.BasicGraphBuilder;
026: import org.geotools.graph.structure.Graph;
027: import org.geotools.graph.structure.GraphVisitor;
028: import org.geotools.graph.structure.Graphable;
029: import org.geotools.graph.structure.Node;
030: import org.geotools.graph.traverse.GraphTraversal;
031: import org.geotools.graph.traverse.basic.BasicGraphTraversal;
032: import org.geotools.graph.traverse.basic.CountingWalker;
033: import org.geotools.graph.util.FIFOQueue;
034:
035: public class DepthFirstIteratorTest extends TestCase {
036:
037: private GraphBuilder m_builder;
038:
039: public DepthFirstIteratorTest(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 simple graph which has no bifurcations and do a normal traversal.
051: * <BR>
052: * <BR>
053: * Expected: 1. Every node should be visited.
054: * 2. Nodes should be visited in order.
055: */
056: public void test_0() {
057: int nnodes = 100;
058: Node[] ends = GraphTestUtil.buildNoBifurcations(builder(),
059: nnodes);
060:
061: CountingWalker walker = new CountingWalker() {
062: public int visit(Graphable element, GraphTraversal traversal) {
063: super .visit(element, traversal);
064: element.setCount(getCount() - 1);
065:
066: //nodes should be visited in order
067: assertTrue(element.getID() == getCount() - 1);
068: return (GraphTraversal.CONTINUE);
069: }
070: };
071:
072: DepthFirstIterator iterator = createIterator();
073:
074: BasicGraphTraversal traversal = new BasicGraphTraversal(
075: builder().getGraph(), walker, iterator);
076: traversal.init();
077:
078: iterator.setSource(ends[0]);
079: traversal.traverse();
080:
081: //every node should have been visited
082: assertTrue(walker.getCount() == builder().getGraph().getNodes()
083: .size());
084:
085: //ensure nodes visited only once
086: assertTrue(walker.getCount() == nnodes);
087:
088: }
089:
090: /**
091: * Create a simple graph which has no bifurcations and do a traversal
092: * suspending at some intermediate node. Then continue traversal.
093: *
094: * Expected: After suspend:
095: * 1. Every node of with an id greater than the id of the suspending
096: * node should not be visited.
097: * After continue:
098: * 1. First node visited after continue should have id =
099: * id + suspend node + 1
100: * 2. Every node should be visited.
101: *
102: */
103: public void test_1() {
104: int nnodes = 100;
105: Node[] ends = GraphTestUtil.buildNoBifurcations(builder(),
106: nnodes);
107: final int suspend = 50;
108: ;
109:
110: CountingWalker walker = new CountingWalker() {
111: private int m_mode = 0;
112:
113: public int visit(Graphable element, GraphTraversal traversal) {
114: super .visit(element, traversal);
115: if (m_mode == 0) {
116: //check for stopping node
117: if (element.getID() == suspend) {
118: m_mode++;
119: return (GraphTraversal.SUSPEND);
120: }
121: } else if (m_mode == 1) {
122: //check first node after continue
123: assertTrue(element.getID() == suspend + 1);
124: m_mode++;
125: }
126: return (GraphTraversal.CONTINUE);
127: }
128: };
129:
130: DepthFirstIterator iterator = createIterator();
131: BasicGraphTraversal traversal = new BasicGraphTraversal(
132: builder().getGraph(), walker, iterator);
133: traversal.init();
134:
135: iterator.setSource(ends[0]);
136: traversal.traverse();
137:
138: //stopping node should be visited and nodes with greater id should not
139: GraphVisitor visitor = new GraphVisitor() {
140: public int visit(Graphable component) {
141: if (component.getID() <= suspend)
142: assertTrue(component.isVisited());
143: else
144: assertTrue(!component.isVisited());
145: return (0);
146: }
147: };
148: builder().getGraph().visitNodes(visitor);
149:
150: //ensure nodes only visited once
151: assertTrue(walker.getCount() == nnodes - suspend + 1);
152:
153: traversal.traverse();
154:
155: //every node should now be visited
156: visitor = new GraphVisitor() {
157: public int visit(Graphable component) {
158: assertTrue(component.isVisited());
159: return (0);
160: }
161: };
162: builder().getGraph().visitNodes(visitor);
163:
164: //ensure nodes only visited once
165: assertTrue(walker.getCount() == nnodes);
166:
167: }
168:
169: /**
170: * Create a simple graph which has no bifurcations and do a kill branch at
171: * some intermediate node. Then continue the traversal.
172: *
173: * Expected: After kill:
174: * 1. Every node of with an id greater than the id of the killing
175: * node should not be visited.
176: * After continue:
177: * 2. No more nodes should be visited.
178: *
179: */
180: public void test_2() {
181: int nnodes = 100;
182: Node[] ends = GraphTestUtil.buildNoBifurcations(builder(),
183: nnodes);
184: final int kill = 50;
185:
186: CountingWalker walker = new CountingWalker() {
187: private int m_mode = 0;
188:
189: public int visit(Graphable element, GraphTraversal traversal) {
190: super .visit(element, traversal);
191: if (m_mode == 0) {
192: //check for stopping node
193: if (element.getID() == kill) {
194: m_mode++;
195: return (GraphTraversal.KILL_BRANCH);
196: }
197: } else if (m_mode == 1) {
198: //should never get here
199: assertTrue(false);
200: }
201: return (GraphTraversal.CONTINUE);
202: }
203: };
204:
205: DepthFirstIterator iterator = createIterator();
206: BasicGraphTraversal traversal = new BasicGraphTraversal(
207: builder().getGraph(), walker, iterator);
208: traversal.init();
209:
210: iterator.setSource(ends[0]);
211: traversal.traverse();
212:
213: //kill node should be visited and nodes with greater id should not
214: GraphVisitor visitor = new GraphVisitor() {
215: public int visit(Graphable component) {
216: if (component.getID() <= kill)
217: assertTrue(component.isVisited());
218: else
219: assertTrue(!component.isVisited());
220: return (0);
221: }
222: };
223: builder().getGraph().visitNodes(visitor);
224:
225: //ensure nodes only visited once
226: assertTrue(walker.getCount() == nnodes - kill + 1);
227:
228: //continue, no more nodes should be visited
229: traversal.traverse();
230: }
231:
232: /**
233: * Create a balanced binary tree and do a normal traversal starting at root.
234: * <BR>
235: * <BR>
236: * Expected: 1. Every node should be visited.
237: * 2. For each node, every node in one of its two subtrees should
238: * have been visited before every node in the other subtree.
239: */
240: public void test_3() {
241: int k = 4;
242: Object[] obj = GraphTestUtil.buildPerfectBinaryTree(builder(),
243: k);
244: Node root = (Node) obj[0];
245: final Map obj2node = (Map) obj[1];
246:
247: GraphVisitor initializer = new GraphVisitor() {
248: public int visit(Graphable component) {
249: component.setCount(-1);
250: return 0;
251: }
252: };
253:
254: CountingWalker walker = new CountingWalker() {
255: public int visit(Graphable element, GraphTraversal traversal) {
256: element.setCount(getCount());
257: return super .visit(element, traversal);
258: }
259: };
260:
261: DepthFirstIterator iterator = createIterator();
262: BasicGraphTraversal traversal = new BasicGraphTraversal(
263: builder().getGraph(), walker, iterator);
264: traversal.init();
265:
266: iterator.setSource(root);
267: traversal.traverse();
268:
269: GraphVisitor visitor = new GraphVisitor() {
270: public int visit(Graphable component) {
271: //ensure component visited
272: assertTrue(component.isVisited());
273:
274: Node ln = (Node) obj2node.get(component.getObject()
275: .toString()
276: + ".0");
277: Node rn = (Node) obj2node.get(component.getObject()
278: .toString()
279: + ".1");
280:
281: if (ln != null) {
282: Node n1 = ln;
283: Node n2 = rn;
284: if (ln.getCount() > rn.getCount()) {
285: n1 = rn;
286: n2 = ln;
287: }
288:
289: FIFOQueue queue = new FIFOQueue(256);
290: queue.enq(n1);
291:
292: //ensure all subnodes of n1 visited before n2
293: while (!queue.isEmpty()) {
294: Node n = (Node) queue.deq();
295:
296: ln = (Node) obj2node.get(n.getObject()
297: .toString()
298: + ".0");
299: rn = (Node) obj2node.get(n.getObject()
300: .toString()
301: + ".1");
302:
303: if (ln == null)
304: continue;
305:
306: assertTrue(ln.getCount() < n2.getCount());
307: assertTrue(rn.getCount() < n2.getCount());
308:
309: queue.enq(ln);
310: queue.enq(rn);
311: }
312: }
313: return 0;
314: }
315: };
316:
317: builder().getGraph().visitNodes(visitor);
318:
319: //ensure nodes only visited once
320: assertTrue(walker.getCount() == (int) Math.pow(2, k + 1) - 1);
321: }
322:
323: /**
324: * Create a balanced binary tree and do a traversal starting at root and
325: * suspending at the first node seen that is not the root, (should be left
326: * child). Then continue the traversal.
327: * <BR>
328: * <BR>
329: * Expected: After suspend:
330: * 1. Only root and first non root should be visited.
331: *
332: * After continue:
333: * 1. First node visited should be child of suspending node.
334: * 2. Every node should be visited.
335: */
336: public void test_4() {
337: int k = 4;
338: Object[] obj = GraphTestUtil.buildPerfectBinaryTree(builder(),
339: k);
340: final Node root = (Node) obj[0];
341: final Map obj2node = (Map) obj[1];
342: final Node ln = (Node) obj2node.get(root.getObject().toString()
343: + ".0");
344: final Node rn = (Node) obj2node.get(root.getObject().toString()
345: + ".1");
346:
347: CountingWalker walker = new CountingWalker() {
348: private int m_mode = 0;
349:
350: public int visit(Graphable element, GraphTraversal traversal) {
351: super .visit(element, traversal);
352: if (m_mode == 0) {
353: if (element != root) {
354: //check which child of root was first visited
355: m_mode++;
356: return (GraphTraversal.SUSPEND);
357: }
358: } else if (m_mode == 1) {
359: String eid = element.getObject().toString();
360: if (ln.isVisited()) {
361: assertTrue(eid.equals(ln.getObject().toString()
362: + ".0")
363: || eid.equals(ln.getObject().toString()
364: + ".1"));
365: } else {
366: assertTrue(eid.equals(rn.getObject().toString()
367: + ".0")
368: || eid.equals(rn.getObject().toString()
369: + ".1"));
370: }
371: m_mode++;
372: }
373:
374: return (GraphTraversal.CONTINUE);
375: }
376: };
377:
378: DepthFirstIterator iterator = createIterator();
379: BasicGraphTraversal traversal = new BasicGraphTraversal(
380: builder().getGraph(), walker, iterator);
381: traversal.init();
382:
383: iterator.setSource(root);
384: traversal.traverse();
385:
386: //ensure that only root and one of children is visited
387: assertTrue(root.isVisited());
388: assertTrue((rn.isVisited() && !ln.isVisited())
389: || (!rn.isVisited() && ln.isVisited()));
390: assertTrue(walker.getCount() == 2);
391:
392: GraphVisitor visitor = new GraphVisitor() {
393: public int visit(Graphable component) {
394: if (component != root && component != ln
395: && component != rn) {
396: assertTrue(!component.isVisited());
397: }
398: return (0);
399: }
400: };
401: builder().getGraph().visitNodes(visitor);
402:
403: traversal.traverse();
404:
405: //ensure all nodes visited
406: visitor = new GraphVisitor() {
407: public int visit(Graphable component) {
408: assertTrue(component.isVisited());
409: return (0);
410: }
411: };
412:
413: builder().getGraph().visitNodes(visitor);
414:
415: assertTrue(walker.getCount() == (int) Math.pow(2, k + 1) - 1);
416: }
417:
418: /**
419: * Create a balanced binary tree and do a traversal starting at root and kill
420: * branch at the first node seen that is not the root, (should be left child).
421: * Then continue the traversal.
422: * <BR>
423: * <BR>
424: * Expected: After kill:
425: * 1. All nodes should be visited except for sub nodes of first
426: * child of root visited. (the kill node)
427: *
428: * After continue:
429: * 1. Same as after kill.
430: */
431: public void test_5() {
432: int k = 4;
433: Object[] obj = GraphTestUtil.buildPerfectBinaryTree(builder(),
434: k);
435: final Node root = (Node) obj[0];
436: final Map obj2node = (Map) obj[1];
437: final Node ln = (Node) obj2node.get(root.getObject().toString()
438: + ".0");
439: final Node rn = (Node) obj2node.get(root.getObject().toString()
440: + ".1");
441:
442: CountingWalker walker = new CountingWalker() {
443: private int m_mode = 0;
444:
445: public int visit(Graphable element, GraphTraversal traversal) {
446: element.setCount(getCount());
447: super .visit(element, traversal); //set count
448:
449: if (m_mode == 0) {
450: if (element != root) {
451: m_mode++;
452: return (GraphTraversal.KILL_BRANCH);
453: }
454: } else if (m_mode == 1) {
455: assertTrue((ln.isVisited() && element == rn)
456: || (rn.isVisited() && element == ln));
457: m_mode++;
458: }
459:
460: return (GraphTraversal.CONTINUE);
461: }
462: };
463:
464: DepthFirstIterator iterator = createIterator();
465: BasicGraphTraversal traversal = new BasicGraphTraversal(
466: builder().getGraph(), walker, iterator);
467: traversal.init();
468:
469: iterator.setSource(root);
470: traversal.traverse();
471:
472: //ensure that subnodes of first visited after root are not visited
473: final String id = (ln.getCount() < rn.getCount()) ? ln
474: .getObject().toString() : rn.getObject().toString();
475:
476: GraphVisitor visitor = new GraphVisitor() {
477: public int visit(Graphable component) {
478: String eid = component.getObject().toString();
479: if (eid.length() <= id.length())
480: assertTrue(component.isVisited());
481: else if (eid.startsWith(id))
482: assertTrue(!component.isVisited());
483: else
484: assertTrue(component.isVisited());
485:
486: return (0);
487: }
488: };
489: builder().getGraph().visitNodes(visitor);
490: assertTrue(walker.getCount() == (int) Math.pow(2, k) + 1);
491:
492: traversal.traverse();
493:
494: builder().getGraph().visitNodes(visitor);
495: assertTrue(walker.getCount() == (int) Math.pow(2, k) + 1);
496: }
497:
498: /**
499: * Create a graph that contains a cycle and do a full traversal.<BR>
500: * <BR>
501: * Expected: 1. All nodes visited.
502: */
503: public void test_6() {
504: int nnodes = 100;
505: GraphTestUtil.buildCircular(builder(), nnodes);
506: GraphVisitor visitor = new GraphVisitor() {
507: public int visit(Graphable component) {
508: if (component.getID() == 50)
509: return (Graph.PASS_AND_CONTINUE);
510: return (Graph.FAIL_QUERY);
511: }
512: };
513: Node source = (Node) builder().getGraph().queryNodes(visitor)
514: .get(0);
515:
516: CountingWalker walker = new CountingWalker();
517: DepthFirstIterator iterator = createIterator();
518:
519: BasicGraphTraversal traversal = new BasicGraphTraversal(
520: builder().getGraph(), walker, iterator);
521: traversal.init();
522:
523: iterator.setSource(source);
524: traversal.traverse();
525:
526: //ensure all nodes visisited
527: visitor = new GraphVisitor() {
528: public int visit(Graphable component) {
529: assertTrue(component.isVisited());
530: return (0);
531: }
532: };
533: builder().getGraph().visitNodes(visitor);
534:
535: assertTrue(walker.getCount() == nnodes);
536: }
537:
538: protected DepthFirstIterator createIterator() {
539: return (new DepthFirstIterator());
540: }
541:
542: protected GraphBuilder createBuilder() {
543: return (new BasicGraphBuilder());
544: }
545:
546: protected GraphBuilder builder() {
547: return (m_builder);
548: }
549: }
|