# Coverage details for edu.uci.ics.jung.algorithms.shortestpath.DijkstraShortestPath

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. visit www.jcoverage.com for updates. | copyright © 2003, jcoverage ltd. all rights reserved. Java is a trademark of Sun Microsystems, Inc. in the United States and other countries.