X-Git-Url: https://git.opendaylight.org/gerrit/gitweb?p=controller.git;a=blobdiff_plain;f=third-party%2Fnet.sf.jung2%2Fsrc%2Fmain%2Fjava%2Fedu%2Fuci%2Fics%2Fjung%2Falgorithms%2Fimportance%2FAbstractRanker.java;fp=third-party%2Fnet.sf.jung2%2Fsrc%2Fmain%2Fjava%2Fedu%2Fuci%2Fics%2Fjung%2Falgorithms%2Fimportance%2FAbstractRanker.java;h=0000000000000000000000000000000000000000;hp=6ea8bc84a7083f8f84b8e109d749d6b6710a64e4;hb=e1c04c5af263a9604a765f1ab98be51dfc51d8cb;hpb=a935ffda7f26be29de879a47b426d0db7a28d588 diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/importance/AbstractRanker.java b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/importance/AbstractRanker.java deleted file mode 100644 index 6ea8bc84a7..0000000000 --- a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/importance/AbstractRanker.java +++ /dev/null @@ -1,388 +0,0 @@ -/* -* 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: - * - *

- * 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; - } -}