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

   1 /*
   2 * Copyright (c) 2003, the JUNG Project and the Regents of the University
   3 * of California
   4 * All rights reserved.
   5 *
   6 * This software is open-source under the BSD license; see either
   7 * "license.txt" or
   8 * http://jung.sourceforge.net/license.txt for a description.
   9 */
  10 package edu.uci.ics.jung.algorithms.shortestpath;
  11
  12 import java.util.HashMap;
  13 import java.util.HashSet;
  14 import java.util.LinkedHashMap;
  15 import java.util.LinkedList;
  16 import java.util.List;
  17 import java.util.Map;
  18 import java.util.Set;
  19
  20 import org.apache.commons.collections15.Transformer;
  21
  22 import edu.uci.ics.jung.graph.Graph;
  23
  24 /**
  25  * <p>Calculates distances and shortest paths using Dijkstra's
  26  * single-source-shortest-path algorithm.  This is a lightweight
  27  * extension of <code>DijkstraDistance</code> that also stores
  28  * path information, so that the shortest paths can be reconstructed.</p>
  29  *
  30  * <p> The elements in the maps returned by
  31  * <code>getIncomingEdgeMap</code> are ordered (that is, returned
  32  * by the iterator) by nondecreasing distance from <code>source</code>.</p>
  33  *
  34  * @author Joshua O'Madadhain
  35  * @author Tom Nelson converted to jung2
  36  * @see DijkstraDistance
  37  */
  38 public class DijkstraShortestPath<V,E> extends DijkstraDistance<V,E> implements ShortestPath<V,E>
  39 {
  40     /**
  41      * <p>Creates an instance of <code>DijkstraShortestPath</code> for
  42      * the specified graph and the specified method of extracting weights
  43      * from edges, which caches results locally if and only if
  44      * <code>cached</code> is <code>true</code>.
  45      *
  46      * @param g     the graph on which distances will be calculated
  47      * @param nev   the class responsible for returning weights for edges
  48      * @param cached    specifies whether the results are to be cached
  49      */
  50     public DijkstraShortestPath(Graph<V,E> g, Transformer<E, ? extends Number> nev, boolean cached)
  51     {
  52         super(g, nev, cached);
  53     }
  54
  55     /**
  56      * <p>Creates an instance of <code>DijkstraShortestPath</code> for
  57      * the specified graph and the specified method of extracting weights
  58      * from edges, which caches results locally.
  59      *
  60      * @param g     the graph on which distances will be calculated
  61      * @param nev   the class responsible for returning weights for edges
  62      */
  63     public DijkstraShortestPath(Graph<V,E> g, Transformer<E, ? extends Number> nev)
  64     {
  65         super(g, nev);
  66     }
  67
  68     /**
  69      * <p>Creates an instance of <code>DijkstraShortestPath</code> for
  70      * the specified unweighted graph (that is, all weights 1) which
  71      * caches results locally.
  72      *
  73      * @param g     the graph on which distances will be calculated
  74      */
  75     public DijkstraShortestPath(Graph<V,E> g)
  76     {
  77         super(g);
  78     }
  79
  80     /**
  81      * <p>Creates an instance of <code>DijkstraShortestPath</code> for
  82      * the specified unweighted graph (that is, all weights 1) which
  83      * caches results locally.
  84      *
  85      * @param g     the graph on which distances will be calculated
  86      * @param cached    specifies whether the results are to be cached
  87      */
  88     public DijkstraShortestPath(Graph<V,E> g, boolean cached)
  89     {
  90         super(g, cached);
  91     }
  92
  93     @Override
  94     protected SourceData getSourceData(V source)
  95     {
  96         SourceData sd = sourceMap.get(source);
  97         if (sd == null)
  98             sd = new SourcePathData(source);
  99         return sd;
 100     }
 101
 102     /**
 103      * <p>Returns the last edge on a shortest path from <code>source</code>
 104      * to <code>target</code>, or null if <code>target</code> is not
 105      * reachable from <code>source</code>.</p>
 106      *
 107      * <p>If either vertex is not in the graph for which this instance
 108      * was created, throws <code>IllegalArgumentException</code>.</p>
 109      */
 110         public E getIncomingEdge(V source, V target)
 111         {
 112         if (!g.containsVertex(source))
 113             throw new IllegalArgumentException("Specified source vertex " +
 114                     source + " is not part of graph " + g);
 115
 116         if (!g.containsVertex(target))
 117             throw new IllegalArgumentException("Specified target vertex " +
 118                     target + " is not part of graph " + g);
 119
 120         Set<V> targets = new HashSet<V>();
 121         targets.add(target);
 122         singleSourceShortestPath(source, targets, g.getVertexCount());
 123         Map<V,E> incomingEdgeMap =
 124             ((SourcePathData)sourceMap.get(source)).incomingEdges;
 125         E incomingEdge = incomingEdgeMap.get(target);
 126
 127         if (!cached)
 128             reset(source);
 129
 130         return incomingEdge;
 131         }
 132
 133     /**
 134      * <p>Returns a <code>LinkedHashMap</code> which maps each vertex
 135      * in the graph (including the <code>source</code> vertex)
 136      * to the last edge on the shortest path from the
 137      * <code>source</code> vertex.
 138      * The map's iterator will return the elements in order of
 139      * increasing distance from <code>source</code>.</p>
 140      *
 141      * @see DijkstraDistance#getDistanceMap(Object,int)
 142      * @see DijkstraDistance#getDistance(Object,Object)
 143      * @param source    the vertex from which distances are measured
 144      */
 145     public Map<V,E> getIncomingEdgeMap(V source)
 146         {
 147                 return getIncomingEdgeMap(source, g.getVertexCount());
 148         }
 149
 150     /**
 151      * Returns a <code>List</code> of the edges on the shortest path from
 152      * <code>source</code> to <code>target</code>, in order of their
 153      * occurrence on this path.
 154      * If either vertex is not in the graph for which this instance
 155      * was created, throws <code>IllegalArgumentException</code>.
 156      */
 157         private List<E> getPath(V source, V target, boolean spath)
 158         {
 159                 if(!g.containsVertex(source))
 160             throw new IllegalArgumentException("Specified source vertex " +
 161                     source + " is not part of graph " + g);
 162
 163                 if(!g.containsVertex(target))
 164             throw new IllegalArgumentException("Specified target vertex " +
 165                     target + " is not part of graph " + g);
 166
 167         LinkedList<E> path = new LinkedList<E>();
 168
 169         // collect path data; must use internal method rather than
 170         // calling getIncomingEdge() because getIncomingEdge() may
 171         // wipe out results if results are not cached
 172         Set<V> targets = new HashSet<V>();
 173         targets.add(target);
 174         if (spath == true) {
 175           singleSourceShortestPath(source, targets, g.getVertexCount());
 176         } else {
 177           singleSourceMaxThroughputPath(source, targets, g.getVertexCount());
 178         }
 179         Map<V,E> incomingEdges =
 180             ((SourcePathData)sourceMap.get(source)).incomingEdges;
 181
 182         if (incomingEdges.isEmpty() || incomingEdges.get(target) == null)
 183             return path;
 184         V current = target;
 185         while (!current.equals(source))
 186         {
 187             E incoming = incomingEdges.get(current);
 188             path.addFirst(incoming);
 189             current = ((Graph<V,E>)g).getOpposite(current, incoming);
 190         }
 191                 return path;
 192         }
 193
 194     /**
 195      * Returns a <code>List</code> of the edges on the shortest path from
 196      * <code>source</code> to <code>target</code>, in order of their
 197      * occurrence on this path.
 198      * If either vertex is not in the graph for which this instance
 199      * was created, throws <code>IllegalArgumentException</code>.
 200      */
 201         public List<E> getPath(V source, V target)
 202         {
 203
 204                 return getPath(source,target, true);
 205         }
 206
 207     /**
 208      * Returns a <code>List</code> of the edges on the Max Througput Shortest
 209      * path from  <code>source</code> to <code>target</code>, in order of their
 210      * their occurrence on this path.
 211      * Important - Transformer fn should return the appropriate edge weight
 212      * for this API to return the Path Correctly.
 213      * If either vertex is not in the graph for which this instance
 214      * was created, throws <code>IllegalArgumentException</code>.
 215      */
 216         public List<E> getMaxThroughputPath(V source, V target)
 217         {
 218
 219                 return getPath(source,target, false);
 220         }
 221
 222
 223     /**
 224      * <p>Returns a <code>LinkedHashMap</code> which maps each of the closest
 225      * <code>numDist</code> vertices to the <code>source</code> vertex
 226      * in the graph (including the <code>source</code> vertex)
 227      * to the incoming edge along the path from that vertex.  Throws
 228      * an <code>IllegalArgumentException</code> if <code>source</code>
 229      * is not in this instance's graph, or if <code>numDests</code> is
 230      * either less than 1 or greater than the number of vertices in the
 231      * graph.
 232      *
 233      * @see #getIncomingEdgeMap(Object)
 234      * @see #getPath(Object,Object)
 235      * @param source    the vertex from which distances are measured
 236      * @param numDests  the number of vertices for which to measure distances
 237      */
 238         public LinkedHashMap<V,E> getIncomingEdgeMap(V source, int numDests)
 239         {
 240         if (g.getVertices().contains(source) == false)
 241             throw new IllegalArgumentException("Specified source vertex " +
 242                     source + " is not part of graph " + g);
 243
 244         if (numDests < 1 || numDests > g.getVertexCount())
 245             throw new IllegalArgumentException("numDests must be >= 1 " +
 246             "and <= g.numVertices()");
 247
 248         singleSourceShortestPath(source, null, numDests);
 249
 250         LinkedHashMap<V,E> incomingEdgeMap =
 251             ((SourcePathData)sourceMap.get(source)).incomingEdges;
 252
 253         if (!cached)
 254             reset(source);
 255
 256         return incomingEdgeMap;
 257         }
 258
 259
 260     /**
 261      * For a given source vertex, holds the estimated and final distances,
 262      * tentative and final assignments of incoming edges on the shortest path from
 263      * the source vertex, and a priority queue (ordered by estimaed distance)
 264      * of the vertices for which distances are unknown.
 265      *
 266      * @author Joshua O'Madadhain
 267      */
 268     protected class SourcePathData extends SourceData
 269     {
 270         protected Map<V,E> tentativeIncomingEdges;
 271                 protected LinkedHashMap<V,E> incomingEdges;
 272
 273                 protected SourcePathData(V source)
 274                 {
 275             super(source);
 276             incomingEdges = new LinkedHashMap<V,E>();
 277             tentativeIncomingEdges = new HashMap<V,E>();
 278                 }
 279
 280         @Override
 281         public void update(V dest, E tentative_edge, double new_dist)
 282         {
 283             super.update(dest, tentative_edge, new_dist);
 284             tentativeIncomingEdges.put(dest, tentative_edge);
 285         }
 286
 287         @Override
 288         public Map.Entry<V,Number> getNextVertex()
 289         {
 290             Map.Entry<V,Number> p = super.getNextVertex();
 291             V v = p.getKey();
 292             E incoming = tentativeIncomingEdges.remove(v);
 293             incomingEdges.put(v, incoming);
 294             return p;
 295         }
 296
 297         @Override
 298         public void restoreVertex(V v, double dist)
 299         {
 300             super.restoreVertex(v, dist);
 301             E incoming = incomingEdges.get(v);
 302             tentativeIncomingEdges.put(v, incoming);
 303         }
 304
 305         @Override
 306         public void createRecord(V w, E e, double new_dist)
 307         {
 308             super.createRecord(w, e, new_dist);
 309             tentativeIncomingEdges.put(w, e);
 310         }
 311
 312     }
 313
 314 }