1 /*
2 * Created on Jul 9, 2005
3 *
4 * Copyright (c) 2005, the JUNG Project and the Regents of the University
5 * of California
6 * All rights reserved.
7 *
8 * This software is open-source under the BSD license; see either
9 * "license.txt" or
10 * http://jung.sourceforge.net/license.txt for a description.
11 */
12 package edu.uci.ics.jung.algorithms.shortestpath;
13
14 import java.util.Collection;
15 import java.util.Comparator;
16 import java.util.HashMap;
17 import java.util.HashSet;
18 import java.util.LinkedHashMap;
19 import java.util.Map;
20 import java.util.Set;
21
22 import org.apache.commons.collections15.Transformer;
23 import org.apache.commons.collections15.functors.ConstantTransformer;
24
25 import edu.uci.ics.jung.algorithms.util.BasicMapEntry;
26 import edu.uci.ics.jung.algorithms.util.MapBinaryHeap;
27 import edu.uci.ics.jung.graph.Graph;
28 import edu.uci.ics.jung.graph.Hypergraph;
29
30 /**
31 * <p>Calculates distances in a specified graph, using
32 * Dijkstra's single-source-shortest-path algorithm. All edge weights
33 * in the graph must be nonnegative; if any edge with negative weight is
34 * found in the course of calculating distances, an
35 * <code>IllegalArgumentException</code> will be thrown.
36 * (Note: this exception will only be thrown when such an edge would be
37 * used to update a given tentative distance;
38 * the algorithm does not check for negative-weight edges "up front".)
39 *
40 * <p>Distances and partial results are optionally cached (by this instance)
41 * for later reference. Thus, if the 10 closest vertices to a specified source
42 * vertex are known, calculating the 20 closest vertices does not require
43 * starting Dijkstra's algorithm over from scratch.</p>
44 *
45 * <p>Distances are stored as double-precision values.
46 * If a vertex is not reachable from the specified source vertex, no
47 * distance is stored. <b>This is new behavior with version 1.4</b>;
48 * the previous behavior was to store a value of
49 * <code>Double.POSITIVE_INFINITY</code>. This change gives the algorithm
50 * an approximate complexity of O(kD log k), where k is either the number of
51 * requested targets or the number of reachable vertices (whichever is smaller),
52 * and D is the average degree of a vertex.</p>
53 *
54 * <p> The elements in the maps returned by <code>getDistanceMap</code>
55 * are ordered (that is, returned
56 * by the iterator) by nondecreasing distance from <code>source</code>.</p>
57 *
58 * <p>Users are cautioned that distances calculated should be assumed to
59 * be invalidated by changes to the graph, and should invoke <code>reset()</code>
60 * when appropriate so that the distances can be recalculated.</p>
61 *
62 * @author Joshua O'Madadhain
63 * @author Tom Nelson converted to jung2
64 */
65 public class DijkstraDistance<V,E> implements Distance<V>
66 {
67 protected Hypergraph<V,E> g;
68 protected Transformer<E,? extends Number> nev;
69 protected Map<V,SourceData> sourceMap; // a map of source vertices to an instance of SourceData
70 protected boolean cached;
71 protected double max_distance;
72 protected int max_targets;
73
74 /**
75 * <p>Creates an instance of <code>DijkstraShortestPath</code> for
76 * the specified graph and the specified method of extracting weights
77 * from edges, which caches results locally if and only if
78 * <code>cached</code> is <code>true</code>.
79 *
80 * @param g the graph on which distances will be calculated
81 * @param nev the class responsible for returning weights for edges
82 * @param cached specifies whether the results are to be cached
83 */
84 public DijkstraDistance(Hypergraph<V,E> g, Transformer<E,? extends Number> nev, boolean cached) {
85 this.g = g;
86 this.nev = nev;
87 this.sourceMap = new HashMap<V,SourceData>();
88 this.cached = cached;
89 this.max_distance = Double.POSITIVE_INFINITY;
90 this.max_targets = Integer.MAX_VALUE;
91 }
92
93 /**
94 * <p>Creates an instance of <code>DijkstraShortestPath</code> for
95 * the specified graph and the specified method of extracting weights
96 * from edges, which caches results locally.
97 *
98 * @param g the graph on which distances will be calculated
99 * @param nev the class responsible for returning weights for edges
100 */
101 public DijkstraDistance(Hypergraph<V,E> g, Transformer<E,? extends Number> nev) {
102 this(g, nev, true);
103 }
104
105 /**
106 * <p>Creates an instance of <code>DijkstraShortestPath</code> for
107 * the specified unweighted graph (that is, all weights 1) which
108 * caches results locally.
109 *
110 * @param g the graph on which distances will be calculated
111 */
112 @SuppressWarnings("unchecked")
113 public DijkstraDistance(Graph<V,E> g) {
114 this(g, new ConstantTransformer(1), true);
115 }
116
117 /**
118 * <p>Creates an instance of <code>DijkstraShortestPath</code> for
119 * the specified unweighted graph (that is, all weights 1) which
120 * caches results locally.
121 *
122 * @param g the graph on which distances will be calculated
123 * @param cached specifies whether the results are to be cached
124 */
125 @SuppressWarnings("unchecked")
126 public DijkstraDistance(Graph<V,E> g, boolean cached) {
127 this(g, new ConstantTransformer(1), cached);
128 }
129
130 /**
131 * Implements Dijkstra's single-source shortest-path algorithm for
132 * weighted graphs. Uses a <code>MapBinaryHeap</code> as the priority queue,
133 * which gives this algorithm a time complexity of O(m lg n) (m = # of edges, n =
134 * # of vertices).
135 * This algorithm will terminate when any of the following have occurred (in order
136 * of priority):
137 * <ul>
138 * <li> the distance to the specified target (if any) has been found
139 * <li> no more vertices are reachable
140 * <li> the specified # of distances have been found, or the maximum distance
141 * desired has been exceeded
142 * <li> all distances have been found
143 * </ul>
144 *
145 * @param source the vertex from which distances are to be measured
146 * @param numDests the number of distances to measure
147 * @param targets the set of vertices to which distances are to be measured
148 */
149 protected LinkedHashMap<V,Number> singleSourceShortestPath(V source, Collection<V> targets, int numDests)
150 {
151 SourceData sd = getSourceData(source);
152
153 Set<V> to_get = new HashSet<V>();
154 if (targets != null) {
155 to_get.addAll(targets);
156 Set<V> existing_dists = sd.distances.keySet();
157 for(V o : targets) {
158 if (existing_dists.contains(o))
159 to_get.remove(o);
160 }
161 }
162
163 // if we've exceeded the max distance or max # of distances we're willing to calculate, or
164 // if we already have all the distances we need,
165 // terminate
166 if (sd.reached_max ||
167 (targets != null && to_get.isEmpty()) ||
168 (sd.distances.size() >= numDests))
169 {
170 return sd.distances;
171 }
172
173 while (!sd.unknownVertices.isEmpty() && (sd.distances.size() < numDests || !to_get.isEmpty()))
174 {
175 Map.Entry<V,Number> p = sd.getNextVertex();
176 V v = p.getKey();
177 double v_dist = p.getValue().doubleValue();
178 to_get.remove(v);
179 if (v_dist > this.max_distance)
180 {
181 // we're done; put this vertex back in so that we're not including
182 // a distance beyond what we specified
183 sd.restoreVertex(v, v_dist);
184 sd.reached_max = true;
185 break;
186 }
187 sd.dist_reached = v_dist;
188
189 if (sd.distances.size() >= this.max_targets)
190 {
191 sd.reached_max = true;
192 break;
193 }
194
195 for (E e : getEdgesToCheck(v) )
196 {
197 for (V w : g.getIncidentVertices(e))
198 {
199 if (!sd.distances.containsKey(w))
200 {
201 double edge_weight = nev.transform(e).doubleValue();
202 if (edge_weight < 0)
203 throw new IllegalArgumentException("Edges weights must be non-negative");
204 double new_dist = v_dist + edge_weight;
205 if (!sd.estimatedDistances.containsKey(w))
206 {
207 sd.createRecord(w, e, new_dist);
208 }
209 else
210 {
211 double w_dist = ((Double)sd.estimatedDistances.get(w)).doubleValue();
212 if (new_dist < w_dist) // update tentative distance & path for w
213 sd.update(w, e, new_dist);
214 }
215 }
216 }
217 }
218 }
219 return sd.distances;
220 }
221
222 protected SourceData getSourceData(V source)
223 {
224 SourceData sd = sourceMap.get(source);
225 if (sd == null)
226 sd = new SourceData(source);
227 return sd;
228 }
229
230 /**
231 * Returns the set of edges incident to <code>v</code> that should be tested.
232 * By default, this is the set of outgoing edges for instances of <code>Graph</code>,
233 * the set of incident edges for instances of <code>Hypergraph</code>,
234 * and is otherwise undefined.
235 */
236 protected Collection<E> getEdgesToCheck(V v)
237 {
238 if (g instanceof Graph)
239 return ((Graph<V,E>)g).getOutEdges(v);
240 else
241 return g.getIncidentEdges(v);
242
243 }
244
245
246 /**
247 * Returns the length of a shortest path from the source to the target vertex,
248 * or null if the target is not reachable from the source.
249 * If either vertex is not in the graph for which this instance
250 * was created, throws <code>IllegalArgumentException</code>.
251 *
252 * @see #getDistanceMap(Object)
253 * @see #getDistanceMap(Object,int)
254 */
255 public Number getDistance(V source, V target)
256 {
257 if (g.containsVertex(target) == false)
258 throw new IllegalArgumentException("Specified target vertex " +
259 target + " is not part of graph " + g);
260 if (g.containsVertex(source) == false)
261 throw new IllegalArgumentException("Specified source vertex " +
262 source + " is not part of graph " + g);
263
264 Set<V> targets = new HashSet<V>();
265 targets.add(target);
266 Map<V,Number> distanceMap = getDistanceMap(source, targets);
267 return distanceMap.get(target);
268 }
269
270
271 /**
272 * Returns a {@code Map} from each element {@code t} of {@code targets} to the
273 * shortest-path distance from {@code source} to {@code t}.
274 */
275 public Map<V,Number> getDistanceMap(V source, Collection<V> targets)
276 {
277 if (g.containsVertex(source) == false)
278 throw new IllegalArgumentException("Specified source vertex " +
279 source + " is not part of graph " + g);
280 if (targets.size() > max_targets)
281 throw new IllegalArgumentException("size of target set exceeds maximum " +
282 "number of targets allowed: " + this.max_targets);
283
284 Map<V,Number> distanceMap =
285 singleSourceShortestPath(source, targets,
286 Math.min(g.getVertexCount(), max_targets));
287 if (!cached)
288 reset(source);
289
290 return distanceMap;
291 }
292
293 /**
294 * <p>Returns a <code>LinkedHashMap</code> which maps each vertex
295 * in the graph (including the <code>source</code> vertex)
296 * to its distance from the <code>source</code> vertex.
297 * The map's iterator will return the elements in order of
298 * increasing distance from <code>source</code>.</p>
299 *
300 * <p>The size of the map returned will be the number of
301 * vertices reachable from <code>source</code>.</p>
302 *
303 * @see #getDistanceMap(Object,int)
304 * @see #getDistance(Object,Object)
305 * @param source the vertex from which distances are measured
306 */
307 public Map<V,Number> getDistanceMap(V source)
308 {
309 return getDistanceMap(source, Math.min(g.getVertexCount(), max_targets));
310 }
311
312
313
314 /**
315 * <p>Returns a <code>LinkedHashMap</code> which maps each of the closest
316 * <code>numDist</code> vertices to the <code>source</code> vertex
317 * in the graph (including the <code>source</code> vertex)
318 * to its distance from the <code>source</code> vertex. Throws
319 * an <code>IllegalArgumentException</code> if <code>source</code>
320 * is not in this instance's graph, or if <code>numDests</code> is
321 * either less than 1 or greater than the number of vertices in the
322 * graph.</p>
323 *
324 * <p>The size of the map returned will be the smaller of
325 * <code>numDests</code> and the number of vertices reachable from
326 * <code>source</code>.
327 *
328 * @see #getDistanceMap(Object)
329 * @see #getDistance(Object,Object)
330 * @param source the vertex from which distances are measured
331 * @param numDests the number of vertices for which to measure distances
332 */
333 public LinkedHashMap<V,Number> getDistanceMap(V source, int numDests)
334 {
335
336 if(g.getVertices().contains(source) == false) {
337 throw new IllegalArgumentException("Specified source vertex " +
338 source + " is not part of graph " + g);
339
340 }
341 if (numDests < 1 || numDests > g.getVertexCount())
342 throw new IllegalArgumentException("numDests must be >= 1 " +
343 "and <= g.numVertices()");
344
345 if (numDests > max_targets)
346 throw new IllegalArgumentException("numDests must be <= the maximum " +
347 "number of targets allowed: " + this.max_targets);
348
349 LinkedHashMap<V,Number> distanceMap =
350 singleSourceShortestPath(source, null, numDests);
351
352 if (!cached)
353 reset(source);
354
355 return distanceMap;
356 }
357
358 /**
359 * Allows the user to specify the maximum distance that this instance will calculate.
360 * Any vertices past this distance will effectively be unreachable from the source, in
361 * the sense that the algorithm will not calculate the distance to any vertices which
362 * are farther away than this distance. A negative value for <code>max_dist</code>
363 * will ensure that no further distances are calculated.
364 *
365 * <p>This can be useful for limiting the amount of time and space used by this algorithm
366 * if the graph is very large.</p>
367 *
368 * <p>Note: if this instance has already calculated distances greater than <code>max_dist</code>,
369 * and the results are cached, those results will still be valid and available; this limit
370 * applies only to subsequent distance calculations.</p>
371 * @see #setMaxTargets(int)
372 */
373 public void setMaxDistance(double max_dist)
374 {
375 this.max_distance = max_dist;
376 for (V v : sourceMap.keySet())
377 {
378 SourceData sd = sourceMap.get(v);
379 sd.reached_max = (this.max_distance <= sd.dist_reached) || (sd.distances.size() >= max_targets);
380 }
381 }
382
383 /**
384 * Allows the user to specify the maximum number of target vertices per source vertex
385 * for which this instance will calculate distances. Once this threshold is reached,
386 * any further vertices will effectively be unreachable from the source, in
387 * the sense that the algorithm will not calculate the distance to any more vertices.
388 * A negative value for <code>max_targets</code> will ensure that no further distances are calculated.
389 *
390 * <p>This can be useful for limiting the amount of time and space used by this algorithm
391 * if the graph is very large.</p>
392 *
393 * <p>Note: if this instance has already calculated distances to a greater number of
394 * targets than <code>max_targets</code>, and the results are cached, those results
395 * will still be valid and available; this limit applies only to subsequent distance
396 * calculations.</p>
397 * @see #setMaxDistance(double)
398 */
399 public void setMaxTargets(int max_targets)
400 {
401 this.max_targets = max_targets;
402 for (V v : sourceMap.keySet())
403 {
404 SourceData sd = sourceMap.get(v);
405 sd.reached_max = (this.max_distance <= sd.dist_reached) || (sd.distances.size() >= max_targets);
406 }
407 }
408
409 /**
410 * Clears all stored distances for this instance.
411 * Should be called whenever the graph is modified (edge weights
412 * changed or edges added/removed). If the user knows that
413 * some currently calculated distances are unaffected by a
414 * change, <code>reset(V)</code> may be appropriate instead.
415 *
416 * @see #reset(Object)
417 */
418 public void reset()
419 {
420 sourceMap = new HashMap<V,SourceData>();
421 }
422
423 /**
424 * Specifies whether or not this instance of <code>DijkstraShortestPath</code>
425 * should cache its results (final and partial) for future reference.
426 *
427 * @param enable <code>true</code> if the results are to be cached, and
428 * <code>false</code> otherwise
429 */
430 public void enableCaching(boolean enable)
431 {
432 this.cached = enable;
433 }
434
435 /**
436 * Clears all stored distances for the specified source vertex
437 * <code>source</code>. Should be called whenever the stored distances
438 * from this vertex are invalidated by changes to the graph.
439 *
440 * @see #reset()
441 */
442 public void reset(V source)
443 {
444 sourceMap.put(source, null);
445 }
446
447 /**
448 * Compares according to distances, so that the BinaryHeap knows how to
449 * order the tree.
450 */
451 protected static class VertexComparator<V> implements Comparator<V>
452 {
453 private Map<V,Number> distances;
454
455 protected VertexComparator(Map<V,Number> distances)
456 {
457 this.distances = distances;
458 }
459
460 public int compare(V o1, V o2)
461 {
462 return ((Double) distances.get(o1)).compareTo((Double) distances.get(o2));
463 }
464 }
465
466 /**
467 * For a given source vertex, holds the estimated and final distances,
468 * tentative and final assignments of incoming edges on the shortest path from
469 * the source vertex, and a priority queue (ordered by estimated distance)
470 * of the vertices for which distances are unknown.
471 *
472 * @author Joshua O'Madadhain
473 */
474 protected class SourceData
475 {
476 protected LinkedHashMap<V,Number> distances;
477 protected Map<V,Number> estimatedDistances;
478 protected MapBinaryHeap<V> unknownVertices;
479 protected boolean reached_max = false;
480 protected double dist_reached = 0;
481
482 protected SourceData(V source)
483 {
484 distances = new LinkedHashMap<V,Number>();
485 estimatedDistances = new HashMap<V,Number>();
486 unknownVertices = new MapBinaryHeap<V>(new VertexComparator<V>(estimatedDistances));
487
488 sourceMap.put(source, this);
489
490 // initialize priority queue
491 estimatedDistances.put(source, new Double(0)); // distance from source to itself is 0
492 unknownVertices.add(source);
493 reached_max = false;
494 dist_reached = 0;
495 }
496
497 protected Map.Entry<V,Number> getNextVertex()
498 {
499 V v = unknownVertices.remove();
500 Double dist = (Double)estimatedDistances.remove(v);
501 distances.put(v, dist);
502 return new BasicMapEntry<V,Number>(v, dist);
503 }
504
505 protected void update(V dest, E tentative_edge, double new_dist)
506 {
507 estimatedDistances.put(dest, new_dist);
508 unknownVertices.update(dest);
509 }
510
511 protected void createRecord(V w, E e, double new_dist)
512 {
513 estimatedDistances.put(w, new_dist);
514 unknownVertices.add(w);
515 }
516
517 protected void restoreVertex(V v, double dist)
518 {
519 estimatedDistances.put(v, dist);
520 unknownVertices.add(v);
521 distances.remove(v);
522 }
523 }
524 }