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 public List<E> getPath(V source, V target)
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 singleSourceShortestPath(source, targets, g.getVertexCount());
175 Map<V,E> incomingEdges =
176 ((SourcePathData)sourceMap.get(source)).incomingEdges;
177
178 if (incomingEdges.isEmpty() || incomingEdges.get(target) == null)
179 return path;
180 V current = target;
181 while (!current.equals(source))
182 {
183 E incoming = incomingEdges.get(current);
184 path.addFirst(incoming);
185 current = ((Graph<V,E>)g).getOpposite(current, incoming);
186 }
187 return path;
188 }
189
190
191 /**
192 * <p>Returns a <code>LinkedHashMap</code> which maps each of the closest
193 * <code>numDist</code> vertices to the <code>source</code> vertex
194 * in the graph (including the <code>source</code> vertex)
195 * to the incoming edge along the path from that vertex. Throws
196 * an <code>IllegalArgumentException</code> if <code>source</code>
197 * is not in this instance's graph, or if <code>numDests</code> is
198 * either less than 1 or greater than the number of vertices in the
199 * graph.
200 *
201 * @see #getIncomingEdgeMap(Object)
202 * @see #getPath(Object,Object)
203 * @param source the vertex from which distances are measured
204 * @param numDests the number of vertics for which to measure distances
205 */
206 public LinkedHashMap<V,E> getIncomingEdgeMap(V source, int numDests)
207 {
208 if (g.getVertices().contains(source) == false)
209 throw new IllegalArgumentException("Specified source vertex " +
210 source + " is not part of graph " + g);
211
212 if (numDests < 1 || numDests > g.getVertexCount())
213 throw new IllegalArgumentException("numDests must be >= 1 " +
214 "and <= g.numVertices()");
215
216 singleSourceShortestPath(source, null, numDests);
217
218 LinkedHashMap<V,E> incomingEdgeMap =
219 ((SourcePathData)sourceMap.get(source)).incomingEdges;
220
221 if (!cached)
222 reset(source);
223
224 return incomingEdgeMap;
225 }
226
227
228 /**
229 * For a given source vertex, holds the estimated and final distances,
230 * tentative and final assignments of incoming edges on the shortest path from
231 * the source vertex, and a priority queue (ordered by estimaed distance)
232 * of the vertices for which distances are unknown.
233 *
234 * @author Joshua O'Madadhain
235 */
236 protected class SourcePathData extends SourceData
237 {
238 protected Map<V,E> tentativeIncomingEdges;
239 protected LinkedHashMap<V,E> incomingEdges;
240
241 protected SourcePathData(V source)
242 {
243 super(source);
244 incomingEdges = new LinkedHashMap<V,E>();
245 tentativeIncomingEdges = new HashMap<V,E>();
246 }
247
248 @Override
249 public void update(V dest, E tentative_edge, double new_dist)
250 {
251 super.update(dest, tentative_edge, new_dist);
252 tentativeIncomingEdges.put(dest, tentative_edge);
253 }
254
255 @Override
256 public Map.Entry<V,Number> getNextVertex()
257 {
258 Map.Entry<V,Number> p = super.getNextVertex();
259 V v = p.getKey();
260 E incoming = tentativeIncomingEdges.remove(v);
261 incomingEdges.put(v, incoming);
262 return p;
263 }
264
265 @Override
266 public void restoreVertex(V v, double dist)
267 {
268 super.restoreVertex(v, dist);
269 E incoming = incomingEdges.get(v);
270 tentativeIncomingEdges.put(v, incoming);
271 }
272
273 @Override
274 public void createRecord(V w, E e, double new_dist)
275 {
276 super.createRecord(w, e, new_dist);
277 tentativeIncomingEdges.put(w, e);
278 }
279
280 }
281
282 }