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 org.geotools.graph.structure.Graph;
020: import org.geotools.graph.structure.Graphable;
021: import org.geotools.graph.traverse.GraphTraversal;
022: import org.geotools.graph.traverse.GraphWalker;
023: import org.geotools.graph.traverse.basic.BasicGraphTraversal;
024: import org.geotools.graph.traverse.standard.DijkstraIterator;
025: import org.geotools.graph.traverse.standard.DijkstraIterator.EdgeWeighter;
026:
027: /**
028: * Calculates node paths in a graph using Dijkstra's Shortest Path Algorithm.
029: * Dijsktras algorithm calculates a shortest path from a specefied node (the
030: * source node of the underlying dijkstra iteration) to every other node in the
031: * graph.
032: *
033: * @see DijsktraIterator
034: * @author Justin Deoliveira, Refractions Research Inc, jdeolive@refractions.net
035: *
036: * @source $URL: http://svn.geotools.org/geotools/tags/2.4.1/modules/extension/graph/src/main/java/org/geotools/graph/path/DijkstraShortestPathFinder.java $
037: */
038: public class DijkstraShortestPathFinder implements GraphWalker {
039:
040: /** Graphs to calculate paths for **/
041: private Graph m_graph;
042:
043: /** Graph traversal used for the dijkstra iteration **/
044: private GraphTraversal m_traversal;
045:
046: /** Underling Dijkstra iterator **/
047: private DijkstraIterator m_iterator;
048:
049: /**
050: * Constructs a new path finder.
051: *
052: * @param graph The graph to calculate paths for.
053: * @param iterator The dijsktra iterator to used to calculate shortest paths.
054: */
055: public DijkstraShortestPathFinder(Graph graph,
056: DijkstraIterator iterator) {
057: m_graph = graph;
058: m_iterator = iterator;
059: m_traversal = new BasicGraphTraversal(graph, this , iterator);
060: }
061:
062: /**
063: * Constructs a new path finder.
064: *
065: * @param graph Graph to calculate paths for.
066: * @param source Node to calculate paths from.
067: * @param weighter Associates weights with edges in the graph.
068: */
069: public DijkstraShortestPathFinder(Graph graph, Graphable source,
070: EdgeWeighter weighter) {
071: m_graph = graph;
072: m_iterator = new DijkstraIterator(weighter);
073: m_iterator.setSource(source);
074: m_traversal = new BasicGraphTraversal(graph, this , m_iterator);
075: }
076:
077: /**
078: * Performs the graph traversal and calculates the shortest path from
079: * the source node to every other node in the graph.
080: */
081: public void calculate() {
082: m_traversal.init();
083: m_traversal.traverse();
084: }
085:
086: /**
087: * Returns a path <B>from</B> g <B>to</B> the source. If the desired path is
088: * the opposite (from the source to g) can be used.
089: *
090: * @param g The start node of the path to be calculated.
091: *
092: * @see Path#riterator()
093: *
094: * @return A path from g to the source.
095: */
096: public Path getPath(Graphable g) {
097: Path p = new Path();
098: p.add(g);
099:
100: Graphable parent = g;
101: while ((parent = m_iterator.getParent(parent)) != null)
102: p.add(parent);
103:
104: if (!p.getLast().equals(m_iterator.getSource()))
105: return (null);
106:
107: return (p);
108: }
109:
110: /**
111: * Returns the cost associated with a node calculated during the graph
112: * traversal.
113: *
114: * @param g The node whose cost is desired.
115: *
116: * @return The cost associated with the node.
117: */
118: public double getCost(Graphable g) {
119: return (m_iterator.getCost(g));
120: }
121:
122: public DijkstraIterator getIterator() {
123: return (m_iterator);
124: }
125:
126: public GraphTraversal getTraversal() {
127: return (m_traversal);
128: }
129:
130: /**
131: * Does nothing except signal the traversal to continue.
132: *
133: * @see GraphWalker#visit(Graphable, GraphTraversal)
134: */
135: public int visit(Graphable element, GraphTraversal traversal) {
136: return (GraphTraversal.CONTINUE);
137: }
138:
139: /**
140: * Does nothing.
141: *
142: * @see GraphWalker#finish()
143: */
144: public void finish() {
145: }
146: }
|