# Coverage details for edu.uci.ics.jung.algorithms.importance.AbstractRanker

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.importance;`
11 |  | ``
12 |  | `import java.util.ArrayList;`
13 |  | `import java.util.Collections;`
14 |  | `import java.util.Iterator;`
15 |  | `import java.util.List;`
16 |  | `import java.util.Set;`
17 |  | ``
18 |  | `import cern.colt.list.DoubleArrayList;`
19 |  | `import corejava.Format;`
20 |  | `import edu.uci.ics.jung.algorithms.IterativeProcess;`
21 |  | `import edu.uci.ics.jung.exceptions.FatalException;`
22 |  | `import edu.uci.ics.jung.graph.Edge;`
23 |  | `import edu.uci.ics.jung.graph.Element;`
24 |  | `import edu.uci.ics.jung.graph.Graph;`
25 |  | `import edu.uci.ics.jung.graph.Vertex;`
26 |  | `import edu.uci.ics.jung.graph.decorators.StringLabeller;`
27 |  | `import edu.uci.ics.jung.utils.MutableDouble;`
28 |  | `import edu.uci.ics.jung.utils.UserData;`
29 |  | ``
30 |  | `/**`
31 |  | `* Abstract class for algorithms that rank nodes or edges by some "importance" metric. Provides a common set of`
32 |  | `* services such as:`
33 |  | `* <ul>`
34 |  | `* <li> storing rank scores</li>`
35 |  | `* <li> getters and setters for rank scores</li>`
36 |  | `* <li> computing default edge weights</li>`
37 |  | `* <li> normalizing default or user-provided edge transition weights </li>`
38 |  | `* <li> normalizing rank scores</li>`
39 |  | `* <li> automatic cleanup of decorations</li>`
40 |  | `* <li> creation of Ranking list</li>`
41 |  | `* <li>print rankings in sorted order by rank</li>`
42 |  | `* </ul>`
43 |  | `* <p>`
44 |  | `* By default, all rank scores are removed from the vertices (or edges) being ranked.`
45 |  | `* @author Scott White`
46 |  | `*/`
47 | 24 | `public abstract class AbstractRanker extends IterativeProcess {`
48 |  | `private Graph mGraph;`
49 |  | `private List mRankings;`
50 |  | `public static final String DEFAULT_EDGE_WEIGHT_KEY = "jung.algorithms.importance.AbstractRanker.EdgeWeight";`
51 |  | `private String mUserDefinedEdgeWeightKey;`
52 |  | `private boolean mRemoveRankScoresOnFinalize;`
53 |  | `private boolean mRankNodes;`
54 |  | `private boolean mRankEdges;`
55 |  | `private boolean mNormalizeRankings;`
56 |  | ``
57 |  | `protected void initialize(Graph graph, boolean isNodeRanker,`
58 |  | `boolean isEdgeRanker)`
59 |  | `{`
60 | 24 | `if (!isNodeRanker && !isEdgeRanker)`
61 | 0 | `throw new IllegalArgumentException("Must rank edges, vertices, or both");`
62 | 24 | `mGraph = graph;`
63 | 24 | `mRemoveRankScoresOnFinalize = true;`
64 | 24 | `mNormalizeRankings = true;`
65 | 24 | `mUserDefinedEdgeWeightKey = null;`
66 | 24 | `mRankNodes = isNodeRanker;`
67 | 24 | `mRankEdges = isEdgeRanker;`
68 | 24 | `}`
69 |  | ``
70 |  | `protected Set getVertices() {`
71 | 553 | `return mGraph.getVertices();`
72 |  | `}`
73 |  | ``
74 |  | `protected Graph getGraph() {`
75 | 21 | `return mGraph;`
76 |  | `}`
77 |  | ``
78 |  | `protected void reinitialize() {`
79 | 0 | `}`
80 |  | ``
81 |  | `/**`
82 |  | `* Returns <code>true</code> if this ranker ranks nodes, and`
83 |  | `* <code>false</code> otherwise.`
84 |  | `*/`
85 |  | `public boolean isRankingNodes() {`
86 | 0 | `return mRankNodes;`
87 |  | `}`
88 |  | ``
89 |  | `/**`
90 |  | `* Returns <code>true</code> if this ranker ranks edges, and`
91 |  | `* <code>false</code> otherwise.`
92 |  | `*/`
93 |  | `public boolean isRankingEdges()`
94 |  | `{`
95 | 0 | `return mRankEdges;`
96 |  | `}`
97 |  | ``
98 |  | `/**`
99 |  | `* Instructs the ranker whether or not it should remove the rank scores from the nodes (or edges) once the ranks`
100 |  | `* have been computed.`
101 |  | `* @param removeRankScoresOnFinalize <code>true</code> if the rank scores are to be removed, <code>false</code> otherwise`
102 |  | `*/`
103 |  | `public void setRemoveRankScoresOnFinalize(boolean removeRankScoresOnFinalize) {`
104 | 15 | `this.mRemoveRankScoresOnFinalize = removeRankScoresOnFinalize;`
105 | 15 | `}`
106 |  | ``
107 | 20162 | `protected void onFinalize(Element e) {}`
108 |  | ``
109 |  | `protected void finalizeIterations() {`
110 | 24 | `ArrayList sortedRankings = new ArrayList();`
111 |  | ``
112 | 24 | `int id = 1;`
113 | 24 | `if (mRankNodes)`
114 |  | `{`
115 | 21 | `for (Iterator it = getVertices().iterator(); it.hasNext();) {`
116 | 20110 | `Vertex currentVertex = (Vertex) it.next();`
117 | 20110 | `NodeRanking ranking = new NodeRanking(id,getRankScore(currentVertex),currentVertex);`
118 | 20110 | `sortedRankings.add(ranking);`
119 | 20110 | `if (mRemoveRankScoresOnFinalize) {`
120 | 20031 | `currentVertex.removeUserDatum(getRankScoreKey());`
121 |  | `}`
122 | 20110 | `id++;`
123 | 20110 | `onFinalize(currentVertex);`
124 |  | `}`
125 |  | `}`
126 | 24 | `if (mRankEdges)`
127 |  | `{`
128 | 7 | `for (Iterator it = mGraph.getEdges().iterator(); it.hasNext();) {`
129 | 60 | `Edge currentEdge = (Edge) it.next();`
130 | 60 | `EdgeRanking ranking = new EdgeRanking(id,getRankScore(currentEdge),currentEdge);`
131 | 60 | `sortedRankings.add(ranking);`
132 | 60 | `if (mRemoveRankScoresOnFinalize) {`
133 | 33 | `currentEdge.removeUserDatum(getRankScoreKey());`
134 |  | `}`
135 | 60 | `id++;`
136 | 60 | `onFinalize(currentEdge);`
137 |  | `}`
138 |  | `}`
139 |  | ``
140 | 24 | `mRankings = sortedRankings;`
141 | 24 | `Collections.sort(mRankings);`
142 | 24 | `}`
143 |  | ``
144 |  | `/**`
145 |  | `* Retrieves the list of ranking instances in descending sorted order by rank score`
146 |  | `* If the algorithm is ranking edges, the instances will be of type <code>EdgeRanking</code>, otherwise`
147 |  | `* if the algorithm is ranking nodes the instances will be of type <code>NodeRanking</code>`
148 |  | `* @return the list of rankings`
149 |  | `*/`
150 |  | `public List getRankings() {`
151 | 28 | `return mRankings;`
152 |  | `}`
153 |  | ``
154 |  | `/**`
155 |  | `* Return a list of the top k rank scores.`
156 |  | `* @param topKRankings the value of k to use`
157 |  | `* @return list of rank scores`
158 |  | `*/`
159 |  | `public DoubleArrayList getRankScores(int topKRankings) {`
160 | 0 | `DoubleArrayList scores = new DoubleArrayList();`
161 | 0 | `int count=1;`
162 | 0 | `for (Iterator rIt=getRankings().iterator(); rIt.hasNext();) {`
163 | 0 | `if (count > topKRankings) {`
164 | 0 | `return scores;`
165 |  | `}`
166 | 0 | `NodeRanking currentRanking = (NodeRanking) rIt.next();`
167 | 0 | `scores.add(currentRanking.rankScore);`
168 | 0 | `count++;`
169 |  | `}`
170 |  | ``
171 | 0 | `return scores;`
172 |  | `}`
173 |  | ``
174 |  | `/**`
175 |  | `* The user datum key used to store the rank score.`
176 |  | `* @return the key`
177 |  | `*/`
178 |  | `abstract public String getRankScoreKey();`
179 |  | ``
180 |  | `/**`
181 |  | `* Given an edge or node, returns the corresponding rank score. This is a default`
182 |  | `* implementation of getRankScore which assumes the decorations are of type MutableDouble.`
183 |  | `* This method only returns legal values if <code>setRemoveRankScoresOnFinalize(false)</code> was called`
184 |  | `* prior to <code>evaluate()</code>.`
185 |  | `* @return the rank score value`
186 |  | `*/`
187 |  | `public double getRankScore(Element e) {`
188 | 61436 | `MutableDouble rankScore = (MutableDouble) e.getUserDatum(getRankScoreKey());`
189 | 61436 | `if (rankScore != null) {`
190 | 61436 | `return rankScore.doubleValue();`
191 |  | `} else {`
192 | 0 | `throw new FatalException("setRemoveRankScoresOnFinalize(false) must be called before evaluate().");`
193 |  | `}`
194 |  | ``
195 |  | `}`
196 |  | ``
197 |  | `protected void setRankScore(Element e, double rankValue) {`
198 | 40683 | `MutableDouble value = (MutableDouble) e.getUserDatum(getRankScoreKey());`
199 |  | ``
200 | 40683 | `if (value == null) {`
201 | 20051 | `e.setUserDatum(getRankScoreKey(),new MutableDouble(rankValue),UserData.SHARED);`
202 |  | `} else {`
203 | 20632 | `value.setDoubleValue(rankValue);`
204 |  | `}`
205 |  | ``
206 | 40683 | `}`
207 |  | ``
208 |  | `protected double getEdgeWeight(Edge e) {`
209 | 1075 | `String edgeWeightKey = getEdgeWeightKeyName();`
210 | 1075 | `return ((Number) e.getUserDatum(edgeWeightKey)).doubleValue();`
211 |  | `}`
212 |  | ``
213 |  | `/**`
214 |  | `* the user datum key used to store the edge weight, if any`
215 |  | `* @return the key`
216 |  | `*/`
217 |  | `public String getEdgeWeightKeyName() {`
218 | 1151 | `if (mUserDefinedEdgeWeightKey == null) {`
219 | 586 | `return DEFAULT_EDGE_WEIGHT_KEY;`
220 |  | `} else {`
221 | 565 | `return mUserDefinedEdgeWeightKey;`
222 |  | `}`
223 |  | `}`
224 |  | ``
225 |  | `protected void setEdgeWeight(Edge e, double weight) {`
226 | 55 | `String edgeWeightKey = getEdgeWeightKeyName();`
227 |  | ``
228 |  | `// MutableDouble value = (MutableDouble) e.getUserDatum(edgeWeightKey);`
229 |  | `// if (value == null) {`
230 |  | `// e.setUserDatum(edgeWeightKey,new MutableDouble(weight),UserData.SHARED);`
231 |  | `// } else {`
232 |  | `// value.setDoubleValue(weight);`
233 |  | `// }`
234 | 55 | `e.setUserDatum(edgeWeightKey,new Double(weight),UserData.SHARED);`
235 | 55 | `}`
236 |  | ``
237 |  | `protected void assignDefaultEdgeTransitionWeights() {`
238 |  | ``
239 | 5 | `for (Iterator vIt = getVertices().iterator(); vIt.hasNext();) {`
240 | 26 | `Vertex currentVertex = (Vertex) vIt.next();`
241 |  | ``
242 |  | `// Set outgoingEdges = null;`
243 |  | `// if (getGraph().isDirected()) {`
244 |  | `// outgoingEdges = currentVertex.getOutEdges();`
245 |  | `// } else {`
246 |  | `// outgoingEdges = currentVertex.getIncidentEdges();`
247 |  | `// }`
248 |  | `// getOutEdges() returns the right thing regardless, so just use this.`
249 | 26 | `Set outgoingEdges = currentVertex.getOutEdges();`
250 |  | ``
251 | 26 | `double numOutEdges = outgoingEdges.size();`
252 | 26 | `for (Iterator edgeIt = outgoingEdges.iterator(); edgeIt.hasNext();) {`
253 | 34 | `Edge currentEdge = (Edge) edgeIt.next();`
254 | 34 | `setEdgeWeight(currentEdge,1.0/numOutEdges);`
255 |  | `}`
256 |  | `}`
257 |  | ``
258 | 5 | `}`
259 |  | ``
260 |  | ``
261 |  | `protected void normalizeEdgeTransitionWeights() {`
262 |  | ``
263 | 4 | `for (Iterator vIt = getVertices().iterator(); vIt.hasNext();) {`
264 | 15 | `Vertex currentVertex = (Vertex) vIt.next();`
265 |  | ``
266 |  | `// Set outgoingEdges = null;`
267 |  | `// if (getGraph().isDirected()) {`
268 |  | `// outgoingEdges = currentVertex.getOutEdges();`
269 |  | `// } else {`
270 |  | `// outgoingEdges = currentVertex.getIncidentEdges();`
271 |  | `// }`
272 | 15 | `Set outgoingEdges = currentVertex.getOutEdges();`
273 |  | ``
274 | 15 | `double totalEdgeWeight = 0;`
275 | 15 | `for (Iterator edgeIt = outgoingEdges.iterator(); edgeIt.hasNext();) {`
276 | 21 | `Edge currentEdge = (Edge) edgeIt.next();`
277 | 21 | `totalEdgeWeight += getEdgeWeight(currentEdge);`
278 |  | `}`
279 |  | ``
280 |  | `//double numOutEdges = outgoingEdges.size();`
281 | 15 | `for (Iterator edgeIt = outgoingEdges.iterator(); edgeIt.hasNext();) {`
282 | 21 | `Edge currentEdge = (Edge) edgeIt.next();`
283 | 21 | `setEdgeWeight(currentEdge,getEdgeWeight(currentEdge)/totalEdgeWeight);`
284 |  | `}`
285 |  | `}`
286 | 4 | `}`
287 |  | ``
288 |  | `protected void normalizeRankings() {`
289 | 7 | `if (!mNormalizeRankings) {`
290 | 0 | `return;`
291 |  | `}`
292 | 7 | `double totalWeight = 0;`
293 | 7 | `Vertex currentVertex = null;`
294 |  | ``
295 | 7 | `for (Iterator it = getVertices().iterator(); it.hasNext();) {`
296 | 20023 | `currentVertex = (Vertex) it.next();`
297 | 20023 | `totalWeight += getRankScore(currentVertex);`
298 |  | `}`
299 |  | ``
300 | 7 | `for (Iterator it = getVertices().iterator(); it.hasNext();) {`
301 | 20023 | `currentVertex = (Vertex) it.next();`
302 | 20023 | `setRankScore(currentVertex,getRankScore(currentVertex)/totalWeight);`
303 |  | `}`
304 | 7 | `}`
305 |  | ``
306 |  | `/**`
307 |  | `* Print the rankings to standard out in descending order of rank score`
308 |  | `* @param verbose if <code>true</code>, include information about the actual rank order as well as`
309 |  | `* the original position of the vertex before it was ranked`
310 |  | `* @param printScore if <code>true</code>, include the actual value of the rank score`
311 |  | `*/`
312 |  | `public void printRankings(boolean verbose,boolean printScore) {`
313 | 0 | `double total = 0;`
314 | 0 | `Format formatter = new Format("%7.6f");`
315 | 0 | `int rank = 1;`
316 | 0 | `boolean hasLabels = StringLabeller.hasStringLabeller(getGraph());`
317 | 0 | `StringLabeller labeller = StringLabeller.getLabeller(getGraph());`
318 | 0 | `for (Iterator it = getRankings().iterator(); it.hasNext();) {`
319 | 0 | `Ranking currentRanking = (Ranking) it.next();`
320 | 0 | `double rankScore = currentRanking.rankScore;`
321 | 0 | `if (verbose) {`
322 | 0 | `System.out.print("Rank " + rank + ": ");`
323 | 0 | `if (printScore) {`
324 | 0 | `System.out.print(formatter.format(rankScore));`
325 |  | `}`
326 | 0 | `System.out.print("\tVertex Id: " + currentRanking.originalPos);`
327 | 0 | `if (hasLabels && currentRanking instanceof NodeRanking) {`
328 | 0 | `Vertex v = ((NodeRanking) currentRanking).vertex;`
329 | 0 | `System.out.print(" (" + labeller.getLabel(v) + ")");`
330 |  | `}`
331 | 0 | `System.out.println();`
332 |  | `} else {`
333 | 0 | `System.out.print(rank + "\t");`
334 | 0 | `if (printScore) {`
335 | 0 | `System.out.print(formatter.format(rankScore));`
336 |  | `}`
337 | 0 | `System.out.println("\t" + currentRanking.originalPos);`
338 |  | ``
339 |  | `}`
340 | 0 | `total += rankScore;`
341 | 0 | `rank++;`
342 |  | `}`
343 |  | ``
344 | 0 | `if (verbose) {`
345 | 0 | `System.out.println("Total: " + formatter.format(total));`
346 |  | `}`
347 | 0 | `}`
348 |  | ``
349 |  | `/**`
350 |  | `* Allows the user to specify whether or not s/he wants the rankings to be normalized.`
351 |  | `* In some cases, this will have no effect since the algorithm doesn't allow normalization`
352 |  | `* as an option`
353 |  | `* @param normalizeRankings`
354 |  | `*/`
355 |  | `public void setNormalizeRankings(boolean normalizeRankings) {`
356 | 0 | `mNormalizeRankings = normalizeRankings;`
357 | 0 | `}`
358 |  | ``
359 |  | `/**`
360 |  | `* Allows the user to provide his own set of data instances as edge weights by giving the ranker`
361 |  | `* the <code>UserDatum</code> key where those instances can be found.`
362 |  | `* @param keyName the name of the <code>UserDatum</code> key where the data instance representing an edge weight`
363 |  | `* can be found`
364 |  | `*/`
365 |  | `public void setUserDefinedEdgeWeightKey(String keyName) {`
366 | 3 | `mUserDefinedEdgeWeightKey = keyName;`
367 | 3 | `}`
368 |  | `}`

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.