# Coverage details for edu.uci.ics.jung.algorithms.connectivity.BFSDistanceLabeler

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.connectivity;`
11 |  | ``
12 |  | `import edu.uci.ics.jung.graph.Vertex;`
13 |  | `import edu.uci.ics.jung.graph.Graph;`
14 |  | `import edu.uci.ics.jung.graph.decorators.NumericDecorator;`
15 |  | `import edu.uci.ics.jung.utils.UserData;`
16 |  | ``
17 |  | `import java.util.*;`
18 |  | ``
19 |  | `/**`
20 |  | `* Labels each node in the graph according to the BFS distance from the start node(s). If nodes are unreachable, then`
21 |  | `* they are assigned a distance of -1.`
22 |  | `* All nodes traversed at step k are marked as predecessors of their successors traversed at step k+1.`
23 |  | `* <p>`
24 |  | `* Running time is: O(m)`
25 |  | `* @author Scott White`
26 |  | `*/`
27 |  | `public class BFSDistanceLabeler {`
28 |  | `public static final String DEFAULT_DISTANCE_KEY = "algorithms.connectivity.BFSDiststanceLabeler.DISTANCE_KEY";`
29 |  | `private NumericDecorator mDistanceDecorator;`
30 |  | `private List mCurrentList;`
31 |  | `private Set mUnvisitedVertices;`
32 |  | `private List mVerticesInOrderVisited;`
33 |  | `private Map mPredecessorMap;`
34 |  | ``
35 |  | ``
36 |  | `/**`
37 |  | `* Creates a new BFS labeler for the specified graph and root set.`
38 |  | `* @param distanceKey the UserDatum key the algorithm should use to store/decorate the distances from the root set`
39 |  | `* The distances are stored in the corresponding Vertex objects and are of type MutableInteger`
40 |  | `*/`
41 | 23 | `public BFSDistanceLabeler(String distanceKey) {`
42 | 23 | `mDistanceDecorator = new NumericDecorator(distanceKey,UserData.SHARED);`
43 | 23 | `mPredecessorMap = new HashMap();`
44 | 23 | `}`
45 |  | ``
46 |  | `/**`
47 |  | `* Creates a new BFS labeler for the specified graph and root set`
48 |  | `* The distances are stored in the corresponding Vertex objects and are of type MutableInteger`
49 |  | `*/`
50 | 0 | `public BFSDistanceLabeler() {`
51 | 0 | `mDistanceDecorator = new NumericDecorator(DEFAULT_DISTANCE_KEY,UserData.SHARED);`
52 | 0 | `mPredecessorMap = new HashMap();`
53 | 0 | `}`
54 |  | ``
55 |  | `/**`
56 |  | `* Returns the list of vertices visited in order of traversal`
57 |  | `* @return the list of vertices`
58 |  | `*/`
59 |  | `public List getVerticesInOrderVisited() {`
60 | 2 | `return mVerticesInOrderVisited;`
61 |  | `}`
62 |  | ``
63 |  | `/**`
64 |  | `* Returns the set of all vertices that were not visited`
65 |  | `* @return the list of unvisited vertices`
66 |  | `*/`
67 |  | `public Set getUnivistedVertices() {`
68 | 2 | `return mUnvisitedVertices;`
69 |  | `}`
70 |  | ``
71 |  | `/**`
72 |  | `* Given a vertex, returns the shortest distance from any node in the root set to v`
73 |  | `* @param v the vertex whose distance is to be retrieved`
74 |  | `* @return the shortest distance from any node in the root set to v`
75 |  | `*/`
76 |  | `public int getDistance(Graph g, Vertex v) {`
77 | 6 | `if (!g.getVertices().contains(v)) {`
78 | 0 | `throw new IllegalArgumentException("Vertex is not contained in the graph.");`
79 |  | `}`
80 |  | ``
81 | 6 | `return mDistanceDecorator.getValue(v).intValue();`
82 |  | `}`
83 |  | ``
84 |  | `/**`
85 |  | `* Returns set of predecessors of the given vertex`
86 |  | `* @param v the vertex whose predecessors are to be retrieved`
87 |  | `* @return the set of predecessors`
88 |  | `*/`
89 |  | `public Set getPredecessors(Vertex v) {`
90 | 6 | `return (Set) mPredecessorMap.get(v);`
91 |  | `}`
92 |  | ``
93 |  | `protected void initialize(Graph g, Set rootSet) {`
94 | 23 | `mVerticesInOrderVisited = new ArrayList();`
95 | 23 | `mUnvisitedVertices = new HashSet();`
96 | 23 | `for (Iterator vIt=g.getVertices().iterator(); vIt.hasNext();) {`
97 | 138 | `Vertex currentVertex = (Vertex) vIt.next();`
98 | 138 | `mUnvisitedVertices.add(currentVertex);`
99 | 138 | `mPredecessorMap.put(currentVertex,new HashSet());`
100 |  | `}`
101 |  | ``
102 | 23 | `mCurrentList = new ArrayList();`
103 | 23 | `for (Iterator rootIt = rootSet.iterator(); rootIt.hasNext();) {`
104 | 24 | `Vertex v = (Vertex) rootIt.next();`
105 | 24 | `mDistanceDecorator.setValue(new Integer(0),v);`
106 | 24 | `mCurrentList.add(v);`
107 | 24 | `mUnvisitedVertices.remove(v);`
108 | 24 | `mVerticesInOrderVisited.add(v);`
109 |  | `}`
110 | 23 | `}`
111 |  | ``
112 |  | `private void addPredecessor(Vertex predecessor,Vertex sucessor) {`
113 | 98 | `HashSet predecessors = (HashSet) mPredecessorMap.get(sucessor);`
114 | 98 | `predecessors.add(predecessor);`
115 | 98 | `}`
116 |  | ``
117 |  | `public void removeDecorations(Graph g) {`
118 | 2 | `for (Iterator vIt=g.getVertices().iterator();vIt.hasNext();) {`
119 | 14 | `Vertex v = (Vertex) vIt.next();`
120 | 14 | `mDistanceDecorator.removeValue(v);`
121 |  | `}`
122 | 2 | `}`
123 |  | ``
124 |  | `/**`
125 |  | `* Computes the distances of all the node from the starting root nodes. If there is more than one root node`
126 |  | `* the minimum distance from each root node is used as the designated distance to a given node. Also keeps track`
127 |  | `* of the predecessors of each node traversed as well as the order of nodes traversed.`
128 |  | `* @param graph the graph to label`
129 |  | `* @param rootSet the set of starting vertices to traverse from`
130 |  | `*/`
131 |  | `public void labelDistances(Graph graph, Set rootSet) {`
132 |  | ``
133 | 23 | `initialize(graph,rootSet);`
134 |  | ``
135 | 23 | `int distance = 1;`
136 |  | `while (true) {`
137 | 62 | `List newList = new ArrayList();`
138 |  | ``
139 | 62 | `for (Iterator vIt = mCurrentList.iterator(); vIt.hasNext();) {`
140 | 112 | `Vertex currentVertex = (Vertex) vIt.next();`
141 | 112 | `for (Iterator uIt = currentVertex.getSuccessors().iterator(); uIt.hasNext();) {`
142 | 250 | `visitNewVertex(currentVertex,(Vertex) uIt.next(), distance, newList);`
143 |  | `}`
144 |  | `}`
145 | 62 | `if (newList.size() == 0) break;`
146 | 39 | `mCurrentList = newList;`
147 | 39 | `distance++;`
148 |  | `}`
149 |  | ``
150 | 23 | `for (Iterator vIt = mUnvisitedVertices.iterator(); vIt.hasNext();) {`
151 | 26 | `Vertex v = (Vertex) vIt.next();`
152 | 26 | `mDistanceDecorator.setValue(new Integer(-1),v);`
153 |  | ``
154 |  | `}`
155 | 23 | `}`
156 |  | ``
157 |  | `/**`
158 |  | `* Computes the distances of all the node from the specified root node. Also keeps track`
159 |  | `* of the predecessors of each node traveresed as well as the order of nodes traversed.`
160 |  | `* @param graph the graph to label`
161 |  | `* @param root the single starting vertex to traverse from`
162 |  | `*/`
163 |  | `public void labelDistances(Graph graph, Vertex root) {`
164 | 21 | `Set rootSet = new HashSet();`
165 | 21 | `rootSet.add(root);`
166 | 21 | `labelDistances(graph,rootSet);`
167 |  | ``
168 | 21 | `}`
169 |  | ``
170 |  | `private void visitNewVertex(Vertex predecessor,Vertex neighbor, int distance, List newList) {`
171 | 250 | `if (mUnvisitedVertices.contains(neighbor)) {`
172 | 88 | `mDistanceDecorator.setValue(new Integer(distance),neighbor);`
173 | 88 | `newList.add(neighbor);`
174 | 88 | `mVerticesInOrderVisited.add(neighbor);`
175 | 88 | `mUnvisitedVertices.remove(neighbor);`
176 |  | `}`
177 | 250 | `int predecessorDistance = mDistanceDecorator.getValue(predecessor).intValue();`
178 | 250 | `int successorDistance = mDistanceDecorator.getValue(neighbor).intValue();`
179 | 250 | `if (predecessorDistance < successorDistance) {`
180 | 98 | `addPredecessor(predecessor,neighbor);`
181 |  | `}`
182 | 250 | `}`
183 |  | `}`

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.