| 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. |
copyright © 2003, jcoverage ltd. all rights reserved. |