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