edu.uci.ics.jung.algorithms.importance
Class AbstractRanker<V,E>

java.lang.Object
  edu.uci.ics.jung.algorithms.util.IterativeProcess
      edu.uci.ics.jung.algorithms.importance.AbstractRanker<V,E>

All Implemented Interfaces:

IterativeContext

Direct Known Subclasses:

BetweennessCentrality, RandomWalkSTBetweenness, RelativeAuthorityRanker, WeightedNIPaths

public abstract class AbstractRanker<V,E>
extends IterativeProcess

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

Field Summary

protected Map<Object,Map<E,Number>>	edgeRankScores
protected Map<Object,Map<V,Number>>	vertexRankScores

Constructor Summary

AbstractRanker()

Method Summary

protected void	assignDefaultEdgeTransitionWeights()
protected void	finalizeIterations() Perform eventual clean-up operations (must be implement by subclass when needed).
double	getEdgeRankScore(E e)
double	getEdgeRankScore(E e, Object key)
Map<Object,Map<E,Number>>	getEdgeRankScores()
Map<E,Number>	getEdgeRankScores(Object key)
protected double	getEdgeWeight(E e)
Map<E,Number>	getEdgeWeights()
protected Graph<V,E>	getGraph()
List<Ranking<?>>	getRankings() 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
abstract Object	getRankScoreKey() The user datum key used to store the rank score.
List<Double>	getRankScores(int topKRankings) Return a list of the top k rank scores.
protected int	getVertexCount()
double	getVertexRankScore(V v) Given an edge or node, returns the corresponding rank score.
double	getVertexRankScore(V v, Object key)
Map<Object,Map<V,Number>>	getVertexRankScores()
Map<V,Number>	getVertexRankScores(Object key)
protected Collection<V>	getVertices()
protected void	initialize(Graph<V,E> graph, boolean isNodeRanker, boolean isEdgeRanker)
boolean	isRankingEdges() Returns true if this ranker ranks edges, and false otherwise.
boolean	isRankingNodes() Returns true if this ranker ranks nodes, and false otherwise.
protected void	normalizeEdgeTransitionWeights()
protected void	normalizeRankings()
protected void	onFinalize(Object e)
void	printRankings(boolean verbose, boolean printScore) Print the rankings to standard out in descending order of rank score
protected void	removeEdgeRankScore(E e)
protected void	removeEdgeRankScore(E e, Object key)
protected void	removeVertexRankScore(V v)
protected void	removeVertexRankScore(V v, Object key)
void	reset()
protected void	setEdgeRankScore(E e, double rankValue)
protected void	setEdgeRankScore(E e, double rankValue, Object key)
protected void	setEdgeWeight(E e, double weight)
void	setEdgeWeights(Map<E,Number> edgeWeights)
void	setNormalizeRankings(boolean normalizeRankings) Allows the user to specify whether or not s/he wants the rankings to be normalized.
void	setRemoveRankScoresOnFinalize(boolean removeRankScoresOnFinalize) Instructs the ranker whether or not it should remove the rank scores from the nodes (or edges) once the ranks have been computed.
protected void	setVertexRankScore(V v, double rankValue)
protected void	setVertexRankScore(V v, double rankValue, Object key)

Methods inherited from class edu.uci.ics.jung.algorithms.util.IterativeProcess

done, evaluate, getDesiredPrecision, getIterations, getMaximumIterations, getPrecision, hasConverged, initializeIterations, relativePrecision, setDesiredPrecision, setMaximumIterations, setPrecision, step

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

vertexRankScores

protected Map<Object,Map<V,Number>> vertexRankScores

edgeRankScores

protected Map<Object,Map<E,Number>> edgeRankScores

Constructor Detail

AbstractRanker

public AbstractRanker()

Method Detail

initialize

protected void initialize(Graph<V,E> graph,
                          boolean isNodeRanker,
                          boolean isEdgeRanker)

