| 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. |