third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/importance/AbstractRanker.java

   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.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;
  19 import java.util.Map;
  20
  21 import org.apache.commons.collections15.Factory;
  22 import org.apache.commons.collections15.map.LazyMap;
  23
  24 import edu.uci.ics.jung.algorithms.util.IterativeProcess;
  25 import edu.uci.ics.jung.graph.Graph;
  26
  27 /**
  28  * Abstract class for algorithms that rank nodes or edges by some "importance" metric. Provides a common set of
  29  * services such as:
  30  * <ul>
  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>
  39  * </ul>
  40  * <p>
  41  * By default, all rank scores are removed from the vertices (or edges) being ranked.
  42  * @author Scott White
  43  */
  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 =
  52         LazyMap.decorate(
  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>();
  57                                         }});
  58     protected Map<Object,Map<E, Number>> edgeRankScores =
  59         LazyMap.decorate(
  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>();
  64                                         }});
  65     private Map<E,Number> edgeWeights = new HashMap<E,Number>();
  66
  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");
  71         mGraph = graph;
  72         mRemoveRankScoresOnFinalize = true;
  73         mNormalizeRankings = true;
  74         mRankNodes = isNodeRanker;
  75         mRankEdges = isEdgeRanker;
  76     }
  77
  78     /**
  79          * @return all rankScores
  80          */
  81         public Map<Object,Map<V, Number>> getVertexRankScores() {
  82                 return vertexRankScores;
  83         }
  84
  85         public Map<Object,Map<E, Number>> getEdgeRankScores() {
  86                 return edgeRankScores;
  87         }
  88
  89     /**
  90          * @return the rankScores
  91          */
  92         public Map<V, Number> getVertexRankScores(Object key) {
  93                 return vertexRankScores.get(key);
  94         }
  95
  96         public Map<E, Number> getEdgeRankScores(Object key) {
  97                 return edgeRankScores.get(key);
  98         }
  99
 100         protected Collection<V> getVertices() {
 101         return mGraph.getVertices();
 102     }
 103
 104         protected int getVertexCount() {
 105         return mGraph.getVertexCount();
 106     }
 107
 108     protected Graph<V,E> getGraph() {
 109         return mGraph;
 110     }
 111
 112     @Override
 113     public void reset() {
 114     }
 115
 116     /**
 117      * Returns <code>true</code> if this ranker ranks nodes, and
 118      * <code>false</code> otherwise.
 119      */
 120     public boolean isRankingNodes() {
 121         return mRankNodes;
 122     }
 123
 124     /**
 125      * Returns <code>true</code> if this ranker ranks edges, and
 126      * <code>false</code> otherwise.
 127      */
 128     public boolean isRankingEdges() {
 129         return mRankEdges;
 130     }
 131
 132     /**
 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
 136      */
 137     public void setRemoveRankScoresOnFinalize(boolean removeRankScoresOnFinalize) {
 138         this.mRemoveRankScoresOnFinalize = removeRankScoresOnFinalize;
 139     }
 140
 141     protected void onFinalize(Object e) {}
 142
 143     /**
 144      * The user datum key used to store the rank score.
 145      * @return the key
 146      */
 147     abstract public Object getRankScoreKey();
 148
 149
 150     @Override
 151     protected void finalizeIterations() {
 152         List<Ranking<?>> sortedRankings = new ArrayList<Ranking<?>>();
 153
 154         int id = 1;
 155         if (mRankNodes) {
 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);
 161                 }
 162                 id++;
 163                 onFinalize(currentVertex);
 164             }
 165         }
 166         if (mRankEdges) {
 167             for (E currentEdge : mGraph.getEdges()) {
 168
 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);
 173                 }
 174                 id++;
 175                 onFinalize(currentEdge);
 176             }
 177         }
 178
 179         mRankings = sortedRankings;
 180         Collections.sort(mRankings);
 181     }
 182
 183     /**
 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
 188      */
 189     public List<Ranking<?>> getRankings() {
 190         return mRankings;
 191     }
 192
 193     /**
 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
 197      */
 198     public List<Double> getRankScores(int topKRankings) {
 199         List<Double> scores = new ArrayList<Double>();
 200         int count=1;
 201         for (Ranking<?> currentRanking : getRankings()) {
 202             if (count > topKRankings) {
 203                 return scores;
 204             }
 205             scores.add(currentRanking.rankScore);
 206             count++;
 207         }
 208
 209         return scores;
 210     }
 211
 212     /**
 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
 218      */
 219     public double getVertexRankScore(V v) {
 220         Number rankScore = vertexRankScores.get(getRankScoreKey()).get(v);
 221         if (rankScore != null) {
 222             return rankScore.doubleValue();
 223         } else {
 224             throw new RuntimeException("setRemoveRankScoresOnFinalize(false) must be called before evaluate().");
 225         }
 226     }
 227
 228     public double getVertexRankScore(V v, Object key) {
 229         return vertexRankScores.get(key).get(v).doubleValue();
 230     }
 231
 232     public double getEdgeRankScore(E e) {
 233         Number rankScore = edgeRankScores.get(getRankScoreKey()).get(e);
 234         if (rankScore != null) {
 235             return rankScore.doubleValue();
 236         } else {
 237             throw new RuntimeException("setRemoveRankScoresOnFinalize(false) must be called before evaluate().");
 238         }
 239     }
 240
 241     public double getEdgeRankScore(E e, Object key) {
 242         return edgeRankScores.get(key).get(e).doubleValue();
 243     }
 244
 245     protected void setVertexRankScore(V v, double rankValue, Object key) {
 246         vertexRankScores.get(key).put(v, rankValue);
 247     }
 248
 249     protected void setEdgeRankScore(E e, double rankValue, Object key) {
 250                 edgeRankScores.get(key).put(e, rankValue);
 251     }
 252
 253     protected void setVertexRankScore(V v, double rankValue) {
 254         setVertexRankScore(v,rankValue, getRankScoreKey());
 255     }
 256
 257     protected void setEdgeRankScore(E e, double rankValue) {
 258         setEdgeRankScore(e, rankValue, getRankScoreKey());
 259     }
 260
 261     protected void removeVertexRankScore(V v, Object key) {
 262         vertexRankScores.get(key).remove(v);
 263     }
 264
 265     protected void removeEdgeRankScore(E e, Object key) {
 266         edgeRankScores.get(key).remove(e);
 267     }
 268
 269     protected void removeVertexRankScore(V v) {
 270         vertexRankScores.get(getRankScoreKey()).remove(v);
 271     }
 272
 273     protected void removeEdgeRankScore(E e) {
 274         edgeRankScores.get(getRankScoreKey()).remove(e);
 275     }
 276
 277     protected double getEdgeWeight(E e) {
 278         return edgeWeights.get(e).doubleValue();
 279     }
 280
 281     protected void setEdgeWeight(E e, double weight) {
 282         edgeWeights.put(e, weight);
 283     }
 284
 285     public void setEdgeWeights(Map<E,Number> edgeWeights) {
 286         this.edgeWeights = edgeWeights;
 287     }
 288
 289     /**
 290          * @return the edgeWeights
 291          */
 292         public Map<E, Number> getEdgeWeights() {
 293                 return edgeWeights;
 294         }
 295
 296         protected void assignDefaultEdgeTransitionWeights() {
 297
 298         for (V currentVertex : getVertices()) {
 299
 300             Collection<E> outgoingEdges = mGraph.getOutEdges(currentVertex);
 301
 302             double numOutEdges = outgoingEdges.size();
 303             for (E currentEdge : outgoingEdges) {
 304                 setEdgeWeight(currentEdge,1.0/numOutEdges);
 305             }
 306         }
 307     }
 308
 309     protected void normalizeEdgeTransitionWeights() {
 310
 311         for (V currentVertex : getVertices()) {
 312
 313                 Collection<E> outgoingEdges = mGraph.getOutEdges(currentVertex);
 314
 315             double totalEdgeWeight = 0;
 316             for (E currentEdge : outgoingEdges) {
 317                 totalEdgeWeight += getEdgeWeight(currentEdge);
 318             }
 319
 320             for (E currentEdge : outgoingEdges) {
 321                 setEdgeWeight(currentEdge,getEdgeWeight(currentEdge)/totalEdgeWeight);
 322             }
 323         }
 324     }
 325
 326     protected void normalizeRankings() {
 327         if (!mNormalizeRankings) {
 328             return;
 329         }
 330         double totalWeight = 0;
 331
 332         for (V currentVertex : getVertices()) {
 333             totalWeight += getVertexRankScore(currentVertex);
 334         }
 335
 336         for (V currentVertex : getVertices()) {
 337             setVertexRankScore(currentVertex,getVertexRankScore(currentVertex)/totalWeight);
 338         }
 339     }
 340
 341     /**
 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
 346      */
 347     public void printRankings(boolean verbose,boolean printScore) {
 348             double total = 0;
 349             Format formatter = new DecimalFormat("#0.#######");
 350             int rank = 1;
 351
 352             for (Ranking<?> currentRanking : getRankings()) {
 353                 double rankScore = currentRanking.rankScore;
 354                 if (verbose) {
 355                     System.out.print("Rank " + rank + ": ");
 356                     if (printScore) {
 357                         System.out.print(formatter.format(rankScore));
 358                     }
 359                     System.out.print("\tVertex Id: " + currentRanking.originalPos);
 360                         System.out.print(" (" + currentRanking.getRanked() + ")");
 361                     System.out.println();
 362                 } else {
 363                     System.out.print(rank + "\t");
 364                      if (printScore) {
 365                         System.out.print(formatter.format(rankScore));
 366                     }
 367                     System.out.println("\t" + currentRanking.originalPos);
 368
 369                 }
 370                 total += rankScore;
 371                 rank++;
 372             }
 373
 374             if (verbose) {
 375                 System.out.println("Total: " + formatter.format(total));
 376             }
 377     }
 378
 379     /**
 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
 382      * as an option
 383      * @param normalizeRankings
 384      */
 385     public void setNormalizeRankings(boolean normalizeRankings) {
 386         mNormalizeRankings = normalizeRankings;
 387     }
 388 }