third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/shortestpath/DijkstraDistance.java

   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(Hypergraph<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(Hypergraph<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      * @param regular   boolean is true if we want regular SP dijkstra. False for MT.
 149      */
 150     private LinkedHashMap<V,Number> singleSourceShortestPath(V source, Collection<V> targets, int numDests, boolean regular)
 151     {
 152         SourceData sd = getSourceData(source);
 153
 154         Set<V> to_get = new HashSet<V>();
 155         if (targets != null) {
 156             to_get.addAll(targets);
 157             Set<V> existing_dists = sd.distances.keySet();
 158             for(V o : targets) {
 159                 if (existing_dists.contains(o))
 160                     to_get.remove(o);
 161             }
 162         }
 163
 164         // if we've exceeded the max distance or max # of distances we're willing to calculate, or
 165         // if we already have all the distances we need,
 166         // terminate
 167         if (sd.reached_max ||
 168             (targets != null && to_get.isEmpty()) ||
 169             (sd.distances.size() >= numDests))
 170         {
 171             return sd.distances;
 172         }
 173
 174         while (!sd.unknownVertices.isEmpty() && (sd.distances.size() < numDests || !to_get.isEmpty()))
 175         {
 176             Map.Entry<V,Number> p = sd.getNextVertex();
 177             V v = p.getKey();
 178             double v_dist = p.getValue().doubleValue();
 179             to_get.remove(v);
 180             if (v_dist > this.max_distance)
 181             {
 182                 // we're done; put this vertex back in so that we're not including
 183                 // a distance beyond what we specified
 184                 sd.restoreVertex(v, v_dist);
 185                 sd.reached_max = true;
 186                 break;
 187             }
 188             sd.dist_reached = v_dist;
 189
 190             if (sd.distances.size() >= this.max_targets)
 191             {
 192                 sd.reached_max = true;
 193                 break;
 194             }
 195
 196             for (E e : getEdgesToCheck(v) )
 197             {
 198                 for (V w : g.getIncidentVertices(e))
 199                 {
 200                     if (!sd.distances.containsKey(w))
 201                     {
 202                         double edge_weight = nev.transform(e).doubleValue();
 203                         if (edge_weight < 0)
 204                             throw new IllegalArgumentException("Edges weights must be non-negative");
 205                         double new_dist;
 206                         if (regular == true) {
 207                           new_dist = v_dist + edge_weight;
 208                         } else {
 209                           if (v_dist <= edge_weight) {
 210                             new_dist = edge_weight;
 211                           } else {
 212                             new_dist = v_dist;
 213                           }
 214                         }
 215                         if (!sd.estimatedDistances.containsKey(w))
 216                         {
 217                             sd.createRecord(w, e, new_dist);
 218                         }
 219                         else
 220                         {
 221                             double w_dist = ((Double)sd.estimatedDistances.get(w)).doubleValue();
 222                             if (new_dist < w_dist) // update tentative distance & path for w
 223                                 sd.update(w, e, new_dist);
 224                         }
 225                     }
 226                 }
 227             }
 228         }
 229         return sd.distances;
 230     }
 231
 232     /**
 233      * Implements Dijkstra's single-source shortest-path algorithm for
 234      * weighted graphs.  Uses a <code>MapBinaryHeap</code> as the priority queue,
 235      * which gives this algorithm a time complexity of O(m lg n) (m = # of edges, n =
 236      * # of vertices).
 237      * This algorithm will terminate when any of the following have occurred (in order
 238      * of priority):
 239      * <ul>
 240      * <li> the distance to the specified target (if any) has been found
 241      * <li> no more vertices are reachable
 242      * <li> the specified # of distances have been found, or the maximum distance
 243      * desired has been exceeded
 244      * <li> all distances have been found
 245      * </ul>
 246      *
 247      * @param source    the vertex from which distances are to be measured
 248      * @param numDests  the number of distances to measure
 249      * @param targets   the set of vertices to which distances are to be measured
 250      */
 251     protected LinkedHashMap<V,Number> singleSourceShortestPath(V source, Collection<V> targets, int numDests)
 252     {
 253         return singleSourceShortestPath(source, targets, numDests, true);
 254     }
 255
 256     /**
 257      * Implements Dijkstra's single-source shortest-path algorithm for
 258      * weighted graphs.  Uses a <code>MapBinaryHeap</code> as the priority queue,
 259      * which gives this algorithm a time complexity of O(m lg n) (m = # of edges, n =
 260      * # of vertices).
 261      * This algorithm will terminate when any of the following have occurred (in order
 262      * of priority):
 263      * <ul>
 264      * <li> the distance to the specified target (if any) has been found
 265      * <li> no more vertices are reachable
 266      * <li> the specified # of distances have been found, or the maximum distance
 267      * desired has been exceeded
 268      * <li> all distances have been found
 269      * </ul>
 270      *
 271      * @param source    the vertex from which distances are to be measured
 272      * @param numDests  the number of distances to measure
 273      * @param targets   the set of vertices to which distances are to be measured
 274      */
 275     protected LinkedHashMap<V,Number> singleSourceMaxThroughputPath(V source, Collection<V> targets, int numDests)
 276     {
 277         return singleSourceShortestPath(source, targets, numDests, false);
 278     }
 279
 280     protected SourceData getSourceData(V source)
 281     {
 282         SourceData sd = sourceMap.get(source);
 283         if (sd == null)
 284             sd = new SourceData(source);
 285         return sd;
 286     }
 287
 288     /**
 289      * Returns the set of edges incident to <code>v</code> that should be tested.
 290      * By default, this is the set of outgoing edges for instances of <code>Graph</code>,
 291      * the set of incident edges for instances of <code>Hypergraph</code>,
 292      * and is otherwise undefined.
 293      */
 294     protected Collection<E> getEdgesToCheck(V v)
 295     {
 296         if (g instanceof Graph)
 297             return ((Graph<V,E>)g).getOutEdges(v);
 298         else
 299             return g.getIncidentEdges(v);
 300
 301     }
 302
 303
 304     /**
 305      * Returns the length of a shortest path from the source to the target vertex,
 306      * or null if the target is not reachable from the source.
 307      * If either vertex is not in the graph for which this instance
 308      * was created, throws <code>IllegalArgumentException</code>.
 309      *
 310      * @see #getDistanceMap(Object)
 311      * @see #getDistanceMap(Object,int)
 312      */
 313     public Number getDistance(V source, V target)
 314     {
 315         if (g.containsVertex(target) == false)
 316             throw new IllegalArgumentException("Specified target vertex " +
 317                     target + " is not part of graph " + g);
 318         if (g.containsVertex(source) == false)
 319             throw new IllegalArgumentException("Specified source vertex " +
 320                     source + " is not part of graph " + g);
 321
 322         Set<V> targets = new HashSet<V>();
 323         targets.add(target);
 324         Map<V,Number> distanceMap = getDistanceMap(source, targets);
 325         return distanceMap.get(target);
 326     }
 327
 328
 329     /**
 330      * Returns a {@code Map} from each element {@code t} of {@code targets} to the
 331      * shortest-path distance from {@code source} to {@code t}.
 332      */
 333     public Map<V,Number> getDistanceMap(V source, Collection<V> targets)
 334     {
 335        if (g.containsVertex(source) == false)
 336             throw new IllegalArgumentException("Specified source vertex " +
 337                     source + " is not part of graph " + g);
 338        if (targets.size() > max_targets)
 339             throw new IllegalArgumentException("size of target set exceeds maximum " +
 340                     "number of targets allowed: " + this.max_targets);
 341
 342         Map<V,Number> distanceMap =
 343                 singleSourceShortestPath(source, targets,
 344                                 Math.min(g.getVertexCount(), max_targets));
 345         if (!cached)
 346             reset(source);
 347
 348         return distanceMap;
 349     }
 350
 351     /**
 352      * <p>Returns a <code>LinkedHashMap</code> which maps each vertex
 353      * in the graph (including the <code>source</code> vertex)
 354      * to its distance from the <code>source</code> vertex.
 355      * The map's iterator will return the elements in order of
 356      * increasing distance from <code>source</code>.</p>
 357      *
 358      * <p>The size of the map returned will be the number of
 359      * vertices reachable from <code>source</code>.</p>
 360      *
 361      * @see #getDistanceMap(Object,int)
 362      * @see #getDistance(Object,Object)
 363      * @param source    the vertex from which distances are measured
 364      */
 365     public Map<V,Number> getDistanceMap(V source)
 366     {
 367         return getDistanceMap(source, Math.min(g.getVertexCount(), max_targets));
 368     }
 369
 370
 371
 372     /**
 373      * <p>Returns a <code>LinkedHashMap</code> which maps each of the closest
 374      * <code>numDist</code> vertices to the <code>source</code> vertex
 375      * in the graph (including the <code>source</code> vertex)
 376      * to its distance from the <code>source</code> vertex.  Throws
 377      * an <code>IllegalArgumentException</code> if <code>source</code>
 378      * is not in this instance's graph, or if <code>numDests</code> is
 379      * either less than 1 or greater than the number of vertices in the
 380      * graph.</p>
 381      *
 382      * <p>The size of the map returned will be the smaller of
 383      * <code>numDests</code> and the number of vertices reachable from
 384      * <code>source</code>.
 385      *
 386      * @see #getDistanceMap(Object)
 387      * @see #getDistance(Object,Object)
 388      * @param source    the vertex from which distances are measured
 389      * @param numDests  the number of vertices for which to measure distances
 390      */
 391     public LinkedHashMap<V,Number> getDistanceMap(V source, int numDests)
 392     {
 393
 394         if(g.getVertices().contains(source) == false) {
 395             throw new IllegalArgumentException("Specified source vertex " +
 396                     source + " is not part of graph " + g);
 397
 398         }
 399         if (numDests < 1 || numDests > g.getVertexCount())
 400             throw new IllegalArgumentException("numDests must be >= 1 " +
 401                 "and <= g.numVertices()");
 402
 403         if (numDests > max_targets)
 404             throw new IllegalArgumentException("numDests must be <= the maximum " +
 405                     "number of targets allowed: " + this.max_targets);
 406
 407         LinkedHashMap<V,Number> distanceMap =
 408                 singleSourceShortestPath(source, null, numDests);
 409
 410         if (!cached)
 411             reset(source);
 412
 413         return distanceMap;
 414     }
 415
 416     /**
 417      * Allows the user to specify the maximum distance that this instance will calculate.
 418      * Any vertices past this distance will effectively be unreachable from the source, in
 419      * the sense that the algorithm will not calculate the distance to any vertices which
 420      * are farther away than this distance.  A negative value for <code>max_dist</code>
 421      * will ensure that no further distances are calculated.
 422      *
 423      * <p>This can be useful for limiting the amount of time and space used by this algorithm
 424      * if the graph is very large.</p>
 425      *
 426      * <p>Note: if this instance has already calculated distances greater than <code>max_dist</code>,
 427      * and the results are cached, those results will still be valid and available; this limit
 428      * applies only to subsequent distance calculations.</p>
 429      * @see #setMaxTargets(int)
 430      */
 431     public void setMaxDistance(double max_dist)
 432     {
 433         this.max_distance = max_dist;
 434         for (V v : sourceMap.keySet())
 435         {
 436             SourceData sd = sourceMap.get(v);
 437             sd.reached_max = (this.max_distance <= sd.dist_reached) || (sd.distances.size() >= max_targets);
 438         }
 439     }
 440
 441     /**
 442      * Allows the user to specify the maximum number of target vertices per source vertex
 443      * for which this instance will calculate distances.  Once this threshold is reached,
 444      * any further vertices will effectively be unreachable from the source, in
 445      * the sense that the algorithm will not calculate the distance to any more vertices.
 446      * A negative value for <code>max_targets</code> will ensure that no further distances are calculated.
 447      *
 448      * <p>This can be useful for limiting the amount of time and space used by this algorithm
 449      * if the graph is very large.</p>
 450      *
 451      * <p>Note: if this instance has already calculated distances to a greater number of
 452      * targets than <code>max_targets</code>, and the results are cached, those results
 453      * will still be valid and available; this limit applies only to subsequent distance
 454      * calculations.</p>
 455      * @see #setMaxDistance(double)
 456      */
 457     public void setMaxTargets(int max_targets)
 458     {
 459         this.max_targets = max_targets;
 460         for (V v : sourceMap.keySet())
 461         {
 462             SourceData sd = sourceMap.get(v);
 463             sd.reached_max = (this.max_distance <= sd.dist_reached) || (sd.distances.size() >= max_targets);
 464         }
 465     }
 466
 467     /**
 468      * Clears all stored distances for this instance.
 469      * Should be called whenever the graph is modified (edge weights
 470      * changed or edges added/removed).  If the user knows that
 471      * some currently calculated distances are unaffected by a
 472      * change, <code>reset(V)</code> may be appropriate instead.
 473      *
 474      * @see #reset(Object)
 475      */
 476     public void reset()
 477     {
 478         sourceMap = new HashMap<V,SourceData>();
 479     }
 480
 481     /**
 482      * Specifies whether or not this instance of <code>DijkstraShortestPath</code>
 483      * should cache its results (final and partial) for future reference.
 484      *
 485      * @param enable    <code>true</code> if the results are to be cached, and
 486      *                  <code>false</code> otherwise
 487      */
 488     public void enableCaching(boolean enable)
 489     {
 490         this.cached = enable;
 491     }
 492
 493     /**
 494      * Clears all stored distances for the specified source vertex
 495      * <code>source</code>.  Should be called whenever the stored distances
 496      * from this vertex are invalidated by changes to the graph.
 497      *
 498      * @see #reset()
 499      */
 500     public void reset(V source)
 501     {
 502         sourceMap.put(source, null);
 503     }
 504
 505     /**
 506      * Compares according to distances, so that the BinaryHeap knows how to
 507      * order the tree.
 508      */
 509     protected static class VertexComparator<V> implements Comparator<V>
 510     {
 511         private Map<V,Number> distances;
 512
 513         protected VertexComparator(Map<V,Number> distances)
 514         {
 515             this.distances = distances;
 516         }
 517
 518         public int compare(V o1, V o2)
 519         {
 520             return ((Double) distances.get(o1)).compareTo((Double) distances.get(o2));
 521         }
 522     }
 523
 524     /**
 525      * For a given source vertex, holds the estimated and final distances,
 526      * tentative and final assignments of incoming edges on the shortest path from
 527      * the source vertex, and a priority queue (ordered by estimated distance)
 528      * of the vertices for which distances are unknown.
 529      *
 530      * @author Joshua O'Madadhain
 531      */
 532     protected class SourceData
 533     {
 534         protected LinkedHashMap<V,Number> distances;
 535         protected Map<V,Number> estimatedDistances;
 536         protected MapBinaryHeap<V> unknownVertices;
 537         protected boolean reached_max = false;
 538         protected double dist_reached = 0;
 539
 540         protected SourceData(V source)
 541         {
 542             distances = new LinkedHashMap<V,Number>();
 543             estimatedDistances = new HashMap<V,Number>();
 544             unknownVertices = new MapBinaryHeap<V>(new VertexComparator<V>(estimatedDistances));
 545
 546             sourceMap.put(source, this);
 547
 548             // initialize priority queue
 549             estimatedDistances.put(source, new Double(0)); // distance from source to itself is 0
 550             unknownVertices.add(source);
 551             reached_max = false;
 552             dist_reached = 0;
 553         }
 554
 555         protected Map.Entry<V,Number> getNextVertex()
 556         {
 557             V v = unknownVertices.remove();
 558             Double dist = (Double)estimatedDistances.remove(v);
 559             distances.put(v, dist);
 560             return new BasicMapEntry<V,Number>(v, dist);
 561         }
 562
 563         protected void update(V dest, E tentative_edge, double new_dist)
 564         {
 565             estimatedDistances.put(dest, new_dist);
 566             unknownVertices.update(dest);
 567         }
 568
 569         protected void createRecord(V w, E e, double new_dist)
 570         {
 571             estimatedDistances.put(w, new_dist);
 572             unknownVertices.add(w);
 573         }
 574
 575         protected void restoreVertex(V v, double dist)
 576         {
 577             estimatedDistances.put(v, dist);
 578             unknownVertices.add(v);
 579             distances.remove(v);
 580         }
 581     }
 582 }