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.util;
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.path.DijkstraShortestPathFinder;
028: import org.geotools.graph.path.Path;
029: import org.geotools.graph.structure.Edge;
030: import org.geotools.graph.structure.Node;
031: import org.geotools.graph.traverse.standard.DijkstraIterator;
032:
033: public class DijkstraShortestPathFinderTest extends TestCase {
034:
035: private GraphBuilder m_builder;
036:
037: public DijkstraShortestPathFinderTest(String name) {
038: super (name);
039: }
040:
041: protected void setUp() throws Exception {
042: super .setUp();
043:
044: m_builder = createBuilder();
045: }
046:
047: /**
048: * Create a graph with no bifurcations and calculate path from beginning
049: * to end. <BR>
050: * <BR>
051: * Expected: 1. Path should contain every node in graph in order.
052: */
053: public void test_0() {
054: int nnodes = 100;
055: Node[] ends = GraphTestUtil.buildNoBifurcations(builder(),
056: nnodes);
057: DijkstraShortestPathFinder pfinder = new DijkstraShortestPathFinder(
058: builder().getGraph(), ends[0], costFunction());
059:
060: pfinder.calculate();
061: Path p = pfinder.getPath(ends[1]);
062:
063: int count = 99;
064: for (Iterator itr = p.iterator(); itr.hasNext();) {
065: Node n = (Node) itr.next();
066: assertTrue(n.getID() == count--);
067: }
068: }
069:
070: /**
071: * Create a circular graph and calculate a path from beginning to end. <BR>
072: * <BR>
073: * Expected: 1. Path should just contain end nodes.
074: *
075: */
076: public void test_1() {
077: int nnodes = 100;
078: Node[] ends = GraphTestUtil.buildCircular(builder(), nnodes);
079:
080: DijkstraShortestPathFinder pfinder = new DijkstraShortestPathFinder(
081: builder().getGraph(), ends[0], costFunction());
082:
083: pfinder.calculate();
084: Path p = pfinder.getPath(ends[1]);
085:
086: assertTrue(p.size() == 2);
087: assertTrue(p.get(0) == ends[1]);
088: assertTrue(p.get(1) == ends[0]);
089: }
090:
091: /**
092: * Create a balanced binary tree and calculate a path from root to a leaf. <BR>
093: * <BR>
094: * Expected 1. Path should be links from leaf to root.
095: */
096: public void test_2() {
097: int k = 4;
098: Object[] obj = GraphTestUtil.buildPerfectBinaryTree(builder(),
099: k);
100: Node root = (Node) obj[0];
101: Map id2node = (Map) obj[1];
102:
103: DijkstraShortestPathFinder pfinder = new DijkstraShortestPathFinder(
104: builder().getGraph(), root, costFunction());
105: pfinder.calculate();
106:
107: for (Iterator itr = builder().getGraph().getNodes().iterator(); itr
108: .hasNext();) {
109: Node node = (Node) itr.next();
110: String id = node.getObject().toString();
111:
112: if (id2node.get(id + ".0") == null) {
113: Path p = pfinder.getPath(node);
114: assertTrue(p.size() == k + 1);
115:
116: for (Iterator pitr = p.iterator(); pitr.hasNext();) {
117: Node n = (Node) pitr.next();
118: assertTrue(n.getObject().toString().equals(id));
119: if (id.length() > 2)
120: id = id.substring(0, id.length() - 2);
121: }
122: }
123: }
124: }
125:
126: protected DijkstraIterator.EdgeWeighter costFunction() {
127: return (new DijkstraIterator.EdgeWeighter() {
128: public double getWeight(Edge e) {
129: return 1;
130: }
131: });
132: }
133:
134: protected GraphBuilder createBuilder() {
135: return (new BasicGraphBuilder());
136: }
137:
138: protected GraphBuilder builder() {
139: return (m_builder);
140: }
141:
142: }
|