-/*
-* 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;
- }
-}
Code Review / controller.git / blobdiff