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.path;
018:
019: import java.util.ArrayList;
020: import java.util.Iterator;
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.Graphable;
029: import org.geotools.graph.structure.Node;
030: import org.geotools.graph.traverse.GraphTraversal;
031: import org.geotools.graph.traverse.GraphWalker;
032: import org.geotools.graph.traverse.basic.BasicGraphTraversal;
033: import org.geotools.graph.traverse.standard.NoBifurcationIterator;
034:
035: public class WalkTest extends TestCase {
036:
037: private GraphBuilder m_builder;
038:
039: public WalkTest(String name) {
040: super (name);
041: }
042:
043: protected void setUp() throws Exception {
044: super .setUp();
045: m_builder = createBuilder();
046: }
047:
048: public void test_add() {
049: Node n = builder().buildNode();
050: Walk walk = new Walk();
051:
052: walk.add(n);
053:
054: assertTrue(walk.size() == 1);
055: assertTrue(walk.get(0).equals(n));
056: }
057:
058: public void test_remove() {
059: Node n = builder().buildNode();
060: Walk walk = new Walk();
061:
062: walk.add(n);
063: assertTrue(!walk.isEmpty());
064:
065: walk.remove(n);
066: assertTrue(walk.isEmpty());
067: }
068:
069: public void test_reverse() {
070: ArrayList nodes = new ArrayList();
071: Walk walk = new Walk();
072:
073: for (int i = 0; i < 10; i++) {
074: Node n = builder().buildNode();
075: nodes.add(n);
076: walk.add(n);
077: }
078:
079: Iterator itr = walk.iterator();
080: for (int i = 0; i < nodes.size(); i++) {
081: Node n1 = (Node) nodes.get(i);
082: Node n2 = (Node) itr.next();
083:
084: assertTrue(n1 == n2);
085: }
086:
087: walk.reverse();
088: itr = walk.iterator();
089:
090: for (int i = nodes.size() - 1; i >= 0; i--) {
091: Node n1 = (Node) nodes.get(i);
092: Node n2 = (Node) itr.next();
093:
094: assertTrue(n1 == n2);
095: }
096: }
097:
098: public void test_isClosed() {
099: Node[] ends = GraphTestUtil.buildNoBifurcations(builder(), 10);
100: final Walk walk = new Walk();
101:
102: NoBifurcationIterator iterator = new NoBifurcationIterator();
103: iterator.setSource(ends[0]);
104:
105: GraphWalker walker = new GraphWalker() {
106: public int visit(Graphable element, GraphTraversal traversal) {
107: walk.add(element);
108: return (GraphTraversal.CONTINUE);
109: }
110:
111: public void finish() {
112:
113: }
114: };
115:
116: BasicGraphTraversal traversal = new BasicGraphTraversal(
117: builder().getGraph(), walker, iterator);
118: traversal.init();
119: traversal.traverse();
120:
121: assertTrue(walk.size() == builder().getGraph().getNodes()
122: .size());
123: assertTrue(walk.isValid() && !walk.isClosed());
124:
125: //create a new edges in the graph making the graph a cycle
126: Edge e = builder().buildEdge(ends[0], ends[1]);
127: builder().addEdge(e);
128:
129: walk.add(ends[0]);
130: assertTrue(walk.isValid() && walk.isClosed());
131: }
132:
133: public void test_getEdges() {
134: Node[] ends = GraphTestUtil.buildNoBifurcations(builder(), 10);
135: final Walk walk = new Walk();
136:
137: NoBifurcationIterator iterator = new NoBifurcationIterator();
138: iterator.setSource(ends[0]);
139:
140: GraphWalker walker = new GraphWalker() {
141: public int visit(Graphable element, GraphTraversal traversal) {
142: walk.add(element);
143: return (GraphTraversal.CONTINUE);
144: }
145:
146: public void finish() {
147:
148: }
149: };
150:
151: BasicGraphTraversal traversal = new BasicGraphTraversal(
152: builder().getGraph(), walker, iterator);
153: traversal.init();
154: traversal.traverse();
155:
156: assertTrue(walk.getEdges() != null);
157: assertTrue(walk.isValid());
158: }
159:
160: public void test_truncate_0() {
161: Node[] ends = GraphTestUtil.buildNoBifurcations(builder(), 10);
162: final Walk walk = new Walk();
163:
164: NoBifurcationIterator iterator = new NoBifurcationIterator();
165: iterator.setSource(ends[0]);
166:
167: GraphWalker walker = new GraphWalker() {
168: public int visit(Graphable element, GraphTraversal traversal) {
169: walk.add(element);
170: return (GraphTraversal.CONTINUE);
171: }
172:
173: public void finish() {
174:
175: }
176: };
177:
178: BasicGraphTraversal traversal = new BasicGraphTraversal(
179: builder().getGraph(), walker, iterator);
180: traversal.init();
181: traversal.traverse();
182:
183: walk.truncate(0);
184: assertTrue(walk.isEmpty());
185: assertTrue(walk.isValid());
186: }
187:
188: public void test_truncate_1() {
189: Node[] ends = GraphTestUtil.buildNoBifurcations(builder(), 10);
190: final Walk walk = new Walk();
191:
192: NoBifurcationIterator iterator = new NoBifurcationIterator();
193: iterator.setSource(ends[0]);
194:
195: GraphWalker walker = new GraphWalker() {
196: int count = 0;
197:
198: public int visit(Graphable element, GraphTraversal traversal) {
199: walk.add(element);
200: return (GraphTraversal.CONTINUE);
201: }
202:
203: public void finish() {
204:
205: }
206: };
207:
208: BasicGraphTraversal traversal = new BasicGraphTraversal(
209: builder().getGraph(), walker, iterator);
210: traversal.init();
211: traversal.traverse();
212:
213: int size = walk.size();
214: walk.truncate(size / 2);
215: assertTrue(walk.size() == size / 2);
216: }
217:
218: public void test_truncate_2() {
219: Node[] ends = GraphTestUtil.buildNoBifurcations(builder(), 11);
220: final Walk walk = new Walk();
221:
222: NoBifurcationIterator iterator = new NoBifurcationIterator();
223: iterator.setSource(ends[0]);
224:
225: GraphWalker walker = new GraphWalker() {
226: int count = 0;
227:
228: public int visit(Graphable element, GraphTraversal traversal) {
229: walk.add(element);
230: return (GraphTraversal.CONTINUE);
231: }
232:
233: public void finish() {
234:
235: }
236: };
237:
238: BasicGraphTraversal traversal = new BasicGraphTraversal(
239: builder().getGraph(), walker, iterator);
240: traversal.init();
241: traversal.traverse();
242:
243: int size = walk.size();
244: walk.truncate(size / 2);
245: assertTrue(walk.size() == size / 2);
246: }
247:
248: protected GraphBuilder createBuilder() {
249: return (new BasicGraphBuilder());
250: }
251:
252: protected GraphBuilder builder() {
253: return (m_builder);
254: }
255:
256: }
|