2 * Copyright (c) 2003, the JUNG Project and the Regents of the University
6 * This software is open-source under the BSD license; see either
8 * http://jung.sourceforge.net/license.txt for a description.
10 package edu.uci.ics.jung.algorithms.shortestpath;
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;
20 import org.apache.commons.collections15.Transformer;
22 import edu.uci.ics.jung.graph.Graph;
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>
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>
34 * @author Joshua O'Madadhain
35 * @author Tom Nelson converted to jung2
36 * @see DijkstraDistance
38 public class DijkstraShortestPath<V,E> extends DijkstraDistance<V,E> implements ShortestPath<V,E>
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>.
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
50 public DijkstraShortestPath(Graph<V,E> g, Transformer<E, ? extends Number> nev, boolean cached)
52 super(g, nev, cached);
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.
60 * @param g the graph on which distances will be calculated
61 * @param nev the class responsible for returning weights for edges
63 public DijkstraShortestPath(Graph<V,E> g, Transformer<E, ? extends Number> nev)
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.
73 * @param g the graph on which distances will be calculated
75 public DijkstraShortestPath(Graph<V,E> g)
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.
85 * @param g the graph on which distances will be calculated
86 * @param cached specifies whether the results are to be cached
88 public DijkstraShortestPath(Graph<V,E> g, boolean cached)
94 protected SourceData getSourceData(V source)
96 SourceData sd = sourceMap.get(source);
98 sd = new SourcePathData(source);
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>
107 * <p>If either vertex is not in the graph for which this instance
108 * was created, throws <code>IllegalArgumentException</code>.</p>
110 public E getIncomingEdge(V source, V target)
112 if (!g.containsVertex(source))
113 throw new IllegalArgumentException("Specified source vertex " +
114 source + " is not part of graph " + g);
116 if (!g.containsVertex(target))
117 throw new IllegalArgumentException("Specified target vertex " +
118 target + " is not part of graph " + g);
120 Set<V> targets = new HashSet<V>();
122 singleSourceShortestPath(source, targets, g.getVertexCount());
123 Map<V,E> incomingEdgeMap =
124 ((SourcePathData)sourceMap.get(source)).incomingEdges;
125 E incomingEdge = incomingEdgeMap.get(target);
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>
141 * @see DijkstraDistance#getDistanceMap(Object,int)
142 * @see DijkstraDistance#getDistance(Object,Object)
143 * @param source the vertex from which distances are measured
145 public Map<V,E> getIncomingEdgeMap(V source)
147 return getIncomingEdgeMap(source, g.getVertexCount());
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>.
157 private List<E> getPath(V source, V target, boolean spath)
159 if(!g.containsVertex(source))
160 throw new IllegalArgumentException("Specified source vertex " +
161 source + " is not part of graph " + g);
163 if(!g.containsVertex(target))
164 throw new IllegalArgumentException("Specified target vertex " +
165 target + " is not part of graph " + g);
167 LinkedList<E> path = new LinkedList<E>();
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>();
175 singleSourceShortestPath(source, targets, g.getVertexCount());
177 singleSourceMaxThroughputPath(source, targets, g.getVertexCount());
179 Map<V,E> incomingEdges =
180 ((SourcePathData)sourceMap.get(source)).incomingEdges;
182 if (incomingEdges.isEmpty() || incomingEdges.get(target) == null)
185 while (!current.equals(source))
187 E incoming = incomingEdges.get(current);
188 path.addFirst(incoming);
189 current = ((Graph<V,E>)g).getOpposite(current, incoming);
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>.
201 public List<E> getPath(V source, V target)
204 return getPath(source,target, true);
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>.
216 public List<E> getMaxThroughputPath(V source, V target)
219 return getPath(source,target, false);
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
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
238 public LinkedHashMap<V,E> getIncomingEdgeMap(V source, int numDests)
240 if (g.getVertices().contains(source) == false)
241 throw new IllegalArgumentException("Specified source vertex " +
242 source + " is not part of graph " + g);
244 if (numDests < 1 || numDests > g.getVertexCount())
245 throw new IllegalArgumentException("numDests must be >= 1 " +
246 "and <= g.numVertices()");
248 singleSourceShortestPath(source, null, numDests);
250 LinkedHashMap<V,E> incomingEdgeMap =
251 ((SourcePathData)sourceMap.get(source)).incomingEdges;
256 return incomingEdgeMap;
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.
266 * @author Joshua O'Madadhain
268 protected class SourcePathData extends SourceData
270 protected Map<V,E> tentativeIncomingEdges;
271 protected LinkedHashMap<V,E> incomingEdges;
273 protected SourcePathData(V source)
276 incomingEdges = new LinkedHashMap<V,E>();
277 tentativeIncomingEdges = new HashMap<V,E>();
281 public void update(V dest, E tentative_edge, double new_dist)
283 super.update(dest, tentative_edge, new_dist);
284 tentativeIncomingEdges.put(dest, tentative_edge);
288 public Map.Entry<V,Number> getNextVertex()
290 Map.Entry<V,Number> p = super.getNextVertex();
292 E incoming = tentativeIncomingEdges.remove(v);
293 incomingEdges.put(v, incoming);
298 public void restoreVertex(V v, double dist)
300 super.restoreVertex(v, dist);
301 E incoming = incomingEdges.get(v);
302 tentativeIncomingEdges.put(v, incoming);
306 public void createRecord(V w, E e, double new_dist)
308 super.createRecord(w, e, new_dist);
309 tentativeIncomingEdges.put(w, e);