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

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