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;ds=sidebyside
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:
- *
- * 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;
- }
-}