/*
* 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:
*
* storing rank scores
* getters and setters for rank scores
* computing default edge weights
* normalizing default or user-provided edge transition weights
* normalizing rank scores
* automatic cleanup of decorations
* creation of Ranking list
* print rankings in sorted order by rank
*
*
* By default, all rank scores are removed from the vertices (or edges) being ranked.
* @author Scott White
*/
public abstract class AbstractRanker extends IterativeProcess {
private Graph mGraph;
private List> mRankings;
private boolean mRemoveRankScoresOnFinalize;
private boolean mRankNodes;
private boolean mRankEdges;
private boolean mNormalizeRankings;
protected Map> vertexRankScores =
LazyMap.decorate(
new HashMap>(),
new Factory>() {
public Map create() {
return new HashMap();
}});
protected Map> edgeRankScores =
LazyMap.decorate(
new HashMap>(),
new Factory>() {
public Map create() {
return new HashMap();
}});
private Map edgeWeights = new HashMap();
protected void initialize(Graph 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> getVertexRankScores() {
return vertexRankScores;
}
public Map> getEdgeRankScores() {
return edgeRankScores;
}
/**
* @return the rankScores
*/
public Map getVertexRankScores(Object key) {
return vertexRankScores.get(key);
}
public Map getEdgeRankScores(Object key) {
return edgeRankScores.get(key);
}
protected Collection getVertices() {
return mGraph.getVertices();
}
protected int getVertexCount() {
return mGraph.getVertexCount();
}
protected Graph getGraph() {
return mGraph;
}
@Override
public void reset() {
}
/**
* Returns true
if this ranker ranks nodes, and
* false
otherwise.
*/
public boolean isRankingNodes() {
return mRankNodes;
}
/**
* Returns true
if this ranker ranks edges, and
* false
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 true
if the rank scores are to be removed, false
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> sortedRankings = new ArrayList>();
int id = 1;
if (mRankNodes) {
for (V currentVertex : getVertices()) {
Ranking ranking = new Ranking(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 ranking = new Ranking(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 EdgeRanking
, otherwise
* if the algorithm is ranking nodes the instances will be of type NodeRanking
* @return the list of rankings
*/
public List> 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 getRankScores(int topKRankings) {
List scores = new ArrayList();
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 setRemoveRankScoresOnFinalize(false)
was called
* prior to evaluate()
.
* @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 edgeWeights) {
this.edgeWeights = edgeWeights;
}
/**
* @return the edgeWeights
*/
public Map getEdgeWeights() {
return edgeWeights;
}
protected void assignDefaultEdgeTransitionWeights() {
for (V currentVertex : getVertices()) {
Collection 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 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 true
, include information about the actual rank order as well as
* the original position of the vertex before it was ranked
* @param printScore if true
, 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;
}
}