Coverage details for edu.uci.ics.jung.algorithms.shortestpath.DijkstraDistance

LineHitsSource
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;
721    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)
8744    {
8844        this.g = g;
8944        this.nev = nev;
9044        this.sourceMap = new HashMap();
9144        this.cached = cached;
9244        this.max_distance = Double.POSITIVE_INFINITY;
9344        this.max_targets = Integer.MAX_VALUE;
9444    }
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     {
1064        this(g, nev, true);
1074    }
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     {
1180        this(g, dev, true);
1190    }
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     {
1310        this(g, dev, cached);
1320    }
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     {
1541702        SourceData sd = getSourceData(source);
155  
1561702        Set to_get = new HashSet();
1571702        if (targets != null)
158         {
159820            to_get.addAll(targets);
160820            Set existing_dists = sd.distances.keySet();
161820            for (Iterator iter = targets.iterator(); iter.hasNext(); )
162             {
163820                Object o = iter.next();
164820                if (existing_dists.contains(o))
165192                    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
1721702        if (sd.reached_max ||
173                 (targets != null && to_get.isEmpty()) ||
174                 (sd.distances.size() >= numDests))
175         {
176192            return sd.distances;
177         }
178         
1795866        while (!sd.unknownVertices.isEmpty() && (sd.distances.size() < numDests || !to_get.isEmpty()))
180         {
1814358            Pair p = sd.getNextVertex();
1824358            ArchetypeVertex v = (ArchetypeVertex)p.getFirst();
1834358            double v_dist = ((Double)p.getSecond()).doubleValue();
1844358            sd.dist_reached = v_dist;
1854358            to_get.remove(v);
1864358            if ((sd.dist_reached >= this.max_distance) || (sd.distances.size() >= max_targets))
187             {
1880                sd.reached_max = true;
1890                break;
190             }
191             
1924358            for (Iterator out_iter = getIncidentEdges(v).iterator(); out_iter.hasNext(); )
193             {
19410619                ArchetypeEdge e = (ArchetypeEdge)out_iter.next();
195 // Vertex w = e.getOpposite(v);
19610619                for (Iterator e_iter = e.getIncidentVertices().iterator(); e_iter.hasNext(); )
197                 {
19821238                    ArchetypeVertex w = (ArchetypeVertex)e_iter.next();
19921238                    if (!sd.distances.containsKey(w))
200                     {
2016289                        double edge_weight = nev.getNumber(e).doubleValue();
2026289                        if (edge_weight < 0)
2032                            throw new IllegalArgumentException("Edge weights must be non-negative");
2046287                        double new_dist = v_dist + edge_weight;
2056287                        if (!sd.estimatedDistances.containsKey(w))
206                         {
2073793                            sd.createRecord(w, e, new_dist);
208                         }
209                         else
210                         {
2112494                            double w_dist = ((Double)sd.estimatedDistances.get(w)).doubleValue();
2122494                            if (new_dist < w_dist) // update tentative distance & path for w
2131021                                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         }
2231508        return sd.distances;
224     }
225  
226     protected SourceData getSourceData(ArchetypeVertex source)
227     {
2280        SourceData sd = (SourceData)sourceMap.get(source);
2290        if (sd == null)
2300            sd = new SourceData(source);
2310        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     {
2424358        if (v instanceof Vertex)
2434358            return ((Vertex)v).getOutEdges();
2440        else if (v instanceof Hypervertex)
2450            return v.getIncidentEdges();
246         else
2470            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     {
262404        if (target.getGraph() != g)
2632            throw new IllegalArgumentException("Specified target vertex " +
264                     target + " is not part of graph " + g);
265         
266402        Set targets = new HashSet();
267402        targets.add(target);
268402        Map distanceMap = getDistanceMap(source, targets);
269400        return (Double)distanceMap.get(target);
270     }
271     
272  
273     public Map getDistanceMap(ArchetypeVertex source, Set targets)
274     {
275402        if (source.getGraph() != g)
2762            throw new IllegalArgumentException("Specified source vertex " +
277                     source + " is not part of graph " + g);
278  
279400        if (targets.size() > max_targets)
2800            throw new IllegalArgumentException("size of target set exceeds maximum " +
281                     "number of targets allowed: " + this.max_targets);
282         
283400        Map distanceMap = singleSourceShortestPath(source, targets, (int)Math.min(g.numVertices(), max_targets));
284         
285400        if (!cached)
286200            reset(source);
287         
288400        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     {
30742        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     {
333450        if (source.getGraph() != g)
3342            throw new IllegalArgumentException("Specified source vertex " +
335                 source + " is not part of graph " + g);
336  
337448        if (numDests < 1 || numDests > g.numVertices())
3386            throw new IllegalArgumentException("numDests must be >= 1 " +
339                 "and <= g.numVertices()");
340  
341442        if (numDests > max_targets)
3420            throw new IllegalArgumentException("numDests must be <= the maximum " +
343                     "number of targets allowed: " + this.max_targets);
344             
345442        LinkedHashMap distanceMap = singleSourceShortestPath(source, null, numDests);
346                 
347440        if (!cached)
348220            reset(source);
349         
350440        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     {
3700        this.max_distance = max_dist;
3710        for (Iterator iter = sourceMap.keySet().iterator(); iter.hasNext(); )
372         {
3730            SourceData sd = (SourceData)sourceMap.get(iter.next());
3740            sd.reached_max = (this.max_distance <= sd.dist_reached) || (sd.distances.size() >= max_targets);
375         }
3760    }
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     {
3960        this.max_targets = max_targets;
3970        for (Iterator iter = sourceMap.keySet().iterator(); iter.hasNext(); )
398         {
3990            SourceData sd = (SourceData)sourceMap.get(iter.next());
4000            sd.reached_max = (this.max_distance <= sd.dist_reached) || (sd.distances.size() >= max_targets);
401         }
4020    }
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     {
415204        sourceMap = new HashMap();
416204    }
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     {
4270        this.cached = enable;
4280    }
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     {
439840        sourceMap.put(source, null);
440840    }
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.
visit www.jcoverage.com for updates.

copyright © 2003, jcoverage ltd. all rights reserved.
Java is a trademark of Sun Microsystems, Inc. in the United States and other countries.