| 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.Iterator; | |
| 14 | import java.util.Map; | |
| 15 | ||
| 16 | import edu.uci.ics.jung.algorithms.connectivity.BFSDistanceLabeler; | |
| 17 | import edu.uci.ics.jung.graph.ArchetypeVertex; | |
| 18 | import edu.uci.ics.jung.graph.Edge; | |
| 19 | import edu.uci.ics.jung.graph.Graph; | |
| 20 | import edu.uci.ics.jung.graph.Vertex; | |
| 21 | import edu.uci.ics.jung.utils.UserDataUtils; | |
| 22 | ||
| 23 | /** | |
| 24 | * Computes the shortest path distances for graphs whose edges are not weighted (using BFS). | |
| 25 | * | |
| 26 | * @author Scott White | |
| 27 | */ | |
| 28 | public class UnweightedShortestPath implements ShortestPath, Distance | |
| 29 | { | |
| 30 | private Map mDistanceMap; | |
| 31 | private Map mIncomingEdgeMap; | |
| 32 | private Graph mGraph; | |
| 33 | ||
| 34 | /** | |
| 35 | * Constructs and initializes algorithm | |
| 36 | * @param g the graph | |
| 37 | */ | |
| 38 | public UnweightedShortestPath(Graph g) | |
| 39 | 5 | { |
| 40 | 5 | mDistanceMap = new HashMap(g.numVertices() * 2); |
| 41 | 5 | mIncomingEdgeMap = new HashMap(g.numVertices() * 2); |
| 42 | 5 | mGraph = g; |
| 43 | 5 | } |
| 44 | ||
| 45 | /** | |
| 46 | * @see edu.uci.ics.jung.algorithms.shortestpath.Distance#getDistance(edu.uci.ics.jung.graph.ArchetypeVertex, edu.uci.ics.jung.graph.ArchetypeVertex) | |
| 47 | */ | |
| 48 | public Number getDistance(ArchetypeVertex source, ArchetypeVertex target) | |
| 49 | { | |
| 50 | 72 | Map sourceSPMap = getDistanceMap(source); |
| 51 | 72 | return (Number) sourceSPMap.get(target); |
| 52 | } | |
| 53 | ||
| 54 | /** | |
| 55 | * @see edu.uci.ics.jung.algorithms.shortestpath.Distance#getDistanceMap(edu.uci.ics.jung.graph.ArchetypeVertex) | |
| 56 | */ | |
| 57 | public Map getDistanceMap(ArchetypeVertex source) | |
| 58 | { | |
| 59 | 74 | Map sourceSPMap = (Map) mDistanceMap.get(source); |
| 60 | 74 | if (sourceSPMap == null) |
| 61 | { | |
| 62 | 20 | computeShortestPathsFromSource(source); |
| 63 | 20 | sourceSPMap = (Map) mDistanceMap.get(source); |
| 64 | } | |
| 65 | 74 | return sourceSPMap; |
| 66 | } | |
| 67 | ||
| 68 | /** | |
| 69 | * @see edu.uci.ics.jung.algorithms.shortestpath.ShortestPath#getIncomingEdgeMap(edu.uci.ics.jung.graph.Vertex) | |
| 70 | */ | |
| 71 | public Map getIncomingEdgeMap(Vertex source) | |
| 72 | { | |
| 73 | 4 | Map sourceIEMap = (Map) mIncomingEdgeMap.get(source); |
| 74 | 4 | if (sourceIEMap == null) |
| 75 | { | |
| 76 | 0 | computeShortestPathsFromSource(source); |
| 77 | 0 | sourceIEMap = (Map) mIncomingEdgeMap.get(source); |
| 78 | } | |
| 79 | 4 | return sourceIEMap; |
| 80 | } | |
| 81 | ||
| 82 | /** | |
| 83 | * Computes the shortest path distance from the source to target. If the shortest path distance has not already | |
| 84 | * been computed, then all pairs shortest paths will be computed. | |
| 85 | * @param source the source node | |
| 86 | * @param target the target node | |
| 87 | * @return the shortest path value (if the target is unreachable, NPE is thrown) | |
| 88 | * @deprecated use getDistance | |
| 89 | */ | |
| 90 | public int getShortestPath(Vertex source, Vertex target) | |
| 91 | { | |
| 92 | 0 | return getDistance(source, target).intValue(); |
| 93 | } | |
| 94 | ||
| 95 | /** | |
| 96 | * Computes the shortest path distances from a given node to all other nodes. | |
| 97 | * @param graph the graph | |
| 98 | * @param source the source node | |
| 99 | * @return A <code>Map</code> whose keys are target vertices and whose values are <code>Integers</code> representing the shortest path distance | |
| 100 | */ | |
| 101 | private void computeShortestPathsFromSource(ArchetypeVertex source) | |
| 102 | { | |
| 103 | 20 | String DISTANCE_KEY = "UnweightedShortestPath.DISTANCE"; |
| 104 | 20 | BFSDistanceLabeler labeler = new BFSDistanceLabeler(DISTANCE_KEY); |
| 105 | 20 | labeler.labelDistances(mGraph, (Vertex)source); |
| 106 | 20 | Map currentSourceSPMap = new HashMap(); |
| 107 | 20 | Map currentSourceEdgeMap = new HashMap(); |
| 108 | ||
| 109 | 20 | for (Iterator vIt = mGraph.getVertices().iterator(); vIt.hasNext();) |
| 110 | { | |
| 111 | 118 | Vertex vertex = (Vertex) vIt.next(); |
| 112 | 118 | Number distanceVal = (Number) vertex.getUserDatum(DISTANCE_KEY); |
| 113 | // BFSDistanceLabeler uses -1 to indicate unreachable vertices; | |
| 114 | // don't bother to store unreachable vertices | |
| 115 | 118 | if (distanceVal != null && distanceVal.intValue() >= 0) |
| 116 | { | |
| 117 | 98 | currentSourceSPMap.put(vertex, distanceVal); |
| 118 | 98 | int minDistance = distanceVal.intValue(); |
| 119 | 98 | for (Iterator eIt = vertex.getInEdges().iterator(); eIt.hasNext();) |
| 120 | { | |
| 121 | 234 | Edge incomingEdge = (Edge) eIt.next(); |
| 122 | 234 | Vertex neighbor = incomingEdge.getOpposite(vertex); |
| 123 | 234 | Number predDistanceVal = |
| 124 | (Number) neighbor.getUserDatum(DISTANCE_KEY); | |
| 125 | 234 | int pred_distance = predDistanceVal.intValue(); |
| 126 | // if (predDistanceVal.intValue() < minDistance) | |
| 127 | 234 | if (pred_distance < minDistance && pred_distance >= 0) |
| 128 | { | |
| 129 | 78 | minDistance = predDistanceVal.intValue(); |
| 130 | 78 | currentSourceEdgeMap.put(vertex, incomingEdge); |
| 131 | } | |
| 132 | } | |
| 133 | } | |
| 134 | } | |
| 135 | ||
| 136 | 20 | UserDataUtils.cleanup(mGraph.getVertices(), DISTANCE_KEY); |
| 137 | ||
| 138 | 20 | mDistanceMap.put(source, currentSourceSPMap); |
| 139 | 20 | mIncomingEdgeMap.put(source, currentSourceEdgeMap); |
| 140 | 20 | } |
| 141 | ||
| 142 | /** | |
| 143 | * Clears all stored distances for this instance. | |
| 144 | * Should be called whenever the graph is modified (edge weights | |
| 145 | * changed or edges added/removed). If the user knows that | |
| 146 | * some currently calculated distances are unaffected by a | |
| 147 | * change, <code>reset(Vertex)</code> may be appropriate instead. | |
| 148 | * | |
| 149 | * @see #reset(Vertex) | |
| 150 | */ | |
| 151 | public void reset() | |
| 152 | { | |
| 153 | 0 | mDistanceMap = new HashMap(mGraph.numVertices() * 2); |
| 154 | 0 | mIncomingEdgeMap = new HashMap(mGraph.numVertices() * 2); |
| 155 | 0 | } |
| 156 | ||
| 157 | /** | |
| 158 | * Clears all stored distances for the specified source vertex | |
| 159 | * <code>source</code>. Should be called whenever the stored distances | |
| 160 | * from this vertex are invalidated by changes to the graph. | |
| 161 | * | |
| 162 | * @see #reset() | |
| 163 | */ | |
| 164 | public void reset(Vertex v) | |
| 165 | { | |
| 166 | 0 | mDistanceMap.put(v, null); |
| 167 | 0 | mIncomingEdgeMap.put(v, null); |
| 168 | 0 | } |
| 169 | } |
|
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |