Line | Hits | Source |
---|---|---|
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 edu.uci.ics.jung.graph.ArchetypeEdge; | |
21 | import edu.uci.ics.jung.graph.ArchetypeGraph; | |
22 | import edu.uci.ics.jung.graph.ArchetypeVertex; | |
23 | import edu.uci.ics.jung.graph.Edge; | |
24 | import edu.uci.ics.jung.graph.Vertex; | |
25 | import edu.uci.ics.jung.graph.decorators.NumberEdgeValue; | |
26 | import edu.uci.ics.jung.utils.Pair; | |
27 | ||
28 | /** | |
29 | * <p>Calculates distances and shortest paths using Dijkstra's | |
30 | * single-source-shortest-path algorithm. This is a lightweight | |
31 | * extension of <code>DijkstraDistance</code> that also stores | |
32 | * path information, so that the shortest paths can be reconstructed.</p> | |
33 | * | |
34 | * <p> The elements in the maps returned by | |
35 | * <code>getIncomingEdgeMap</code> are ordered (that is, returned | |
36 | * by the iterator) by nondecreasing distance from <code>source</code>.</p> | |
37 | * | |
38 | * @author Joshua O'Madadhain | |
39 | * @see DijkstraDistance | |
40 | */ | |
41 | public class DijkstraShortestPath extends DijkstraDistance implements ShortestPath | |
42 | { | |
43 | /** | |
44 | * <p>Creates an instance of <code>DijkstraShortestPath</code> for | |
45 | * the specified graph and the specified method of extracting weights | |
46 | * from edges, which caches results locally if and only if | |
47 | * <code>cached</code> is <code>true</code>. | |
48 | * | |
49 | * @param g the graph on which distances will be calculated | |
50 | * @param nev the class responsible for returning weights for edges | |
51 | * @param cached specifies whether the results are to be cached | |
52 | */ | |
53 | public DijkstraShortestPath(ArchetypeGraph g, NumberEdgeValue nev, boolean cached) | |
54 | { | |
55 | 40 | super(g, nev, cached); |
56 | 40 | } |
57 | ||
58 | /** | |
59 | * <p>Creates an instance of <code>DijkstraShortestPath</code> for | |
60 | * the specified graph and the specified method of extracting weights | |
61 | * from edges, which caches results locally. | |
62 | * | |
63 | * @param g the graph on which distances will be calculated | |
64 | * @param nev the class responsible for returning weights for edges | |
65 | */ | |
66 | public DijkstraShortestPath(ArchetypeGraph g, NumberEdgeValue nev) | |
67 | { | |
68 | 4 | super(g, nev); |
69 | 4 | } |
70 | ||
71 | /** | |
72 | * <p>Creates an instance of <code>DijkstraShortestPath</code> for | |
73 | * the specified unweighted graph (that is, all weights 1) which | |
74 | * caches results locally. | |
75 | * | |
76 | * @param g the graph on which distances will be calculated | |
77 | */ | |
78 | public DijkstraShortestPath(ArchetypeGraph g) | |
79 | { | |
80 | 0 | super(g); |
81 | 0 | } |
82 | ||
83 | /** | |
84 | * <p>Creates an instance of <code>DijkstraShortestPath</code> for | |
85 | * the specified unweighted graph (that is, all weights 1) which | |
86 | * caches results locally. | |
87 | * | |
88 | * @param g the graph on which distances will be calculated | |
89 | * @param cached specifies whether the results are to be cached | |
90 | */ | |
91 | public DijkstraShortestPath(ArchetypeGraph g, boolean cached) | |
92 | { | |
93 | 0 | super(g, cached); |
94 | 0 | } |
95 | ||
96 | protected SourceData getSourceData(ArchetypeVertex source) | |
97 | { | |
98 | 1702 | SourceData sd = (SourcePathData)sourceMap.get(source); |
99 | 1702 | if (sd == null) |
100 | 964 | sd = new SourcePathData(source); |
101 | 1702 | return sd; |
102 | } | |
103 | ||
104 | /** | |
105 | * <p>Returns the last edge on a shortest path from <code>source</code> | |
106 | * to <code>target</code>, or null if <code>target</code> is not | |
107 | * reachable from <code>source</code>.</p> | |
108 | * | |
109 | * <p>If either vertex is not in the graph for which this instance | |
110 | * was created, throws <code>IllegalArgumentException</code>.</p> | |
111 | */ | |
112 | public Edge getIncomingEdge(Vertex source, Vertex target) | |
113 | { | |
114 | 404 | if (source.getGraph() != g) |
115 | 2 | throw new IllegalArgumentException("Specified source vertex " + |
116 | source + " is not part of graph " + g); | |
117 | ||
118 | 402 | if (target.getGraph() != g) |
119 | 2 | throw new IllegalArgumentException("Specified target vertex " + |
120 | target + " is not part of graph " + g); | |
121 | ||
122 | 400 | Set targets = new HashSet(); |
123 | 400 | targets.add(target); |
124 | 400 | singleSourceShortestPath(source, targets, g.numVertices()); |
125 | 400 | Map incomingEdgeMap = |
126 | ((SourcePathData)sourceMap.get(source)).incomingEdges; | |
127 | 400 | Edge incomingEdge = (Edge)incomingEdgeMap.get(target); |
128 | ||
129 | 400 | if (!cached) |
130 | 200 | reset(source); |
131 | ||
132 | 400 | return incomingEdge; |
133 | } | |
134 | ||
135 | /** | |
136 | * <p>Returns a <code>LinkedHashMap</code> which maps each vertex | |
137 | * in the graph (including the <code>source</code> vertex) | |
138 | * to the last edge on the shortest path from the | |
139 | * <code>source</code> vertex. | |
140 | * The map's iterator will return the elements in order of | |
141 | * increasing distance from <code>source</code>.</p> | |
142 | * | |
143 | * @see DijkstraDistance#getDistanceMap(Vertex,int) | |
144 | * @see DijkstraDistance#getDistance(Vertex,Vertex) | |
145 | * @param source the vertex from which distances are measured | |
146 | */ | |
147 | public Map getIncomingEdgeMap(Vertex source) | |
148 | { | |
149 | 40 | return getIncomingEdgeMap(source, g.numVertices()); |
150 | } | |
151 | ||
152 | /** | |
153 | * Returns a <code>List</code> of the edges on the shortest path from | |
154 | * <code>source</code> to <code>target</code>, in order of their | |
155 | * occurrence on this path. | |
156 | * If either vertex is not in the graph for which this instance | |
157 | * was created, throws <code>IllegalArgumentException</code>. | |
158 | */ | |
159 | public List getPath(Vertex source, Vertex target) | |
160 | { | |
161 | 20 | if (source.getGraph() != g) |
162 | 0 | throw new IllegalArgumentException("Specified source vertex " + |
163 | source + " is not part of graph " + g); | |
164 | ||
165 | 20 | if (target.getGraph() != g) |
166 | 0 | throw new IllegalArgumentException("Specified target vertex " + |
167 | target + " is not part of graph " + g); | |
168 | ||
169 | 20 | LinkedList path = new LinkedList(); |
170 | ||
171 | // collect path data; must use internal method rather than | |
172 | // calling getIncomingEdge() because getIncomingEdge() may | |
173 | // wipe out results if results are not cached | |
174 | 20 | Set targets = new HashSet(); |
175 | 20 | targets.add(target); |
176 | 20 | singleSourceShortestPath(source, targets, g.numVertices()); |
177 | 20 | Map incomingEdges = |
178 | ((SourcePathData)sourceMap.get(source)).incomingEdges; | |
179 | ||
180 | 20 | if (incomingEdges.isEmpty() || incomingEdges.get(target) == null) |
181 | 8 | return path; |
182 | 12 | Vertex current = target; |
183 | 34 | while (current != source) |
184 | { | |
185 | 22 | Edge incoming = (Edge)incomingEdges.get(current); |
186 | 22 | path.addFirst(incoming); |
187 | 22 | current = incoming.getOpposite(current); |
188 | } | |
189 | 12 | return path; |
190 | } | |
191 | ||
192 | ||
193 | /** | |
194 | * <p>Returns a <code>LinkedHashMap</code> which maps each of the closest | |
195 | * <code>numDist</code> vertices to the <code>source</code> vertex | |
196 | * in the graph (including the <code>source</code> vertex) | |
197 | * to the incoming edge along the path from that vertex. Throws | |
198 | * an <code>IllegalArgumentException</code> if <code>source</code> | |
199 | * is not in this instance's graph, or if <code>numDests</code> is | |
200 | * either less than 1 or greater than the number of vertices in the | |
201 | * graph. | |
202 | * | |
203 | * @see #getIncomingEdgeMap(Vertex) | |
204 | * @see #getPath(Vertex,Vertex) | |
205 | * @param source the vertex from which distances are measured | |
206 | * @param numDests the number of vertics for which to measure distances | |
207 | */ | |
208 | public LinkedHashMap getIncomingEdgeMap(Vertex source, int numDests) | |
209 | { | |
210 | 444 | if (source.getGraph() != g) |
211 | 2 | throw new IllegalArgumentException("Specified source vertex " + |
212 | source + " is not part of graph " + g); | |
213 | ||
214 | 442 | if (numDests < 1 || numDests > g.numVertices()) |
215 | 2 | throw new IllegalArgumentException("numDests must be >= 1 " + |
216 | "and <= g.numVertices()"); | |
217 | ||
218 | 440 | singleSourceShortestPath(source, null, numDests); |
219 | ||
220 | 440 | LinkedHashMap incomingEdgeMap = |
221 | ((SourcePathData)sourceMap.get(source)).incomingEdges; | |
222 | ||
223 | 440 | if (!cached) |
224 | 220 | reset(source); |
225 | ||
226 | 440 | return incomingEdgeMap; |
227 | } | |
228 | ||
229 | ||
230 | /** | |
231 | * For a given source vertex, holds the estimated and final distances, | |
232 | * tentative and final assignments of incoming edges on the shortest path from | |
233 | * the source vertex, and a priority queue (ordered by estimaed distance) | |
234 | * of the vertices for which distances are unknown. | |
235 | * | |
236 | * @author Joshua O'Madadhain | |
237 | */ | |
238 | protected class SourcePathData extends SourceData | |
239 | { | |
240 | public Map tentativeIncomingEdges; | |
241 | public LinkedHashMap incomingEdges; | |
242 | ||
243 | public SourcePathData(ArchetypeVertex source) | |
244 | { | |
245 | super(source); | |
246 | incomingEdges = new LinkedHashMap(); | |
247 | tentativeIncomingEdges = new HashMap(); | |
248 | } | |
249 | ||
250 | public void update(ArchetypeVertex dest, ArchetypeEdge tentative_edge, double new_dist) | |
251 | { | |
252 | super.update(dest, tentative_edge, new_dist); | |
253 | tentativeIncomingEdges.put(dest, tentative_edge); | |
254 | } | |
255 | ||
256 | public Pair getNextVertex() | |
257 | { | |
258 | Pair p = super.getNextVertex(); | |
259 | ArchetypeVertex v = (ArchetypeVertex)p.getFirst(); | |
260 | Edge incoming = (Edge)tentativeIncomingEdges.remove(v); | |
261 | incomingEdges.put(v, incoming); | |
262 | return p; | |
263 | } | |
264 | ||
265 | public void createRecord(ArchetypeVertex w, ArchetypeEdge e, double new_dist) | |
266 | { | |
267 | super.createRecord(w, e, new_dist); | |
268 | tentativeIncomingEdges.put(w, e); | |
269 | } | |
270 | ||
271 | } | |
272 | ||
273 | } |
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |