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 DepthFirstTopologicalIteratorTest extends TestCase {
034: private GraphBuilder m_builder;
035:
036: public DepthFirstTopologicalIteratorTest(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 from one end to other in order.
050: */
051: public void test_0() {
052: int nnodes = 100;
053: GraphTestUtil.buildNoBifurcations(builder(), nnodes);
054:
055: CountingWalker walker = new CountingWalker() {
056: public int visit(Graphable element, GraphTraversal traversal) {
057: element.setCount(getCount());
058: return super .visit(element, traversal);
059: }
060: };
061: DepthFirstTopologicalIterator iterator = createIterator();
062: BasicGraphTraversal traversal = new BasicGraphTraversal(
063: builder().getGraph(), walker, iterator);
064: traversal.init();
065: traversal.traverse();
066:
067: assertTrue(walker.getCount() == nnodes);
068:
069: boolean flip = false;
070:
071: for (Iterator itr = builder().getGraph().getNodes().iterator(); itr
072: .hasNext();) {
073: Node node = (Node) itr.next();
074: if (node.getID() == 0 && node.getCount() != 0) {
075: flip = true;
076: break;
077: }
078: }
079:
080: for (Iterator itr = builder().getGraph().getNodes().iterator(); itr
081: .hasNext();) {
082: Node node = (Node) itr.next();
083: if (flip)
084: assertTrue(node.getCount() == 100 - 1 - node.getID());
085: else
086: assertTrue(node.getCount() == node.getID());
087: }
088: }
089:
090: /**
091: * Create a circular graph and do a full traversal. <BR>
092: * <BR>
093: * Expected: 1. No nodes should be visited.
094: *
095: */
096: public void test_1() {
097: int nnodes = 100;
098: GraphTestUtil.buildCircular(builder(), nnodes);
099:
100: CountingWalker walker = new CountingWalker();
101: BreadthFirstTopologicalIterator iterator = createIterator();
102:
103: BasicGraphTraversal traversal = new BasicGraphTraversal(
104: builder().getGraph(), walker, iterator);
105: traversal.init();
106: traversal.traverse();
107:
108: GraphVisitor visitor = new GraphVisitor() {
109: public int visit(Graphable component) {
110: assertTrue(!component.isVisited());
111: return 0;
112: }
113: };
114: builder().getGraph().visitNodes(visitor);
115:
116: assertTrue(walker.getCount() == 0);
117: }
118:
119: protected GraphBuilder createBuilder() {
120: return (new BasicGraphBuilder());
121: }
122:
123: protected GraphBuilder builder() {
124: return (m_builder);
125: }
126:
127: protected DepthFirstTopologicalIterator createIterator() {
128: return (new DepthFirstTopologicalIterator());
129: }
130: }
|