--- /dev/null
+/*
+* Copyright (c) 2003, the JUNG Project and the Regents of the University
+* of California
+* All rights reserved.
+*
+* This software is open-source under the BSD license; see either
+* "license.txt" or
+* http://jung.sourceforge.net/license.txt for a description.
+*/
+package edu.uci.ics.jung.algorithms.importance;
+
+import java.text.DecimalFormat;
+import java.text.Format;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+import org.apache.commons.collections15.Factory;
+import org.apache.commons.collections15.map.LazyMap;
+
+import edu.uci.ics.jung.algorithms.util.IterativeProcess;
+import edu.uci.ics.jung.graph.Graph;
+
+/**
+ * Abstract class for algorithms that rank nodes or edges by some "importance" metric. Provides a common set of
+ * services such as:
+ * <ul>
+ * <li> storing rank scores</li>
+ * <li> getters and setters for rank scores</li>
+ * <li> computing default edge weights</li>
+ * <li> normalizing default or user-provided edge transition weights </li>
+ * <li> normalizing rank scores</li>
+ * <li> automatic cleanup of decorations</li>
+ * <li> creation of Ranking list</li>
+ * <li>print rankings in sorted order by rank</li>
+ * </ul>
+ * <p>
+ * By default, all rank scores are removed from the vertices (or edges) being ranked.
+ * @author Scott White
+ */
+public abstract class AbstractRanker<V,E> extends IterativeProcess {
+ private Graph<V,E> mGraph;
+ private List<Ranking<?>> mRankings;
+ private boolean mRemoveRankScoresOnFinalize;
+ private boolean mRankNodes;
+ private boolean mRankEdges;
+ private boolean mNormalizeRankings;
+ protected Map<Object,Map<V, Number>> vertexRankScores =
+ LazyMap.decorate(
+ new HashMap<Object,Map<V,Number>>(),
+ new Factory<Map<V,Number>>() {
+ public Map<V,Number> create() {
+ return new HashMap<V,Number>();
+ }});
+ protected Map<Object,Map<E, Number>> edgeRankScores =
+ LazyMap.decorate(
+ new HashMap<Object,Map<E,Number>>(),
+ new Factory<Map<E,Number>>() {
+ public Map<E,Number> create() {
+ return new HashMap<E,Number>();
+ }});
+ private Map<E,Number> edgeWeights = new HashMap<E,Number>();
+
+ protected void initialize(Graph<V,E> graph, boolean isNodeRanker,
+ boolean isEdgeRanker) {
+ if (!isNodeRanker && !isEdgeRanker)
+ throw new IllegalArgumentException("Must rank edges, vertices, or both");
+ mGraph = graph;
+ mRemoveRankScoresOnFinalize = true;
+ mNormalizeRankings = true;
+ mRankNodes = isNodeRanker;
+ mRankEdges = isEdgeRanker;
+ }
+
+ /**
+ * @return all rankScores
+ */
+ public Map<Object,Map<V, Number>> getVertexRankScores() {
+ return vertexRankScores;
+ }
+
+ public Map<Object,Map<E, Number>> getEdgeRankScores() {
+ return edgeRankScores;
+ }
+
+ /**
+ * @return the rankScores
+ */
+ public Map<V, Number> getVertexRankScores(Object key) {
+ return vertexRankScores.get(key);
+ }
+
+ public Map<E, Number> getEdgeRankScores(Object key) {
+ return edgeRankScores.get(key);
+ }
+
+ protected Collection<V> getVertices() {
+ return mGraph.getVertices();
+ }
+
+ protected int getVertexCount() {
+ return mGraph.getVertexCount();
+ }
+
+ protected Graph<V,E> getGraph() {
+ return mGraph;
+ }
+
+ @Override
+ public void reset() {
+ }
+
+ /**
+ * Returns <code>true</code> if this ranker ranks nodes, and
+ * <code>false</code> otherwise.
+ */
+ public boolean isRankingNodes() {
+ return mRankNodes;
+ }
+
+ /**
+ * Returns <code>true</code> if this ranker ranks edges, and
+ * <code>false</code> otherwise.
+ */
+ public boolean isRankingEdges() {
+ return mRankEdges;
+ }
+
+ /**
+ * Instructs the ranker whether or not it should remove the rank scores from the nodes (or edges) once the ranks
+ * have been computed.
+ * @param removeRankScoresOnFinalize <code>true</code> if the rank scores are to be removed, <code>false</code> otherwise
+ */
+ public void setRemoveRankScoresOnFinalize(boolean removeRankScoresOnFinalize) {
+ this.mRemoveRankScoresOnFinalize = removeRankScoresOnFinalize;
+ }
+
+ protected void onFinalize(Object e) {}
+
+ /**
+ * The user datum key used to store the rank score.
+ * @return the key
+ */
+ abstract public Object getRankScoreKey();
+
+
+ @Override
+ protected void finalizeIterations() {
+ List<Ranking<?>> sortedRankings = new ArrayList<Ranking<?>>();
+
+ int id = 1;
+ if (mRankNodes) {
+ for (V currentVertex : getVertices()) {
+ Ranking<V> ranking = new Ranking<V>(id,getVertexRankScore(currentVertex),currentVertex);
+ sortedRankings.add(ranking);
+ if (mRemoveRankScoresOnFinalize) {
+ this.vertexRankScores.get(getRankScoreKey()).remove(currentVertex);
+ }
+ id++;
+ onFinalize(currentVertex);
+ }
+ }
+ if (mRankEdges) {
+ for (E currentEdge : mGraph.getEdges()) {
+
+ Ranking<E> ranking = new Ranking<E>(id,getEdgeRankScore(currentEdge),currentEdge);
+ sortedRankings.add(ranking);
+ if (mRemoveRankScoresOnFinalize) {
+ this.edgeRankScores.get(getRankScoreKey()).remove(currentEdge);
+ }
+ id++;
+ onFinalize(currentEdge);
+ }
+ }
+
+ mRankings = sortedRankings;
+ Collections.sort(mRankings);
+ }
+
+ /**
+ * Retrieves the list of ranking instances in descending sorted order by rank score
+ * If the algorithm is ranking edges, the instances will be of type <code>EdgeRanking</code>, otherwise
+ * if the algorithm is ranking nodes the instances will be of type <code>NodeRanking</code>
+ * @return the list of rankings
+ */
+ public List<Ranking<?>> getRankings() {
+ return mRankings;
+ }
+
+ /**
+ * Return a list of the top k rank scores.
+ * @param topKRankings the value of k to use
+ * @return list of rank scores
+ */
+ public List<Double> getRankScores(int topKRankings) {
+ List<Double> scores = new ArrayList<Double>();
+ int count=1;
+ for (Ranking<?> currentRanking : getRankings()) {
+ if (count > topKRankings) {
+ return scores;
+ }
+ scores.add(currentRanking.rankScore);
+ count++;
+ }
+
+ return scores;
+ }
+
+ /**
+ * Given an edge or node, returns the corresponding rank score. This is a default
+ * implementation of getRankScore which assumes the decorations are of type MutableDouble.
+ * This method only returns legal values if <code>setRemoveRankScoresOnFinalize(false)</code> was called
+ * prior to <code>evaluate()</code>.
+ * @return the rank score value
+ */
+ public double getVertexRankScore(V v) {
+ Number rankScore = vertexRankScores.get(getRankScoreKey()).get(v);
+ if (rankScore != null) {
+ return rankScore.doubleValue();
+ } else {
+ throw new RuntimeException("setRemoveRankScoresOnFinalize(false) must be called before evaluate().");
+ }
+ }
+
+ public double getVertexRankScore(V v, Object key) {
+ return vertexRankScores.get(key).get(v).doubleValue();
+ }
+
+ public double getEdgeRankScore(E e) {
+ Number rankScore = edgeRankScores.get(getRankScoreKey()).get(e);
+ if (rankScore != null) {
+ return rankScore.doubleValue();
+ } else {
+ throw new RuntimeException("setRemoveRankScoresOnFinalize(false) must be called before evaluate().");
+ }
+ }
+
+ public double getEdgeRankScore(E e, Object key) {
+ return edgeRankScores.get(key).get(e).doubleValue();
+ }
+
+ protected void setVertexRankScore(V v, double rankValue, Object key) {
+ vertexRankScores.get(key).put(v, rankValue);
+ }
+
+ protected void setEdgeRankScore(E e, double rankValue, Object key) {
+ edgeRankScores.get(key).put(e, rankValue);
+ }
+
+ protected void setVertexRankScore(V v, double rankValue) {
+ setVertexRankScore(v,rankValue, getRankScoreKey());
+ }
+
+ protected void setEdgeRankScore(E e, double rankValue) {
+ setEdgeRankScore(e, rankValue, getRankScoreKey());
+ }
+
+ protected void removeVertexRankScore(V v, Object key) {
+ vertexRankScores.get(key).remove(v);
+ }
+
+ protected void removeEdgeRankScore(E e, Object key) {
+ edgeRankScores.get(key).remove(e);
+ }
+
+ protected void removeVertexRankScore(V v) {
+ vertexRankScores.get(getRankScoreKey()).remove(v);
+ }
+
+ protected void removeEdgeRankScore(E e) {
+ edgeRankScores.get(getRankScoreKey()).remove(e);
+ }
+
+ protected double getEdgeWeight(E e) {
+ return edgeWeights.get(e).doubleValue();
+ }
+
+ protected void setEdgeWeight(E e, double weight) {
+ edgeWeights.put(e, weight);
+ }
+
+ public void setEdgeWeights(Map<E,Number> edgeWeights) {
+ this.edgeWeights = edgeWeights;
+ }
+
+ /**
+ * @return the edgeWeights
+ */
+ public Map<E, Number> getEdgeWeights() {
+ return edgeWeights;
+ }
+
+ protected void assignDefaultEdgeTransitionWeights() {
+
+ for (V currentVertex : getVertices()) {
+
+ Collection<E> outgoingEdges = mGraph.getOutEdges(currentVertex);
+
+ double numOutEdges = outgoingEdges.size();
+ for (E currentEdge : outgoingEdges) {
+ setEdgeWeight(currentEdge,1.0/numOutEdges);
+ }
+ }
+ }
+
+ protected void normalizeEdgeTransitionWeights() {
+
+ for (V currentVertex : getVertices()) {
+
+ Collection<E> outgoingEdges = mGraph.getOutEdges(currentVertex);
+
+ double totalEdgeWeight = 0;
+ for (E currentEdge : outgoingEdges) {
+ totalEdgeWeight += getEdgeWeight(currentEdge);
+ }
+
+ for (E currentEdge : outgoingEdges) {
+ setEdgeWeight(currentEdge,getEdgeWeight(currentEdge)/totalEdgeWeight);
+ }
+ }
+ }
+
+ protected void normalizeRankings() {
+ if (!mNormalizeRankings) {
+ return;
+ }
+ double totalWeight = 0;
+
+ for (V currentVertex : getVertices()) {
+ totalWeight += getVertexRankScore(currentVertex);
+ }
+
+ for (V currentVertex : getVertices()) {
+ setVertexRankScore(currentVertex,getVertexRankScore(currentVertex)/totalWeight);
+ }
+ }
+
+ /**
+ * Print the rankings to standard out in descending order of rank score
+ * @param verbose if <code>true</code>, include information about the actual rank order as well as
+ * the original position of the vertex before it was ranked
+ * @param printScore if <code>true</code>, include the actual value of the rank score
+ */
+ public void printRankings(boolean verbose,boolean printScore) {
+ double total = 0;
+ Format formatter = new DecimalFormat("#0.#######");
+ int rank = 1;
+
+ for (Ranking<?> currentRanking : getRankings()) {
+ double rankScore = currentRanking.rankScore;
+ if (verbose) {
+ System.out.print("Rank " + rank + ": ");
+ if (printScore) {
+ System.out.print(formatter.format(rankScore));
+ }
+ System.out.print("\tVertex Id: " + currentRanking.originalPos);
+ System.out.print(" (" + currentRanking.getRanked() + ")");
+ System.out.println();
+ } else {
+ System.out.print(rank + "\t");
+ if (printScore) {
+ System.out.print(formatter.format(rankScore));
+ }
+ System.out.println("\t" + currentRanking.originalPos);
+
+ }
+ total += rankScore;
+ rank++;
+ }
+
+ if (verbose) {
+ System.out.println("Total: " + formatter.format(total));
+ }
+ }
+
+ /**
+ * Allows the user to specify whether or not s/he wants the rankings to be normalized.
+ * In some cases, this will have no effect since the algorithm doesn't allow normalization
+ * as an option
+ * @param normalizeRankings
+ */
+ public void setNormalizeRankings(boolean normalizeRankings) {
+ mNormalizeRankings = normalizeRankings;
+ }
+}