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:
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.GraphVisitor;
027: import org.geotools.graph.structure.Graphable;
028: import org.geotools.graph.structure.Node;
029: import org.geotools.graph.traverse.GraphTraversal;
030: import org.geotools.graph.traverse.basic.BasicGraphTraversal;
031: import org.geotools.graph.traverse.basic.CountingWalker;
032:
033: public class BreadthFirstTopologicalIteratorTest extends TestCase {
034: private GraphBuilder m_builder;
035:
036: public BreadthFirstTopologicalIteratorTest(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 graph with no bifurcations and do a full traversal. <BR>
048: * <BR>
049: * Expected: 1. Nodes should be visited in order (1,n,2,n-2,...n/2). This
050: * order can be reversed.
051: */
052: public void test_0() {
053: int nnodes = 9;
054: //odd number so there is a middle node
055: GraphTestUtil.buildNoBifurcations(builder(), nnodes);
056:
057: //note: traversal uses count and we are changing the count value here.
058: // but it shouldn't matter because at the time of visitation, the traversal
059: // no longer needs the counter value.
060: CountingWalker walker = new CountingWalker() {
061: public int visit(Graphable element, GraphTraversal traversal) {
062: element.setCount(getCount());
063: return super .visit(element, traversal);
064: }
065: };
066:
067: BreadthFirstTopologicalIterator iterator = createIterator();
068: BasicGraphTraversal traversal = new BasicGraphTraversal(
069: builder().getGraph(), walker, iterator);
070: traversal.init();
071: traversal.traverse();
072:
073: assertTrue(walker.getCount() == nnodes);
074:
075: boolean flip = false;
076: for (Iterator itr = builder().getGraph().getNodes().iterator(); itr
077: .hasNext();) {
078: Node node = (Node) itr.next();
079: if (node.getID() == 0 && node.getCount() != 0) {
080: flip = true;
081: break;
082: }
083: }
084: final int size = builder().getGraph().getNodes().size();
085:
086: for (Iterator itr = builder().getGraph().getNodes().iterator(); itr
087: .hasNext();) {
088: Node node = (Node) itr.next();
089: int id = node.getID();
090: int expected = -1;
091:
092: if (id == (int) size / 2)
093: expected = size - 1;
094: else if (id < (int) size / 2) {
095: if (!flip) {
096: expected = id * 2;
097: } else {
098: expected = id * 2 + 1;
099: }
100: } else {
101: if (!flip) {
102: expected = (size - 1 - id) * 2 + 1;
103: } else {
104: expected = (size - 1 - id) * 2;
105: }
106: }
107:
108: assertTrue(expected == node.getCount());
109: }
110: ;
111: }
112:
113: /**
114: * Create a balanced binary tree and do a full traversal. <BR>
115: * <BR>
116: * Expected: 1. Nodes in a lower level of the tree should be visited before
117: * nodes in a higher level.
118: */
119: public void test_1() {
120: int k = 4;
121: GraphTestUtil.buildPerfectBinaryTree(builder(), k);
122:
123: CountingWalker walker = new CountingWalker() {
124: public int visit(Graphable element, GraphTraversal traversal) {
125: element.setCount(getCount());
126: return super .visit(element, traversal);
127: }
128: };
129:
130: BreadthFirstTopologicalIterator iterator = createIterator();
131:
132: BasicGraphTraversal traversal = new BasicGraphTraversal(
133: builder().getGraph(), walker, iterator);
134: traversal.init();
135: traversal.traverse();
136:
137: //ensure that each node in lower level visited before node in higher level
138: GraphVisitor visitor = new GraphVisitor() {
139: public int visit(Graphable component) {
140: String id = component.getObject().toString();
141:
142: for (Iterator itr = builder().getGraph().getNodes()
143: .iterator(); itr.hasNext();) {
144: Node other = (Node) itr.next();
145: if (other.getObject().toString().length() < id
146: .length()) {
147: assertTrue(other.getCount() > component
148: .getCount());
149: }
150: }
151: return 0;
152: }
153: };
154: builder().getGraph().visitNodes(visitor);
155:
156: assertTrue(walker.getCount() == Math.pow(2, k + 1) - 1);
157: }
158:
159: /**
160: * Create a circular graph and do a full traversal. <BR>
161: * <BR>
162: * Expected: 1. No nodes should be visited.
163: *
164: */
165: public void test_2() {
166: int nnodes = 100;
167: GraphTestUtil.buildCircular(builder(), nnodes);
168:
169: CountingWalker walker = new CountingWalker();
170: BreadthFirstTopologicalIterator iterator = createIterator();
171:
172: BasicGraphTraversal traversal = new BasicGraphTraversal(
173: builder().getGraph(), walker, iterator);
174: traversal.init();
175: traversal.traverse();
176:
177: GraphVisitor visitor = new GraphVisitor() {
178: public int visit(Graphable component) {
179: assertTrue(!component.isVisited());
180: return 0;
181: }
182: };
183: builder().getGraph().visitNodes(visitor);
184:
185: assertTrue(walker.getCount() == 0);
186: }
187:
188: protected GraphBuilder createBuilder() {
189: return (new BasicGraphBuilder());
190: }
191:
192: protected GraphBuilder builder() {
193: return (m_builder);
194: }
195:
196: protected BreadthFirstTopologicalIterator createIterator() {
197: return (new BreadthFirstTopologicalIterator());
198: }
199: }
|