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. |
copyright © 2003, jcoverage ltd. all rights reserved. |