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: import java.util.Map;
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.Graph;
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 BreadthFirstIteratorTest extends TestCase {
036:
037: private GraphBuilder m_builder;
038:
039: public BreadthFirstIteratorTest(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: element.setCount(getCount());
064: super .visit(element, traversal);
065:
066: //nodes should be visited in order
067: assertTrue(element.getID() == getCount() - 1);
068: return (GraphTraversal.CONTINUE);
069: }
070: };
071:
072: BreadthFirstIterator iterator = createIterator();
073: BasicGraphTraversal traversal = new BasicGraphTraversal(
074: builder().getGraph(), walker, iterator);
075: traversal.init();
076:
077: iterator.setSource(ends[0]);
078: traversal.traverse();
079:
080: //every node should have been visited
081: assertTrue(walker.getCount() == builder().getGraph().getNodes()
082: .size());
083:
084: //ensure nodes only visited once
085: assertTrue(walker.getCount() == nnodes);
086:
087: }
088:
089: /**
090: * Create a simple graph which has no bifurcations and do a traversal
091: * suspending at some intermediate node. Then continue traversal.
092: *
093: * Expected: After suspend:
094: * 1. Every node of with an id greater than the id of the suspending
095: * node should not be visited.
096: * After continue:
097: * 1. First node visited after continue should have id =
098: * id + suspend node + 1
099: * 2. Every node should be visited.
100: */
101: public void test_1() {
102: int nnodes = 100;
103: Node[] ends = GraphTestUtil.buildNoBifurcations(builder(),
104: nnodes);
105: final int suspend = 50;
106:
107: CountingWalker walker = new CountingWalker() {
108: private int m_mode = 0;
109:
110: public int visit(Graphable element, GraphTraversal traversal) {
111: super .visit(element, traversal);
112: if (m_mode == 0) {
113: //check for stopping node
114: if (element.getID() == suspend) {
115: m_mode++;
116: return (GraphTraversal.SUSPEND);
117: }
118: } else if (m_mode == 1) {
119: //check first node after continue
120: assertTrue(element.getID() == suspend + 1);
121: m_mode++;
122: }
123: return (GraphTraversal.CONTINUE);
124: }
125: };
126:
127: BreadthFirstIterator iterator = createIterator();
128: BasicGraphTraversal traversal = new BasicGraphTraversal(
129: builder().getGraph(), walker, iterator);
130: traversal.init();
131:
132: iterator.setSource(ends[0]);
133: traversal.traverse();
134:
135: //ensure nodes only visited once
136: assertTrue(walker.getCount() == nnodes - suspend + 1);
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: traversal.traverse();
151:
152: //every node should now be visited
153: visitor = new GraphVisitor() {
154: public int visit(Graphable component) {
155: assertTrue(component.isVisited());
156: return (0);
157: }
158: };
159: builder().getGraph().visitNodes(visitor);
160:
161: //ensure nodes only visited once
162: assertTrue(walker.getCount() == nnodes);
163: }
164:
165: /**
166: * Create a simple graph which has no bifurcations and do a kill branch at
167: * some intermediate node. Then continue the traversal.
168: *
169: * Expected: After kill:
170: * 1. Every node of with an id greater than the id of the killing
171: * node should not be visited.
172: * After continue:
173: * 2. No more nodes should be visited.
174: *
175: */
176: public void test_2() {
177: int nnodes = 100;
178: Node[] ends = GraphTestUtil.buildNoBifurcations(builder(),
179: nnodes);
180: final int kill = 50;
181:
182: CountingWalker walker = new CountingWalker() {
183: private int m_mode = 0;
184:
185: public int visit(Graphable element, GraphTraversal traversal) {
186: super .visit(element, traversal);
187: if (m_mode == 0) {
188: //check for stopping node
189: if (element.getID() == kill) {
190: m_mode++;
191: return (GraphTraversal.KILL_BRANCH);
192: }
193: } else if (m_mode == 1) {
194: //should never get here
195: assertTrue(false);
196: }
197: return (GraphTraversal.CONTINUE);
198: }
199: };
200:
201: BreadthFirstIterator iterator = createIterator();
202: BasicGraphTraversal traversal = new BasicGraphTraversal(
203: builder().getGraph(), walker, iterator);
204: traversal.init();
205:
206: iterator.setSource(ends[0]);
207: traversal.traverse();
208:
209: //kill node should be visited and nodes with greater id should not
210: GraphVisitor visitor = new GraphVisitor() {
211: public int visit(Graphable component) {
212: if (component.getID() <= kill)
213: assertTrue(component.isVisited());
214: else
215: assertTrue(!component.isVisited());
216: return (0);
217: }
218: };
219: builder().getGraph().visitNodes(visitor);
220:
221: //ensure nodes only visited once
222: assertTrue(walker.getCount() == nnodes - kill + 1);
223:
224: //continue, no more nodes should be visited
225:
226: traversal.traverse();
227:
228: //ensure nodes only visited once
229: assertTrue(walker.getCount() == nnodes - kill + 1);
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 level in the tree, each node in the level should
238: * be visited before any node in a lower level
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: BreadthFirstIterator 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: int level = component.getObject().toString().length();
275:
276: //check all nodes that are at a lower level in the tree
277: for (Iterator itr = builder().getGraph().getNodes()
278: .iterator(); itr.hasNext();) {
279: Node other = (Node) itr.next();
280: if (other.getObject().toString().length() > level)
281: assertTrue(other.getCount() > component
282: .getCount());
283:
284: }
285: return 0;
286: }
287: };
288:
289: builder().getGraph().visitNodes(visitor);
290:
291: //ensure nodes visited once
292: assertTrue(walker.getCount() == Math.pow(2, k + 1) - 1);
293: }
294:
295: /**
296: * Create a balanced binary tree and do a traversal starting at root and
297: * suspending at the first node seen that is not the root, (should be left
298: * child). Then continue the traversal.
299: * <BR>
300: * <BR>
301: * Expected: After suspend:
302: * 1. Only root and first non root should be visited.
303: *
304: * After continue:
305: * 1. First node visited should be sibling of suspending node.
306: * 2. Every node should be visited.
307: */
308: public void test_4() {
309: int k = 4;
310: Object[] obj = GraphTestUtil.buildPerfectBinaryTree(builder(),
311: k);
312: final Node root = (Node) obj[0];
313: final Map obj2node = (Map) obj[1];
314: final Node ln = (Node) obj2node.get(root.getObject().toString()
315: + ".0");
316: final Node rn = (Node) obj2node.get(root.getObject().toString()
317: + ".1");
318:
319: CountingWalker walker = new CountingWalker() {
320: private int m_mode = 0;
321:
322: public int visit(Graphable element, GraphTraversal traversal) {
323: super .visit(element, traversal);
324: if (m_mode == 0) {
325: if (element != root) {
326: //check which child of root was first visited
327: m_mode++;
328: return (GraphTraversal.SUSPEND);
329: }
330: } else if (m_mode == 1) {
331: String eid = element.getObject().toString();
332: if (ln.isVisited())
333: assertTrue(element == rn);
334: else
335: assertTrue(element == ln);
336:
337: m_mode++;
338: }
339:
340: return (GraphTraversal.CONTINUE);
341: }
342: };
343:
344: BreadthFirstIterator iterator = createIterator();
345: BasicGraphTraversal traversal = new BasicGraphTraversal(
346: builder().getGraph(), walker, iterator);
347: traversal.init();
348:
349: iterator.setSource(root);
350: traversal.traverse();
351:
352: //ensure that only root and one of children is visited
353: assertTrue(root.isVisited());
354: assertTrue((rn.isVisited() && !ln.isVisited())
355: || (!rn.isVisited() && ln.isVisited()));
356:
357: GraphVisitor visitor = new GraphVisitor() {
358: public int visit(Graphable component) {
359: if (component != root && component != ln
360: && component != rn) {
361: assertTrue(!component.isVisited());
362: }
363: return (0);
364: }
365: };
366: builder().getGraph().visitNodes(visitor);
367:
368: //ensure nodes only visited once
369: assertTrue(walker.getCount() == 2);
370:
371: traversal.traverse();
372:
373: //ensure all nodes visited
374: visitor = new GraphVisitor() {
375: public int visit(Graphable component) {
376: assertTrue(component.isVisited());
377: return (0);
378: }
379: };
380:
381: builder().getGraph().visitNodes(visitor);
382:
383: //ensure nodes visited once
384: //ensure nodes only visited once
385: assertTrue(walker.getCount() == (int) Math.pow(2, k + 1) - 1);
386: }
387:
388: /**
389: * Create a balanced binary tree and do a traversal starting at root and kill
390: * branch at the first node seen that is not the root, (should be left child).
391: * Then continue the traversal.
392: * <BR>
393: * <BR>
394: * Expected: After kill:
395: * 1. All nodes should be visited except for sub nodes of first
396: * child of root visited. (the kill node)
397: *
398: * After continue:
399: * 1. Same as after kill.
400: */
401: public void test_5() {
402: int k = 4;
403: Object[] obj = GraphTestUtil.buildPerfectBinaryTree(builder(),
404: k);
405: final Node root = (Node) obj[0];
406: final Map obj2node = (Map) obj[1];
407: final Node ln = (Node) obj2node.get(root.getObject().toString()
408: + ".0");
409: final Node rn = (Node) obj2node.get(root.getObject().toString()
410: + ".1");
411:
412: CountingWalker walker = new CountingWalker() {
413: private int m_mode = 0;
414:
415: public int visit(Graphable element, GraphTraversal traversal) {
416: super .visit(element, traversal); //set count
417: element.setCount(getCount() - 1);
418: if (m_mode == 0) {
419: if (element != root) {
420: m_mode++;
421: return (GraphTraversal.KILL_BRANCH);
422: }
423: } else if (m_mode == 1) {
424: assertTrue((ln.isVisited() && element == rn)
425: || (rn.isVisited() && element == ln));
426: m_mode++;
427: }
428:
429: return (GraphTraversal.CONTINUE);
430: }
431: };
432:
433: BreadthFirstIterator iterator = createIterator();
434: BasicGraphTraversal traversal = new BasicGraphTraversal(
435: builder().getGraph(), walker, iterator);
436: traversal.init();
437:
438: iterator.setSource(root);
439: traversal.traverse();
440:
441: //ensure that subnodes of first visited after root are not visited
442: final String id = (ln.getCount() < rn.getCount()) ? ln
443: .getObject().toString() : rn.getObject().toString();
444:
445: GraphVisitor visitor = new GraphVisitor() {
446: public int visit(Graphable component) {
447: String eid = component.getObject().toString();
448: if (eid.length() <= id.length())
449: assertTrue(component.isVisited());
450: else if (eid.startsWith(id))
451: assertTrue(!component.isVisited());
452: else
453: assertTrue(component.isVisited());
454:
455: return (0);
456: }
457: };
458: builder().getGraph().visitNodes(visitor);
459:
460: //ensure that nodes only visited once
461: assertTrue(walker.getCount() == (int) Math.pow(2, k) + 1);
462: traversal.traverse();
463:
464: builder().getGraph().visitNodes(visitor);
465:
466: //ensure that nodes only visited once
467: assertTrue(walker.getCount() == (int) Math.pow(2, k) + 1);
468: }
469:
470: /**
471: * Create a graph that contains a cycle and do a full traversal.<BR>
472: * <BR>
473: * Expected: 1. All nodes visited.
474: */
475: public void test_6() {
476: GraphTestUtil.buildCircular(builder(), 100);
477: GraphVisitor visitor = new GraphVisitor() {
478: public int visit(Graphable component) {
479: if (component.getID() == 50)
480: return (Graph.PASS_AND_CONTINUE);
481: return (Graph.FAIL_QUERY);
482: }
483: };
484: Node source = (Node) builder().getGraph().queryNodes(visitor)
485: .get(0);
486:
487: CountingWalker walker = new CountingWalker();
488: BreadthFirstIterator iterator = createIterator();
489:
490: BasicGraphTraversal traversal = new BasicGraphTraversal(
491: builder().getGraph(), walker, iterator);
492: traversal.init();
493:
494: iterator.setSource(source);
495: traversal.traverse();
496:
497: //ensure all nodes visisited
498: visitor = new GraphVisitor() {
499: public int visit(Graphable component) {
500: assertTrue(component.isVisited());
501: return (0);
502: }
503: };
504:
505: builder().getGraph().visitNodes(visitor);
506:
507: //ensure all nodes only visitied once
508: assertTrue(walker.getCount() == builder().getGraph().getNodes()
509: .size());
510: }
511:
512: protected GraphBuilder createBuilder() {
513: return (new BasicGraphBuilder());
514: }
515:
516: protected GraphBuilder builder() {
517: return (m_builder);
518: }
519:
520: protected BreadthFirstIterator createIterator() {
521: return (new BreadthFirstIterator());
522: }
523:
524: }
|