third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/importance/WeightedNIPaths.java

   1 /*
   2 * Copyright (c) 2003, the JUNG Project and the Regents of the University
   3 * of California
   4 * All rights reserved.
   5 *
   6 * This software is open-source under the BSD license; see either
   7 * "license.txt" or
   8 * http://jung.sourceforge.net/license.txt for a description.
   9 */
  10 package edu.uci.ics.jung.algorithms.importance;
  11
  12 import java.util.ArrayList;
  13 import java.util.Collection;
  14 import java.util.HashMap;
  15 import java.util.HashSet;
  16 import java.util.List;
  17 import java.util.Map;
  18 import java.util.Set;
  19
  20 import org.apache.commons.collections15.Factory;
  21
  22 import edu.uci.ics.jung.graph.DirectedGraph;
  23
  24
  25
  26 /**
  27  * This algorithm measures the importance of nodes based upon both the number and length of disjoint paths that lead
  28  * to a given node from each of the nodes in the root set. Specifically the formula for measuring the importance of a
  29  * 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
  30  * and P(r,t) is a set of maximum-sized node-disjoint paths from r to t.
  31  * <p>
  32  * This algorithm uses heuristic breadth-first search to try and find the maximum-sized set of node-disjoint paths
  33  * between two nodes. As such, it is not guaranteed to give exact answers.
  34  * <p>
  35  * A simple example of usage is:
  36  * <pre>
  37  * WeightedNIPaths ranker = new WeightedNIPaths(someGraph,2.0,6,rootSet);
  38  * ranker.evaluate();
  39  * ranker.printRankings();
  40  * </pre>
  41  *
  42  * @author Scott White
  43  * @see "Algorithms for Estimating Relative Importance in Graphs by Scott White and Padhraic Smyth, 2003"
  44  */
  45 public class WeightedNIPaths<V,E> extends AbstractRanker<V,E> {
  46     public final static String WEIGHTED_NIPATHS_KEY = "jung.algorithms.importance.WEIGHTED_NIPATHS_KEY";
  47     private double mAlpha;
  48     private int mMaxDepth;
  49     private Set<V> mPriors;
  50     private Map<E,Number> pathIndices = new HashMap<E,Number>();
  51     private Map<Object,V> roots = new HashMap<Object,V>();
  52     private Map<V,Set<Number>> pathsSeenMap = new HashMap<V,Set<Number>>();
  53     private Factory<V> vertexFactory;
  54     private Factory<E> edgeFactory;
  55
  56     /**
  57      * Constructs and initializes the algorithm.
  58      * @param graph the graph whose nodes are being measured for their importance
  59      * @param alpha the path decay coefficient (>= 1); 2 is recommended
  60      * @param maxDepth the maximal depth to search out from the root set
  61      * @param priors the root set (starting vertices)
  62      */
  63     public WeightedNIPaths(DirectedGraph<V,E> graph, Factory<V> vertexFactory,
  64                 Factory<E> edgeFactory, double alpha, int maxDepth, Set<V> priors) {
  65         super.initialize(graph, true,false);
  66         this.vertexFactory = vertexFactory;
  67         this.edgeFactory = edgeFactory;
  68         mAlpha = alpha;
  69         mMaxDepth = maxDepth;
  70         mPriors = priors;
  71         for (V v : graph.getVertices()) {
  72                 super.setVertexRankScore(v, 0.0);
  73         }
  74     }
  75
  76     protected void incrementRankScore(V v, double rankValue) {
  77         setVertexRankScore(v, getVertexRankScore(v) + rankValue);
  78     }
  79
  80     protected void computeWeightedPathsFromSource(V root, int depth) {
  81
  82         int pathIdx = 1;
  83
  84         for (E e : getGraph().getOutEdges(root)) {
  85             this.pathIndices.put(e, pathIdx);
  86             this.roots.put(e, root);
  87             newVertexEncountered(pathIdx, getGraph().getEndpoints(e).getSecond(), root);
  88             pathIdx++;
  89         }
  90
  91         List<E> edges = new ArrayList<E>();
  92
  93         V virtualNode = vertexFactory.create();
  94         getGraph().addVertex(virtualNode);
  95         E virtualSinkEdge = edgeFactory.create();
  96
  97         getGraph().addEdge(virtualSinkEdge, virtualNode, root);
  98         edges.add(virtualSinkEdge);
  99
 100         int currentDepth = 0;
 101         while (currentDepth <= depth) {
 102
 103             double currentWeight = Math.pow(mAlpha, -1.0 * currentDepth);
 104             for (E currentEdge : edges) {
 105                 incrementRankScore(getGraph().getEndpoints(currentEdge).getSecond(),//
 106                                 currentWeight);
 107             }
 108
 109             if ((currentDepth == depth) || (edges.size() == 0)) break;
 110
 111             List<E> newEdges = new ArrayList<E>();
 112
 113             for (E currentSourceEdge : edges) { //Iterator sourceEdgeIt = edges.iterator(); sourceEdgeIt.hasNext();) {
 114                 Number sourcePathIndex = this.pathIndices.get(currentSourceEdge);
 115
 116                 // from the currentSourceEdge, get its opposite end
 117                 // then iterate over the out edges of that opposite end
 118                 V newDestVertex = getGraph().getEndpoints(currentSourceEdge).getSecond();
 119                 Collection<E> outs = getGraph().getOutEdges(newDestVertex);
 120                 for (E currentDestEdge : outs) {
 121                         V destEdgeRoot = this.roots.get(currentDestEdge);
 122                         V destEdgeDest = getGraph().getEndpoints(currentDestEdge).getSecond();
 123
 124                     if (currentSourceEdge == virtualSinkEdge) {
 125                         newEdges.add(currentDestEdge);
 126                         continue;
 127                     }
 128                     if (destEdgeRoot == root) {
 129                         continue;
 130                     }
 131                     if (destEdgeDest == getGraph().getEndpoints(currentSourceEdge).getFirst()) {//currentSourceEdge.getSource()) {
 132                         continue;
 133                     }
 134                     Set<Number> pathsSeen = this.pathsSeenMap.get(destEdgeDest);
 135
 136                     if (pathsSeen == null) {
 137                         newVertexEncountered(sourcePathIndex.intValue(), destEdgeDest, root);
 138                     } else if (roots.get(destEdgeDest) != root) {
 139                         roots.put(destEdgeDest,root);
 140                         pathsSeen.clear();
 141                         pathsSeen.add(sourcePathIndex);
 142                     } else if (!pathsSeen.contains(sourcePathIndex)) {
 143                         pathsSeen.add(sourcePathIndex);
 144                     } else {
 145                         continue;
 146                     }
 147
 148                     this.pathIndices.put(currentDestEdge, sourcePathIndex);
 149                     this.roots.put(currentDestEdge, root);
 150                     newEdges.add(currentDestEdge);
 151                 }
 152             }
 153
 154             edges = newEdges;
 155             currentDepth++;
 156         }
 157
 158         getGraph().removeVertex(virtualNode);
 159     }
 160
 161     private void newVertexEncountered(int sourcePathIndex, V dest, V root) {
 162         Set<Number> pathsSeen = new HashSet<Number>();
 163         pathsSeen.add(sourcePathIndex);
 164         this.pathsSeenMap.put(dest, pathsSeen);
 165         roots.put(dest, root);
 166     }
 167
 168     @Override
 169     public void step() {
 170         for (V v : mPriors) {
 171             computeWeightedPathsFromSource(v, mMaxDepth);
 172         }
 173
 174         normalizeRankings();
 175 //        return 0;
 176     }
 177
 178     /**
 179      * Given a node, returns the corresponding rank score. This implementation of <code>getRankScore</code> assumes
 180      * the decoration representing the rank score is of type <code>MutableDouble</code>.
 181      * @return  the rank score for this node
 182      */
 183     @Override
 184     public String getRankScoreKey() {
 185         return WEIGHTED_NIPATHS_KEY;
 186     }
 187
 188     @Override
 189     protected void onFinalize(Object udc) {
 190         pathIndices.remove(udc);
 191         roots.remove(udc);
 192         pathsSeenMap.remove(udc);
 193     }
 194 }