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

Line | Hits | Source
--- | --- | ---
1 |  | `/*`
2 |  | `* Created on Jul 9, 2005`
3 |  | `*`
4 |  | `* Copyright (c) 2005, the JUNG Project and the Regents of the University`
5 |  | `* of California`
6 |  | `* All rights reserved.`
7 |  | `*`
8 |  | `* This software is open-source under the BSD license; see either`
9 |  | `* "license.txt" or`
10 |  | `* http://jung.sourceforge.net/license.txt for a description.`
11 |  | `*/`
12 |  | `package edu.uci.ics.jung.algorithms.shortestpath;`
13 |  | ``
14 |  | `import java.util.Comparator;`
15 |  | `import java.util.HashMap;`
16 |  | `import java.util.HashSet;`
17 |  | `import java.util.Iterator;`
18 |  | `import java.util.LinkedHashMap;`
19 |  | `import java.util.Map;`
20 |  | `import java.util.Set;`
21 |  | ``
22 |  | `import edu.uci.ics.jung.graph.ArchetypeEdge;`
23 |  | `import edu.uci.ics.jung.graph.ArchetypeGraph;`
24 |  | `import edu.uci.ics.jung.graph.ArchetypeVertex;`
25 |  | `import edu.uci.ics.jung.graph.Hypervertex;`
26 |  | `import edu.uci.ics.jung.graph.Vertex;`
27 |  | `import edu.uci.ics.jung.graph.decorators.ConstantEdgeValue;`
28 |  | `import edu.uci.ics.jung.graph.decorators.NumberEdgeValue;`
29 |  | `import edu.uci.ics.jung.utils.MapBinaryHeap;`
30 |  | `import edu.uci.ics.jung.utils.Pair;`
31 |  | ``
32 |  | `/**`
33 |  | `* <p>Calculates distances in a specified graph, using`
34 |  | `* Dijkstra's single-source-shortest-path algorithm. All edge weights`
35 |  | `* in the graph must be nonnegative; if any edge with negative weight is`
36 |  | `* found in the course of calculating distances, an`
37 |  | `* <code>IllegalArgumentException</code> will be thrown.`
38 |  | `* (Note: this exception will only be thrown when such an edge would be`
39 |  | `* used to update a given tentative distance;`
40 |  | `* the algorithm does not check for negative-weight edges "up front".)`
41 |  | `*`
42 |  | `* <p>Distances and partial results are optionally cached (by this instance)`
43 |  | `* for later reference. Thus, if the 10 closest vertices to a specified source`
44 |  | `* vertex are known, calculating the 20 closest vertices does not require`
45 |  | `* starting Dijkstra's algorithm over from scratch.</p>`
46 |  | `*`
47 |  | `* <p>Distances are stored as double-precision values.`
48 |  | `* If a vertex is not reachable from the specified source vertex, no`
49 |  | `* distance is stored. <b>This is new behavior with version 1.4</b>;`
50 |  | `* the previous behavior was to store a value of`
51 |  | `* <code>Double.POSITIVE_INFINITY</code>. This change gives the algorithm`
52 |  | `* an approximate complexity of O(kD log k), where k is either the number of`
53 |  | `* requested targets or the number of reachable vertices (whichever is smaller),`
54 |  | `* and D is the average degree of a vertex.</p>`
55 |  | `*`
56 |  | `* <p> The elements in the maps returned by <code>getDistanceMap</code>`
57 |  | `* are ordered (that is, returned`
58 |  | `* by the iterator) by nondecreasing distance from <code>source</code>.</p>`
59 |  | `*`
60 |  | `* <p>Users are cautioned that distances calculated should be assumed to`
61 |  | `* be invalidated by changes to the graph, and should invoke <code>reset()</code>`
62 |  | `* when appropriate so that the distances can be recalculated.</p>`
63 |  | `*`
64 |  | `* @author Joshua O'Madadhain`
65 |  | `*/`
66 |  | `public class DijkstraDistance implements Distance`
67 |  | `{`
68 |  | `protected ArchetypeGraph g;`
69 |  | `protected NumberEdgeValue nev;`
70 |  | `protected Map sourceMap; // a map of source vertices to an instance of SourceData`
71 |  | `protected boolean cached;`
72 | 1 | `protected static final NumberEdgeValue dev = new ConstantEdgeValue(new Integer(1));`
73 |  | `protected double max_distance;`
74 |  | `protected int max_targets;`
75 |  | ``
76 |  | `/**`
77 |  | `* <p>Creates an instance of <code>DijkstraShortestPath</code> for`
78 |  | `* the specified graph and the specified method of extracting weights`
79 |  | `* from edges, which caches results locally if and only if`
80 |  | `* <code>cached</code> is <code>true</code>.`
81 |  | `*`
82 |  | `* @param g the graph on which distances will be calculated`
83 |  | `* @param nev the class responsible for returning weights for edges`
84 |  | `* @param cached specifies whether the results are to be cached`
85 |  | `*/`
86 |  | `public DijkstraDistance(ArchetypeGraph g, NumberEdgeValue nev, boolean cached)`
87 | 44 | `{`
88 | 44 | `this.g = g;`
89 | 44 | `this.nev = nev;`
90 | 44 | `this.sourceMap = new HashMap();`
91 | 44 | `this.cached = cached;`
92 | 44 | `this.max_distance = Double.POSITIVE_INFINITY;`
93 | 44 | `this.max_targets = Integer.MAX_VALUE;`
94 | 44 | `}`
95 |  | ``
96 |  | `/**`
97 |  | `* <p>Creates an instance of <code>DijkstraShortestPath</code> for`
98 |  | `* the specified graph and the specified method of extracting weights`
99 |  | `* from edges, which caches results locally.`
100 |  | `*`
101 |  | `* @param g the graph on which distances will be calculated`
102 |  | `* @param nev the class responsible for returning weights for edges`
103 |  | `*/`
104 |  | `public DijkstraDistance(ArchetypeGraph g, NumberEdgeValue nev)`
105 |  | `{`
106 | 4 | `this(g, nev, true);`
107 | 4 | `}`
108 |  | ``
109 |  | `/**`
110 |  | `* <p>Creates an instance of <code>DijkstraShortestPath</code> for`
111 |  | `* the specified unweighted graph (that is, all weights 1) which`
112 |  | `* caches results locally.`
113 |  | `*`
114 |  | `* @param g the graph on which distances will be calculated`
115 |  | `*/`
116 |  | `public DijkstraDistance(ArchetypeGraph g)`
117 |  | `{`
118 | 0 | `this(g, dev, true);`
119 | 0 | `}`
120 |  | ``
121 |  | `/**`
122 |  | `* <p>Creates an instance of <code>DijkstraShortestPath</code> for`
123 |  | `* the specified unweighted graph (that is, all weights 1) which`
124 |  | `* caches results locally.`
125 |  | `*`
126 |  | `* @param g the graph on which distances will be calculated`
127 |  | `* @param cached specifies whether the results are to be cached`
128 |  | `*/`
129 |  | `public DijkstraDistance(ArchetypeGraph g, boolean cached)`
130 |  | `{`
131 | 0 | `this(g, dev, cached);`
132 | 0 | `}`
133 |  | ``
134 |  | `/**`
135 |  | `* Implements Dijkstra's single-source shortest-path algorithm for`
136 |  | `* weighted graphs. Uses a <code>MapBinaryHeap</code> as the priority queue,`
137 |  | `* which gives this algorithm a time complexity of O(m lg n) (m = # of edges, n =`
138 |  | `* # of vertices).`
139 |  | `* This algorithm will terminate when any of the following have occurred (in order`
140 |  | `* of priority):`
141 |  | `* <ul>`
142 |  | `* <li> the distance to the specified target (if any) has been found`
143 |  | `* <li/> no more vertices are reachable`
144 |  | `* <li> the specified # of distances have been found`
145 |  | `* <li> all distances have been found`
146 |  | `* </ul>`
147 |  | `*`
148 |  | `* @param source the vertex from which distances are to be measured`
149 |  | `* @param numDests the number of distances to measure`
150 |  | `* @param targets the set of vertices to which distances are to be measured`
151 |  | `*/`
152 |  | `protected LinkedHashMap singleSourceShortestPath(ArchetypeVertex source, Set targets, int numDests)`
153 |  | `{`
154 | 1702 | `SourceData sd = getSourceData(source);`
155 |  | ``
156 | 1702 | `Set to_get = new HashSet();`
157 | 1702 | `if (targets != null)`
158 |  | `{`
159 | 820 | `to_get.addAll(targets);`
160 | 820 | `Set existing_dists = sd.distances.keySet();`
161 | 820 | `for (Iterator iter = targets.iterator(); iter.hasNext(); )`
162 |  | `{`
163 | 820 | `Object o = iter.next();`
164 | 820 | `if (existing_dists.contains(o))`
165 | 192 | `to_get.remove(o);`
166 |  | `}`
167 |  | `}`
168 |  | ``
169 |  | `// if we've exceeded the max distance or max # of distances we're willing to calculate, or`
170 |  | `// if we already have all the distances we need,`
171 |  | `// terminate`
172 | 1702 | `if (sd.reached_max ||`
173 |  | `(targets != null && to_get.isEmpty()) ||`
174 |  | `(sd.distances.size() >= numDests))`
175 |  | `{`
176 | 192 | `return sd.distances;`
177 |  | `}`
178 |  | ``
179 | 5866 | `while (!sd.unknownVertices.isEmpty() && (sd.distances.size() < numDests || !to_get.isEmpty()))`
180 |  | `{`
181 | 4358 | `Pair p = sd.getNextVertex();`
182 | 4358 | `ArchetypeVertex v = (ArchetypeVertex)p.getFirst();`
183 | 4358 | `double v_dist = ((Double)p.getSecond()).doubleValue();`
184 | 4358 | `sd.dist_reached = v_dist;`
185 | 4358 | `to_get.remove(v);`
186 | 4358 | `if ((sd.dist_reached >= this.max_distance) || (sd.distances.size() >= max_targets))`
187 |  | `{`
188 | 0 | `sd.reached_max = true;`
189 | 0 | `break;`
190 |  | `}`
191 |  | ``
192 | 4358 | `for (Iterator out_iter = getIncidentEdges(v).iterator(); out_iter.hasNext(); )`
193 |  | `{`
194 | 10619 | `ArchetypeEdge e = (ArchetypeEdge)out_iter.next();`
195 |  | `// Vertex w = e.getOpposite(v);`
196 | 10619 | `for (Iterator e_iter = e.getIncidentVertices().iterator(); e_iter.hasNext(); )`
197 |  | `{`
198 | 21238 | `ArchetypeVertex w = (ArchetypeVertex)e_iter.next();`
199 | 21238 | `if (!sd.distances.containsKey(w))`
200 |  | `{`
201 | 6289 | `double edge_weight = nev.getNumber(e).doubleValue();`
202 | 6289 | `if (edge_weight < 0)`
203 | 2 | `throw new IllegalArgumentException("Edge weights must be non-negative");`
204 | 6287 | `double new_dist = v_dist + edge_weight;`
205 | 6287 | `if (!sd.estimatedDistances.containsKey(w))`
206 |  | `{`
207 | 3793 | `sd.createRecord(w, e, new_dist);`
208 |  | `}`
209 |  | `else`
210 |  | `{`
211 | 2494 | `double w_dist = ((Double)sd.estimatedDistances.get(w)).doubleValue();`
212 | 2494 | `if (new_dist < w_dist) // update tentative distance & path for w`
213 | 1021 | `sd.update(w, e, new_dist);`
214 |  | `}`
215 |  | `}`
216 |  | `}`
217 |  | `}`
218 |  | `// // if we have calculated the distance to the target, stop`
219 |  | `// if (v == target)`
220 |  | `// break;`
221 |  | ``
222 |  | `}`
223 | 1508 | `return sd.distances;`
224 |  | `}`
225 |  | ``
226 |  | `protected SourceData getSourceData(ArchetypeVertex source)`
227 |  | `{`
228 | 0 | `SourceData sd = (SourceData)sourceMap.get(source);`
229 | 0 | `if (sd == null)`
230 | 0 | `sd = new SourceData(source);`
231 | 0 | `return sd;`
232 |  | `}`
233 |  | ``
234 |  | `/**`
235 |  | `* Returns the set of edges incident to <code>v</code> that should be tested.`
236 |  | `* By default, this is the set of outgoing edges for instances of <code>Vertex</code>,`
237 |  | `* the set of incident edges for instances of <code>Hypervertex</code>,`
238 |  | `* and is otherwise undefined.`
239 |  | `*/`
240 |  | `protected Set getIncidentEdges(ArchetypeVertex v)`
241 |  | `{`
242 | 4358 | `if (v instanceof Vertex)`
243 | 4358 | `return ((Vertex)v).getOutEdges();`
244 | 0 | `else if (v instanceof Hypervertex)`
245 | 0 | `return v.getIncidentEdges();`
246 |  | `else`
247 | 0 | `throw new IllegalArgumentException("Unrecognized vertex type: " + v.getClass().getName());`
248 |  | `}`
249 |  | ``
250 |  | ``
251 |  | `/**`
252 |  | `* Returns the length of a shortest path from the source to the target vertex,`
253 |  | `* or null if the target is not reachable from the source.`
254 |  | `* If either vertex is not in the graph for which this instance`
255 |  | `* was created, throws <code>IllegalArgumentException</code>.`
256 |  | `*`
257 |  | `* @see #getDistanceMap(ArchetypeVertex)`
258 |  | `* @see #getDistanceMap(ArchetypeVertex,int)`
259 |  | `*/`
260 |  | `public Number getDistance(ArchetypeVertex source, ArchetypeVertex target)`
261 |  | `{`
262 | 404 | `if (target.getGraph() != g)`
263 | 2 | `throw new IllegalArgumentException("Specified target vertex " +`
264 |  | `target + " is not part of graph " + g);`
265 |  | ``
266 | 402 | `Set targets = new HashSet();`
267 | 402 | `targets.add(target);`
268 | 402 | `Map distanceMap = getDistanceMap(source, targets);`
269 | 400 | `return (Double)distanceMap.get(target);`
270 |  | `}`
271 |  | ``
272 |  | ``
273 |  | `public Map getDistanceMap(ArchetypeVertex source, Set targets)`
274 |  | `{`
275 | 402 | `if (source.getGraph() != g)`
276 | 2 | `throw new IllegalArgumentException("Specified source vertex " +`
277 |  | `source + " is not part of graph " + g);`
278 |  | ``
279 | 400 | `if (targets.size() > max_targets)`
280 | 0 | `throw new IllegalArgumentException("size of target set exceeds maximum " +`
281 |  | `"number of targets allowed: " + this.max_targets);`
282 |  | ``
283 | 400 | `Map distanceMap = singleSourceShortestPath(source, targets, (int)Math.min(g.numVertices(), max_targets));`
284 |  | ``
285 | 400 | `if (!cached)`
286 | 200 | `reset(source);`
287 |  | ``
288 | 400 | `return distanceMap;`
289 |  | `}`
290 |  | ``
291 |  | `/**`
292 |  | `* <p>Returns a <code>LinkedHashMap</code> which maps each vertex`
293 |  | `* in the graph (including the <code>source</code> vertex)`
294 |  | `* to its distance from the <code>source</code> vertex.`
295 |  | `* The map's iterator will return the elements in order of`
296 |  | `* increasing distance from <code>source</code>.</p>`
297 |  | `*`
298 |  | `* <p>The size of the map returned will be the number of`
299 |  | `* vertices reachable from <code>source</code>.</p>`
300 |  | `*`
301 |  | `* @see #getDistanceMap(ArchetypeVertex,int)`
302 |  | `* @see #getDistance(ArchetypeVertex,ArchetypeVertex)`
303 |  | `* @param source the vertex from which distances are measured`
304 |  | `*/`
305 |  | `public Map getDistanceMap(ArchetypeVertex source)`
306 |  | `{`
307 | 42 | `return getDistanceMap(source, (int)Math.min(g.numVertices(), max_targets));`
308 |  | `}`
309 |  | ``
310 |  | ``
311 |  | ``
312 |  | `/**`
313 |  | `* <p>Returns a <code>LinkedHashMap</code> which maps each of the closest`
314 |  | `* <code>numDist</code> vertices to the <code>source</code> vertex`
315 |  | `* in the graph (including the <code>source</code> vertex)`
316 |  | `* to its distance from the <code>source</code> vertex. Throws`
317 |  | `* an <code>IllegalArgumentException</code> if <code>source</code>`
318 |  | `* is not in this instance's graph, or if <code>numDests</code> is`
319 |  | `* either less than 1 or greater than the number of vertices in the`
320 |  | `* graph.</p>`
321 |  | `*`
322 |  | `* <p>The size of the map returned will be the smaller of`
323 |  | `* <code>numDests</code> and the number of vertices reachable from`
324 |  | `* <code>source</code>.`
325 |  | `*`
326 |  | `* @see #getDistanceMap(ArchetypeVertex)`
327 |  | `* @see #getDistance(ArchetypeVertex,ArchetypeVertex)`
328 |  | `* @param source the vertex from which distances are measured`
329 |  | `* @param numDests the number of vertices for which to measure distances`
330 |  | `*/`
331 |  | `public LinkedHashMap getDistanceMap(ArchetypeVertex source, int numDests)`
332 |  | `{`
333 | 450 | `if (source.getGraph() != g)`
334 | 2 | `throw new IllegalArgumentException("Specified source vertex " +`
335 |  | `source + " is not part of graph " + g);`
336 |  | ``
337 | 448 | `if (numDests < 1 || numDests > g.numVertices())`
338 | 6 | `throw new IllegalArgumentException("numDests must be >= 1 " +`
339 |  | `"and <= g.numVertices()");`
340 |  | ``
341 | 442 | `if (numDests > max_targets)`
342 | 0 | `throw new IllegalArgumentException("numDests must be <= the maximum " +`
343 |  | `"number of targets allowed: " + this.max_targets);`
344 |  | ``
345 | 442 | `LinkedHashMap distanceMap = singleSourceShortestPath(source, null, numDests);`
346 |  | ``
347 | 440 | `if (!cached)`
348 | 220 | `reset(source);`
349 |  | ``
350 | 440 | `return distanceMap;`
351 |  | `}`
352 |  | ``
353 |  | `/**`
354 |  | `* Allows the user to specify the maximum distance that this instance will calculate.`
355 |  | `* Any vertices past this distance will effectively be unreachable from the source, in`
356 |  | `* the sense that the algorithm will not calculate the distance to any vertices which`
357 |  | `* are farther away than this distance. A negative value for <code>max_dist</code>`
358 |  | `* will ensure that no further distances are calculated.`
359 |  | `*`
360 |  | `* <p>This can be useful for limiting the amount of time and space used by this algorithm`
361 |  | `* if the graph is very large.</p>`
362 |  | `*`
363 |  | `* <p>Note: if this instance has already calculated distances greater than <code>max_dist</code>,`
364 |  | `* and the results are cached, those results will still be valid and available; this limit`
365 |  | `* applies only to subsequent distance calculations.</p>`
366 |  | `* @see #setMaxTargets(double)`
367 |  | `*/`
368 |  | `public void setMaxDistance(double max_dist)`
369 |  | `{`
370 | 0 | `this.max_distance = max_dist;`
371 | 0 | `for (Iterator iter = sourceMap.keySet().iterator(); iter.hasNext(); )`
372 |  | `{`
373 | 0 | `SourceData sd = (SourceData)sourceMap.get(iter.next());`
374 | 0 | `sd.reached_max = (this.max_distance <= sd.dist_reached) || (sd.distances.size() >= max_targets);`
375 |  | `}`
376 | 0 | `}`
377 |  | ``
378 |  | `/**`
379 |  | `* Allows the user to specify the maximum number of target vertices per source vertex`
380 |  | `* for which this instance will calculate distances. Once this threshold is reached,`
381 |  | `* any further vertices will effectively be unreachable from the source, in`
382 |  | `* the sense that the algorithm will not calculate the distance to any more vertices.`
383 |  | `* A negative value for <code>max_targets</code> will ensure that no further distances are calculated.`
384 |  | `*`
385 |  | `* <p>This can be useful for limiting the amount of time and space used by this algorithm`
386 |  | `* if the graph is very large.</p>`
387 |  | `*`
388 |  | `* <p>Note: if this instance has already calculated distances to a greater number of`
389 |  | `* targets than <code>max_targets</code>, and the results are cached, those results`
390 |  | `* will still be valid and available; this limit applies only to subsequent distance`
391 |  | `* calculations.</p>`
392 |  | `* @see #setMaxDistance(double)`
393 |  | `*/`
394 |  | `public void setMaxTargets(int max_targets)`
395 |  | `{`
396 | 0 | `this.max_targets = max_targets;`
397 | 0 | `for (Iterator iter = sourceMap.keySet().iterator(); iter.hasNext(); )`
398 |  | `{`
399 | 0 | `SourceData sd = (SourceData)sourceMap.get(iter.next());`
400 | 0 | `sd.reached_max = (this.max_distance <= sd.dist_reached) || (sd.distances.size() >= max_targets);`
401 |  | `}`
402 | 0 | `}`
403 |  | ``
404 |  | `/**`
405 |  | `* Clears all stored distances for this instance.`
406 |  | `* Should be called whenever the graph is modified (edge weights`
407 |  | `* changed or edges added/removed). If the user knows that`
408 |  | `* some currently calculated distances are unaffected by a`
409 |  | `* change, <code>reset(Vertex)</code> may be appropriate instead.`
410 |  | `*`
411 |  | `* @see #reset(Vertex)`
412 |  | `*/`
413 |  | `public void reset()`
414 |  | `{`
415 | 204 | `sourceMap = new HashMap();`
416 | 204 | `}`
417 |  | ``
418 |  | `/**`
419 |  | `* Specifies whether or not this instance of <code>DijkstraShortestPath</code>`
420 |  | `* should cache its results (final and partial) for future reference.`
421 |  | `*`
422 |  | `* @param enable <code>true</code> if the results are to be cached, and`
423 |  | `* <code>false</code> otherwise`
424 |  | `*/`
425 |  | `public void enableCaching(boolean enable)`
426 |  | `{`
427 | 0 | `this.cached = enable;`
428 | 0 | `}`
429 |  | ``
430 |  | `/**`
431 |  | `* Clears all stored distances for the specified source vertex`
432 |  | `* <code>source</code>. Should be called whenever the stored distances`
433 |  | `* from this vertex are invalidated by changes to the graph.`
434 |  | `*`
435 |  | `* @see #reset()`
436 |  | `*/`
437 |  | `public void reset(ArchetypeVertex source)`
438 |  | `{`
439 | 840 | `sourceMap.put(source, null);`
440 | 840 | `}`
441 |  | ``
442 |  | `/**`
443 |  | `* Compares according to distances, so that the BinaryHeap knows how to`
444 |  | `* order the tree.`
445 |  | `*/`
446 |  | `protected class VertexComparator implements Comparator`
447 |  | `{`
448 |  | `private Map distances;`
449 |  | ``
450 |  | `public VertexComparator(Map distances)`
451 |  | `{`
452 |  | `this.distances = distances;`
453 |  | `}`
454 |  | ``
455 |  | `public int compare(Object o1, Object o2)`
456 |  | `{`
457 |  | `return ((Comparable)distances.get(o1)).compareTo(distances.get(o2));`
458 |  | `}`
459 |  | `}`
460 |  | ``
461 |  | `/**`
462 |  | `* For a given source vertex, holds the estimated and final distances,`
463 |  | `* tentative and final assignments of incoming edges on the shortest path from`
464 |  | `* the source vertex, and a priority queue (ordered by estimaed distance)`
465 |  | `* of the vertices for which distances are unknown.`
466 |  | `*`
467 |  | `* @author Joshua O'Madadhain`
468 |  | `*/`
469 |  | `protected class SourceData`
470 |  | `{`
471 |  | `public LinkedHashMap distances;`
472 |  | `public Map estimatedDistances;`
473 |  | `public MapBinaryHeap unknownVertices;`
474 |  | `public boolean reached_max = false;`
475 |  | `public double dist_reached = 0;`
476 |  | ``
477 |  | `public SourceData(ArchetypeVertex source)`
478 |  | `{`
479 |  | `distances = new LinkedHashMap();`
480 |  | `estimatedDistances = new HashMap();`
481 |  | `unknownVertices = new MapBinaryHeap(new VertexComparator(estimatedDistances));`
482 |  | ``
483 |  | `sourceMap.put(source, this);`
484 |  | ``
485 |  | `// initialize priority queue`
486 |  | `estimatedDistances.put(source, new Double(0)); // distance from source to itself is 0`
487 |  | `unknownVertices.add(source);`
488 |  | `reached_max = false;`
489 |  | `dist_reached = 0;`
490 |  | `}`
491 |  | ``
492 |  | `public Pair getNextVertex()`
493 |  | `{`
494 |  | `ArchetypeVertex v = (ArchetypeVertex)unknownVertices.pop();`
495 |  | `Double dist = (Double)estimatedDistances.remove(v);`
496 |  | `distances.put(v, dist);`
497 |  | `return new Pair(v, dist);`
498 |  | `}`
499 |  | ``
500 |  | `public void update(ArchetypeVertex dest, ArchetypeEdge tentative_edge, double new_dist)`
501 |  | `{`
502 |  | `estimatedDistances.put(dest, new Double(new_dist));`
503 |  | `unknownVertices.update(dest);`
504 |  | `}`
505 |  | ``
506 |  | `public void createRecord(ArchetypeVertex w, ArchetypeEdge e, double new_dist)`
507 |  | `{`
508 |  | `estimatedDistances.put(w, new Double(new_dist));`
509 |  | `unknownVertices.add(w);`
510 |  | `}`
511 |  | `}`
512 |  | `}`

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.