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.Comparator;
020: import java.util.HashMap;
021: import java.util.Iterator;
022:
023: import org.geotools.graph.structure.Edge;
024: import org.geotools.graph.structure.Graph;
025: import org.geotools.graph.structure.GraphVisitor;
026: import org.geotools.graph.structure.Graphable;
027: import org.geotools.graph.structure.Node;
028: import org.geotools.graph.traverse.GraphTraversal;
029: import org.geotools.graph.traverse.basic.SourceGraphIterator;
030: import org.geotools.graph.util.PriorityQueue;
031:
032: /**
033: * Iterates over the nodes of a graph in pattern using <B>Dijkstra's
034: * Shortest Path Algorithm</B>. A Dijkstra iteration returns nodes
035: * in an order of increasing cost relative to a specified node
036: * (the source node of the iteration).<BR>
037: * <BR>
038: * In a Dijsktra iteration, a <B>weight</B> is associated with each edge
039: * and a <B>cost</B> with each node. The iteration operates by maintaining
040: * two sets of nodes. The first the set of nodes whose final cost is known, and
041: * the second is the set of nodes whose final cost is unknown.
042: * Initially, every node except for the source node has a cost of infinity, and
043: * resides in the unkown set. The source node has a cost of zero, and is
044: * is a member of the known set.<BR>
045: * <BR>
046: * The iteration operatates as follows:<BR>
047: * <PRE>
048: * sn = source node of iteration
049: * N = set of all nodes
050: * K = set of nodes with known cost = {sn}
051: * U = set of nodes with unknown cost = N - K
052: *
053: * cost(sn) = 0
054: * for each node $un in U
055: * cost(un) = infinity
056: *
057: * while(|U| > 0)
058: * for each node n in K
059: * find a node un in U that relates to n
060: * if cost(n) + weight(n,un) < cost(un)
061: * cost(un) = cost(n) + weight(n,un)
062: *
063: * ln = node with least cost in U
064: * remove ln from U
065: * add ln to K
066: *
067: * return ln as next node in iteration
068: * </PRE>
069: * The following is an illustration of the algorithm. Edge weights are labelled
070: * in blue and the final node costs are labelled in red.<BR>
071: * <IMG src="doc-files/dijkstra.gif"/>
072: * <BR>
073: * The nodes are returned in order of increasing cost which yields the sequence
074: * A,C,B,D,E,F,G,H,I.<BR>
075: *
076: * @author Justin Deoliveira, Refractions Research Inc, jdeolive@refractions.net
077: *
078: * @source $URL: http://svn.geotools.org/geotools/tags/2.4.1/modules/extension/graph/src/main/java/org/geotools/graph/traverse/standard/DijkstraIterator.java $
079: */
080: public class DijkstraIterator extends SourceGraphIterator {
081:
082: /** compares two internal nodes used by the iteration by comparing costs **/
083: private static Comparator comparator = new Comparator() {
084: public int compare(Object o1, Object o2) {
085: DijkstraNode n1 = (DijkstraNode) o1;
086: DijkstraNode n2 = (DijkstraNode) o2;
087:
088: return (n1.cost < n2.cost ? -1 : n1.cost > n2.cost ? 1 : 0);
089: }
090: };
091:
092: /** provides weights for edges in the graph **/
093: private EdgeWeighter m_weighter;
094:
095: /** priority queue to manage active nodes **/
096: private PriorityQueue m_queue;
097:
098: /** map of graph node to internal dijkstra node **/
099: private HashMap m_nodemap;
100:
101: /**
102: * Constructs a new Dijkstra iterator which uses the specided EdgeWeighter.
103: *
104: * @param weighter Calculates weights for edges in the graph being iterated
105: * over.
106: */
107: public DijkstraIterator(EdgeWeighter weighter) {
108: m_weighter = weighter;
109: }
110:
111: /**
112: * Builds internal priority queue to manage node costs.
113: *
114: * @see org.geotools.graph.traverse.GraphIterator#init(Graph)
115: */
116: public void init(Graph graph, GraphTraversal traversal) {
117: //initialize data structures
118: m_nodemap = new HashMap();
119:
120: m_queue = new PriorityQueue(comparator);
121: m_queue.init(graph.getNodes().size());
122:
123: //place nodes into priority queue
124: graph.visitNodes(new GraphVisitor() {
125: public int visit(Graphable component) {
126: //create a dijkstra node with infinite cost
127: DijkstraNode dn = new DijkstraNode((Node) component,
128: Double.MAX_VALUE);
129:
130: //create the mapping
131: m_nodemap.put(component, dn);
132:
133: //source component gets a cost of 0
134: if (component == getSource())
135: dn.cost = 0d;
136:
137: //place into priority queue
138: m_queue.insert(dn);
139:
140: return 0;
141: }
142: });
143: }
144:
145: /**
146: * Returns the next node in the priority queue. If the next node coming out
147: * of the queue has infinite cost, then the node is not adjacent to any nodes
148: * in the set of nodes with known costs. This situation will end the traversal
149: * every other node will also have infinite cost. This usally is the result of
150: * a disconnected graph.
151: *
152: * @see org.geotools.graph.traverse.GraphIterator#next()
153: */
154: public Graphable next(GraphTraversal traversal) {
155: if (m_queue.isEmpty())
156: return (null);
157:
158: DijkstraNode next = (DijkstraNode) m_queue.extract();
159:
160: //check cost of node, if cost == infinity then return null
161: // because no node in the visited set ever updated the node
162: // since it is at the top of the heap it means no more nodes
163: // in the visited set will be visited
164: if (next.cost == Double.MAX_VALUE)
165: return (null);
166:
167: return (next.node);
168: }
169:
170: /**
171: * Looks for adjacent nodes to the current node which are in the adjacent
172: * node and updates costs.
173: *
174: * @see org.geotools.graph.traverse.GraphIterator#cont(Graphable)
175: */
176: public void cont(Graphable current, GraphTraversal traversal) {
177: DijkstraNode currdn = (DijkstraNode) m_nodemap.get(current);
178:
179: for (Iterator itr = getRelated(current); itr.hasNext();) {
180: Node related = (Node) itr.next();
181: if (!traversal.isVisited(related)) {
182: DijkstraNode reldn = (DijkstraNode) m_nodemap
183: .get(related);
184:
185: //calculate cost from current node to related node
186: double cost = m_weighter.getWeight(currdn.node
187: .getEdge(related))
188: + currdn.cost;
189:
190: //if cost less than current cost of related node, update
191: if (cost < reldn.cost) {
192: reldn.cost = cost;
193: reldn.parent = currdn;
194: m_queue.update(reldn);
195: }
196: }
197: }
198: }
199:
200: /**
201: * Kills the branch of the traversal by not updating the cost of any
202: * adjacent nodes.
203: *
204: * @see org.geotools.graph.traverse.GraphIterator#killBranch(Graphable)
205: */
206: public void killBranch(Graphable current, GraphTraversal traversal) {
207: //do nothing
208: }
209:
210: /**
211: * Returns the internal cost of a node which has been calculated by the
212: * iterator.
213: *
214: * @param component The component whose cost to return.
215: *
216: * @return The cost associated with the component.
217: */
218: public double getCost(Graphable component) {
219: return (((DijkstraNode) m_nodemap.get(component)).cost);
220: }
221:
222: /**
223: * Returns the last node in the known set to update the node. The iteration
224: * operates by nodes in the known set updating the cost of nodes in the
225: * unknown set. Each time an update occurs, the known node is set as the
226: * parent of the unkown node.
227: *
228: * @param component The node whose parent to return (child)
229: *
230: * @return The parent, or null if the method is supplied the source of the
231: * iteration.
232: */
233: public Graphable getParent(Graphable component) {
234: if (component.equals(getSource()))
235: return (null);
236: DijkstraNode dn = (DijkstraNode) m_nodemap.get(component);
237:
238: if (dn == null || dn.parent == null)
239: return (null);
240: return (dn.parent.node);
241:
242: //return(((DijkstraNode)m_nodemap.get(component)).parent.node);
243: }
244:
245: protected PriorityQueue getQueue() {
246: return (m_queue);
247: }
248:
249: protected Iterator getRelated(Graphable current) {
250: return (current.getRelated());
251: }
252:
253: /**
254: * Supplies a weight for each edge in the graph to be used by the iteration
255: * when calculating node costs.
256: *
257: * @author Justin Deoliveira, Refractions Research Inc, jdeolive@refractions.net
258: *
259: */
260: public static interface EdgeWeighter {
261:
262: /**
263: * Returns the weight for the associated edge.
264: *
265: * @param e The edge whose weight to return.
266: *
267: * @return The weight of the edge.
268: */
269: public double getWeight(Edge e);
270: }
271:
272: /**
273: * Internal data structure used to track node costs, and parent nodes.
274: *
275: * @author Justin Deoliveira, Refractions Research Inc, jdeolive@refractions.net
276: *
277: */
278: protected static class DijkstraNode {
279: /** underlying graph node **/
280: public Node node;
281:
282: /** cost associated with the node **/
283: public double cost;
284:
285: /** last node to update the cost the the underlying graph node **/
286: public DijkstraNode parent;
287:
288: /**
289: * Constructs a new Dijsktra node.
290: *
291: * @param node Underling node in graph being iterated over.
292: * @param cost Initial cost of node.
293: */
294: public DijkstraNode(Node node, double cost) {
295: this.node = node;
296: this.cost = cost;
297: }
298: }
299: }
|