getVertexRankScores

public Map<Object,Map<V,Number>> getVertexRankScores()

Returns:

all rankScores

getEdgeRankScores

public Map<Object,Map<E,Number>> getEdgeRankScores()

getVertexRankScores

public Map<V,Number> getVertexRankScores(Object key)

Returns:

the rankScores

getEdgeRankScores

public Map<E,Number> getEdgeRankScores(Object key)

getVertices

protected Collection<V> getVertices()

getVertexCount

protected int getVertexCount()

getGraph

protected Graph<V,E> getGraph()

reset

public void reset()

Overrides:

reset in class IterativeProcess

isRankingNodes

public boolean isRankingNodes()

Returns true if this ranker ranks nodes, and false otherwise.

isRankingEdges

public boolean isRankingEdges()

Returns true if this ranker ranks edges, and false otherwise.

setRemoveRankScoresOnFinalize

public void setRemoveRankScoresOnFinalize(boolean removeRankScoresOnFinalize)

Instructs the ranker whether or not it should remove the rank scores from the nodes (or edges) once the ranks have been computed.

Parameters:

removeRankScoresOnFinalize - true if the rank scores are to be removed, false otherwise

onFinalize

protected void onFinalize(Object e)

getRankScoreKey

public abstract Object getRankScoreKey()

The user datum key used to store the rank score.

Returns:

the key

finalizeIterations

protected void finalizeIterations()

Description copied from class: IterativeProcess

Perform eventual clean-up operations (must be implement by subclass when needed).

Overrides:

finalizeIterations in class IterativeProcess

getRankings

public List<Ranking<?>> getRankings()

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

Returns:

the list of rankings

getRankScores

public List<Double> getRankScores(int topKRankings)

Return a list of the top k rank scores.

Parameters:

topKRankings - the value of k to use

Returns:

list of rank scores

getVertexRankScore

public double getVertexRankScore(V v)

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().

Returns:

the rank score value

getVertexRankScore

public double getVertexRankScore(V v,
                                 Object key)

getEdgeRankScore

public double getEdgeRankScore(E e)

getEdgeRankScore

public double getEdgeRankScore(E e,
                               Object key)

setVertexRankScore

protected void setVertexRankScore(V v,
                                  double rankValue,
                                  Object key)

setEdgeRankScore

protected void setEdgeRankScore(E e,
                                double rankValue,
                                Object key)

setVertexRankScore

protected void setVertexRankScore(V v,
                                  double rankValue)

setEdgeRankScore

protected void setEdgeRankScore(E e,
                                double rankValue)

removeVertexRankScore

protected void removeVertexRankScore(V v,
                                     Object key)

removeEdgeRankScore

protected void removeEdgeRankScore(E e,
                                   Object key)

removeVertexRankScore

protected void removeVertexRankScore(V v)

removeEdgeRankScore

protected void removeEdgeRankScore(E e)

getEdgeWeight

protected double getEdgeWeight(E e)

setEdgeWeight

protected void setEdgeWeight(E e,
                             double weight)

setEdgeWeights

public void setEdgeWeights(Map<E,Number> edgeWeights)

getEdgeWeights

public Map<E,Number> getEdgeWeights()

Returns:

the edgeWeights

assignDefaultEdgeTransitionWeights

protected void assignDefaultEdgeTransitionWeights()

normalizeEdgeTransitionWeights

protected void normalizeEdgeTransitionWeights()

normalizeRankings

protected void normalizeRankings()

printRankings

public void printRankings(boolean verbose,
                          boolean printScore)

Print the rankings to standard out in descending order of rank score

Parameters:

verbose - if true, include information about the actual rank order as well as the original position of the vertex before it was ranked

printScore - if true, include the actual value of the rank score

setNormalizeRankings

public void setNormalizeRankings(boolean normalizeRankings)

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

Parameters:

normalizeRankings -