X-Git-Url: https://git.opendaylight.org/gerrit/gitweb?a=blobdiff_plain;f=third-party%2Fnet.sf.jung2%2Fsrc%2Fmain%2Fjava%2Fedu%2Fuci%2Fics%2Fjung%2Falgorithms%2Fimportance%2FWeightedNIPaths.java;fp=third-party%2Fnet.sf.jung2%2Fsrc%2Fmain%2Fjava%2Fedu%2Fuci%2Fics%2Fjung%2Falgorithms%2Fimportance%2FWeightedNIPaths.java;h=0000000000000000000000000000000000000000;hb=e1c04c5af263a9604a765f1ab98be51dfc51d8cb;hp=bd715ce7ed0b995b0082ebefd1c296d3266f6fe4;hpb=a935ffda7f26be29de879a47b426d0db7a28d588;p=controller.git diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/importance/WeightedNIPaths.java b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/importance/WeightedNIPaths.java deleted file mode 100644 index bd715ce7ed..0000000000 --- a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/importance/WeightedNIPaths.java +++ /dev/null @@ -1,194 +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.util.ArrayList; -import java.util.Collection; -import java.util.HashMap; -import java.util.HashSet; -import java.util.List; -import java.util.Map; -import java.util.Set; - -import org.apache.commons.collections15.Factory; - -import edu.uci.ics.jung.graph.DirectedGraph; - - - -/** - * This algorithm measures the importance of nodes based upon both the number and length of disjoint paths that lead - * to a given node from each of the nodes in the root set. Specifically the formula for measuring the importance of a - * node is given by: I(t|R) = sum_i=1_|P(r,t)|_{alpha^|p_i|} where alpha is the path decay coefficient, p_i is path i - * and P(r,t) is a set of maximum-sized node-disjoint paths from r to t. - *

- * This algorithm uses heuristic breadth-first search to try and find the maximum-sized set of node-disjoint paths - * between two nodes. As such, it is not guaranteed to give exact answers. - *

- * A simple example of usage is: - * 

- * WeightedNIPaths ranker = new WeightedNIPaths(someGraph,2.0,6,rootSet);
- * ranker.evaluate();
- * ranker.printRankings();
- *
- * - * @author Scott White - * @see "Algorithms for Estimating Relative Importance in Graphs by Scott White and Padhraic Smyth, 2003" - */ -public class WeightedNIPaths extends AbstractRanker { - public final static String WEIGHTED_NIPATHS_KEY = "jung.algorithms.importance.WEIGHTED_NIPATHS_KEY"; - private double mAlpha; - private int mMaxDepth; - private Set mPriors; - private Map pathIndices = new HashMap(); - private Map roots = new HashMap(); - private Map> pathsSeenMap = new HashMap>(); - private Factory vertexFactory; - private Factory edgeFactory; - - /** - * Constructs and initializes the algorithm. - * @param graph the graph whose nodes are being measured for their importance - * @param alpha the path decay coefficient (>= 1); 2 is recommended - * @param maxDepth the maximal depth to search out from the root set - * @param priors the root set (starting vertices) - */ - public WeightedNIPaths(DirectedGraph graph, Factory vertexFactory, - Factory edgeFactory, double alpha, int maxDepth, Set priors) { - super.initialize(graph, true,false); - this.vertexFactory = vertexFactory; - this.edgeFactory = edgeFactory; - mAlpha = alpha; - mMaxDepth = maxDepth; - mPriors = priors; - for (V v : graph.getVertices()) { - super.setVertexRankScore(v, 0.0); - } - } - - protected void incrementRankScore(V v, double rankValue) { - setVertexRankScore(v, getVertexRankScore(v) + rankValue); - } - - protected void computeWeightedPathsFromSource(V root, int depth) { - - int pathIdx = 1; - - for (E e : getGraph().getOutEdges(root)) { - this.pathIndices.put(e, pathIdx); - this.roots.put(e, root); - newVertexEncountered(pathIdx, getGraph().getEndpoints(e).getSecond(), root); - pathIdx++; - } - - List edges = new ArrayList(); - - V virtualNode = vertexFactory.create(); - getGraph().addVertex(virtualNode); - E virtualSinkEdge = edgeFactory.create(); - - getGraph().addEdge(virtualSinkEdge, virtualNode, root); - edges.add(virtualSinkEdge); - - int currentDepth = 0; - while (currentDepth <= depth) { - - double currentWeight = Math.pow(mAlpha, -1.0 * currentDepth); - for (E currentEdge : edges) { - incrementRankScore(getGraph().getEndpoints(currentEdge).getSecond(),// - currentWeight); - } - - if ((currentDepth == depth) || (edges.size() == 0)) break; - - List newEdges = new ArrayList(); - - for (E currentSourceEdge : edges) { //Iterator sourceEdgeIt = edges.iterator(); sourceEdgeIt.hasNext();) { - Number sourcePathIndex = this.pathIndices.get(currentSourceEdge); - - // from the currentSourceEdge, get its opposite end - // then iterate over the out edges of that opposite end - V newDestVertex = getGraph().getEndpoints(currentSourceEdge).getSecond(); - Collection outs = getGraph().getOutEdges(newDestVertex); - for (E currentDestEdge : outs) { - V destEdgeRoot = this.roots.get(currentDestEdge); - V destEdgeDest = getGraph().getEndpoints(currentDestEdge).getSecond(); - - if (currentSourceEdge == virtualSinkEdge) { - newEdges.add(currentDestEdge); - continue; - } - if (destEdgeRoot == root) { - continue; - } - if (destEdgeDest == getGraph().getEndpoints(currentSourceEdge).getFirst()) {//currentSourceEdge.getSource()) { - continue; - } - Set pathsSeen = this.pathsSeenMap.get(destEdgeDest); - - if (pathsSeen == null) { - newVertexEncountered(sourcePathIndex.intValue(), destEdgeDest, root); - } else if (roots.get(destEdgeDest) != root) { - roots.put(destEdgeDest,root); - pathsSeen.clear(); - pathsSeen.add(sourcePathIndex); - } else if (!pathsSeen.contains(sourcePathIndex)) { - pathsSeen.add(sourcePathIndex); - } else { - continue; - } - - this.pathIndices.put(currentDestEdge, sourcePathIndex); - this.roots.put(currentDestEdge, root); - newEdges.add(currentDestEdge); - } - } - - edges = newEdges; - currentDepth++; - } - - getGraph().removeVertex(virtualNode); - } - - private void newVertexEncountered(int sourcePathIndex, V dest, V root) { - Set pathsSeen = new HashSet(); - pathsSeen.add(sourcePathIndex); - this.pathsSeenMap.put(dest, pathsSeen); - roots.put(dest, root); - } - - @Override - public void step() { - for (V v : mPriors) { - computeWeightedPathsFromSource(v, mMaxDepth); - } - - normalizeRankings(); -// return 0; - } - - /** - * Given a node, returns the corresponding rank score. This implementation of getRankScore assumes - * the decoration representing the rank score is of type MutableDouble. - * @return the rank score for this node - */ - @Override - public String getRankScoreKey() { - return WEIGHTED_NIPATHS_KEY; - } - - @Override - protected void onFinalize(Object udc) { - pathIndices.remove(udc); - roots.remove(udc); - pathsSeenMap.remove(udc); - } -}