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