2 * Copyright (c) 2003, the JUNG Project and the Regents of the University
6 * This software is open-source under the BSD license; see either
8 * http://jung.sourceforge.net/license.txt for a description.
10 package edu.uci.ics.jung.algorithms.importance;
12 import java.text.DecimalFormat;
13 import java.text.Format;
14 import java.util.ArrayList;
15 import java.util.Collection;
16 import java.util.Collections;
17 import java.util.HashMap;
18 import java.util.List;
21 import org.apache.commons.collections15.Factory;
22 import org.apache.commons.collections15.map.LazyMap;
24 import edu.uci.ics.jung.algorithms.util.IterativeProcess;
25 import edu.uci.ics.jung.graph.Graph;
28 * Abstract class for algorithms that rank nodes or edges by some "importance" metric. Provides a common set of
31 * <li> storing rank scores</li>
32 * <li> getters and setters for rank scores</li>
33 * <li> computing default edge weights</li>
34 * <li> normalizing default or user-provided edge transition weights </li>
35 * <li> normalizing rank scores</li>
36 * <li> automatic cleanup of decorations</li>
37 * <li> creation of Ranking list</li>
38 * <li>print rankings in sorted order by rank</li>
41 * By default, all rank scores are removed from the vertices (or edges) being ranked.
44 public abstract class AbstractRanker<V,E> extends IterativeProcess {
45 private Graph<V,E> mGraph;
46 private List<Ranking<?>> mRankings;
47 private boolean mRemoveRankScoresOnFinalize;
48 private boolean mRankNodes;
49 private boolean mRankEdges;
50 private boolean mNormalizeRankings;
51 protected Map<Object,Map<V, Number>> vertexRankScores =
53 new HashMap<Object,Map<V,Number>>(),
54 new Factory<Map<V,Number>>() {
55 public Map<V,Number> create() {
56 return new HashMap<V,Number>();
58 protected Map<Object,Map<E, Number>> edgeRankScores =
60 new HashMap<Object,Map<E,Number>>(),
61 new Factory<Map<E,Number>>() {
62 public Map<E,Number> create() {
63 return new HashMap<E,Number>();
65 private Map<E,Number> edgeWeights = new HashMap<E,Number>();
67 protected void initialize(Graph<V,E> graph, boolean isNodeRanker,
68 boolean isEdgeRanker) {
69 if (!isNodeRanker && !isEdgeRanker)
70 throw new IllegalArgumentException("Must rank edges, vertices, or both");
72 mRemoveRankScoresOnFinalize = true;
73 mNormalizeRankings = true;
74 mRankNodes = isNodeRanker;
75 mRankEdges = isEdgeRanker;
79 * @return all rankScores
81 public Map<Object,Map<V, Number>> getVertexRankScores() {
82 return vertexRankScores;
85 public Map<Object,Map<E, Number>> getEdgeRankScores() {
86 return edgeRankScores;
90 * @return the rankScores
92 public Map<V, Number> getVertexRankScores(Object key) {
93 return vertexRankScores.get(key);
96 public Map<E, Number> getEdgeRankScores(Object key) {
97 return edgeRankScores.get(key);
100 protected Collection<V> getVertices() {
101 return mGraph.getVertices();
104 protected int getVertexCount() {
105 return mGraph.getVertexCount();
108 protected Graph<V,E> getGraph() {
113 public void reset() {
117 * Returns <code>true</code> if this ranker ranks nodes, and
118 * <code>false</code> otherwise.
120 public boolean isRankingNodes() {
125 * Returns <code>true</code> if this ranker ranks edges, and
126 * <code>false</code> otherwise.
128 public boolean isRankingEdges() {
133 * Instructs the ranker whether or not it should remove the rank scores from the nodes (or edges) once the ranks
134 * have been computed.
135 * @param removeRankScoresOnFinalize <code>true</code> if the rank scores are to be removed, <code>false</code> otherwise
137 public void setRemoveRankScoresOnFinalize(boolean removeRankScoresOnFinalize) {
138 this.mRemoveRankScoresOnFinalize = removeRankScoresOnFinalize;
141 protected void onFinalize(Object e) {}
144 * The user datum key used to store the rank score.
147 abstract public Object getRankScoreKey();
151 protected void finalizeIterations() {
152 List<Ranking<?>> sortedRankings = new ArrayList<Ranking<?>>();
156 for (V currentVertex : getVertices()) {
157 Ranking<V> ranking = new Ranking<V>(id,getVertexRankScore(currentVertex),currentVertex);
158 sortedRankings.add(ranking);
159 if (mRemoveRankScoresOnFinalize) {
160 this.vertexRankScores.get(getRankScoreKey()).remove(currentVertex);
163 onFinalize(currentVertex);
167 for (E currentEdge : mGraph.getEdges()) {
169 Ranking<E> ranking = new Ranking<E>(id,getEdgeRankScore(currentEdge),currentEdge);
170 sortedRankings.add(ranking);
171 if (mRemoveRankScoresOnFinalize) {
172 this.edgeRankScores.get(getRankScoreKey()).remove(currentEdge);
175 onFinalize(currentEdge);
179 mRankings = sortedRankings;
180 Collections.sort(mRankings);
184 * Retrieves the list of ranking instances in descending sorted order by rank score
185 * If the algorithm is ranking edges, the instances will be of type <code>EdgeRanking</code>, otherwise
186 * if the algorithm is ranking nodes the instances will be of type <code>NodeRanking</code>
187 * @return the list of rankings
189 public List<Ranking<?>> getRankings() {
194 * Return a list of the top k rank scores.
195 * @param topKRankings the value of k to use
196 * @return list of rank scores
198 public List<Double> getRankScores(int topKRankings) {
199 List<Double> scores = new ArrayList<Double>();
201 for (Ranking<?> currentRanking : getRankings()) {
202 if (count > topKRankings) {
205 scores.add(currentRanking.rankScore);
213 * Given an edge or node, returns the corresponding rank score. This is a default
214 * implementation of getRankScore which assumes the decorations are of type MutableDouble.
215 * This method only returns legal values if <code>setRemoveRankScoresOnFinalize(false)</code> was called
216 * prior to <code>evaluate()</code>.
217 * @return the rank score value
219 public double getVertexRankScore(V v) {
220 Number rankScore = vertexRankScores.get(getRankScoreKey()).get(v);
221 if (rankScore != null) {
222 return rankScore.doubleValue();
224 throw new RuntimeException("setRemoveRankScoresOnFinalize(false) must be called before evaluate().");
228 public double getVertexRankScore(V v, Object key) {
229 return vertexRankScores.get(key).get(v).doubleValue();
232 public double getEdgeRankScore(E e) {
233 Number rankScore = edgeRankScores.get(getRankScoreKey()).get(e);
234 if (rankScore != null) {
235 return rankScore.doubleValue();
237 throw new RuntimeException("setRemoveRankScoresOnFinalize(false) must be called before evaluate().");
241 public double getEdgeRankScore(E e, Object key) {
242 return edgeRankScores.get(key).get(e).doubleValue();
245 protected void setVertexRankScore(V v, double rankValue, Object key) {
246 vertexRankScores.get(key).put(v, rankValue);
249 protected void setEdgeRankScore(E e, double rankValue, Object key) {
250 edgeRankScores.get(key).put(e, rankValue);
253 protected void setVertexRankScore(V v, double rankValue) {
254 setVertexRankScore(v,rankValue, getRankScoreKey());
257 protected void setEdgeRankScore(E e, double rankValue) {
258 setEdgeRankScore(e, rankValue, getRankScoreKey());
261 protected void removeVertexRankScore(V v, Object key) {
262 vertexRankScores.get(key).remove(v);
265 protected void removeEdgeRankScore(E e, Object key) {
266 edgeRankScores.get(key).remove(e);
269 protected void removeVertexRankScore(V v) {
270 vertexRankScores.get(getRankScoreKey()).remove(v);
273 protected void removeEdgeRankScore(E e) {
274 edgeRankScores.get(getRankScoreKey()).remove(e);
277 protected double getEdgeWeight(E e) {
278 return edgeWeights.get(e).doubleValue();
281 protected void setEdgeWeight(E e, double weight) {
282 edgeWeights.put(e, weight);
285 public void setEdgeWeights(Map<E,Number> edgeWeights) {
286 this.edgeWeights = edgeWeights;
290 * @return the edgeWeights
292 public Map<E, Number> getEdgeWeights() {
296 protected void assignDefaultEdgeTransitionWeights() {
298 for (V currentVertex : getVertices()) {
300 Collection<E> outgoingEdges = mGraph.getOutEdges(currentVertex);
302 double numOutEdges = outgoingEdges.size();
303 for (E currentEdge : outgoingEdges) {
304 setEdgeWeight(currentEdge,1.0/numOutEdges);
309 protected void normalizeEdgeTransitionWeights() {
311 for (V currentVertex : getVertices()) {
313 Collection<E> outgoingEdges = mGraph.getOutEdges(currentVertex);
315 double totalEdgeWeight = 0;
316 for (E currentEdge : outgoingEdges) {
317 totalEdgeWeight += getEdgeWeight(currentEdge);
320 for (E currentEdge : outgoingEdges) {
321 setEdgeWeight(currentEdge,getEdgeWeight(currentEdge)/totalEdgeWeight);
326 protected void normalizeRankings() {
327 if (!mNormalizeRankings) {
330 double totalWeight = 0;
332 for (V currentVertex : getVertices()) {
333 totalWeight += getVertexRankScore(currentVertex);
336 for (V currentVertex : getVertices()) {
337 setVertexRankScore(currentVertex,getVertexRankScore(currentVertex)/totalWeight);
342 * Print the rankings to standard out in descending order of rank score
343 * @param verbose if <code>true</code>, include information about the actual rank order as well as
344 * the original position of the vertex before it was ranked
345 * @param printScore if <code>true</code>, include the actual value of the rank score
347 public void printRankings(boolean verbose,boolean printScore) {
349 Format formatter = new DecimalFormat("#0.#######");
352 for (Ranking<?> currentRanking : getRankings()) {
353 double rankScore = currentRanking.rankScore;
355 System.out.print("Rank " + rank + ": ");
357 System.out.print(formatter.format(rankScore));
359 System.out.print("\tVertex Id: " + currentRanking.originalPos);
360 System.out.print(" (" + currentRanking.getRanked() + ")");
361 System.out.println();
363 System.out.print(rank + "\t");
365 System.out.print(formatter.format(rankScore));
367 System.out.println("\t" + currentRanking.originalPos);
375 System.out.println("Total: " + formatter.format(total));
380 * Allows the user to specify whether or not s/he wants the rankings to be normalized.
381 * In some cases, this will have no effect since the algorithm doesn't allow normalization
383 * @param normalizeRankings
385 public void setNormalizeRankings(boolean normalizeRankings) {
386 mNormalizeRankings = normalizeRankings;