2 * Copyright (c) 2003, the JUNG Project and the Regents of the University
6 * This software is open-source under the BSD license; see either
8 * http://jung.sourceforge.net/license.txt for a description.
10 package edu.uci.ics.jung.algorithms.importance;
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;
20 import org.apache.commons.collections15.Factory;
22 import edu.uci.ics.jung.graph.DirectedGraph;
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.
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.
35 * A simple example of usage is:
37 * WeightedNIPaths ranker = new WeightedNIPaths(someGraph,2.0,6,rootSet);
39 * ranker.printRankings();
43 * @see "Algorithms for Estimating Relative Importance in Graphs by Scott White and Padhraic Smyth, 2003"
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;
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)
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;
71 for (V v : graph.getVertices()) {
72 super.setVertexRankScore(v, 0.0);
76 protected void incrementRankScore(V v, double rankValue) {
77 setVertexRankScore(v, getVertexRankScore(v) + rankValue);
80 protected void computeWeightedPathsFromSource(V root, int depth) {
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);
91 List<E> edges = new ArrayList<E>();
93 V virtualNode = vertexFactory.create();
94 getGraph().addVertex(virtualNode);
95 E virtualSinkEdge = edgeFactory.create();
97 getGraph().addEdge(virtualSinkEdge, virtualNode, root);
98 edges.add(virtualSinkEdge);
100 int currentDepth = 0;
101 while (currentDepth <= depth) {
103 double currentWeight = Math.pow(mAlpha, -1.0 * currentDepth);
104 for (E currentEdge : edges) {
105 incrementRankScore(getGraph().getEndpoints(currentEdge).getSecond(),//
109 if ((currentDepth == depth) || (edges.size() == 0)) break;
111 List<E> newEdges = new ArrayList<E>();
113 for (E currentSourceEdge : edges) { //Iterator sourceEdgeIt = edges.iterator(); sourceEdgeIt.hasNext();) {
114 Number sourcePathIndex = this.pathIndices.get(currentSourceEdge);
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();
124 if (currentSourceEdge == virtualSinkEdge) {
125 newEdges.add(currentDestEdge);
128 if (destEdgeRoot == root) {
131 if (destEdgeDest == getGraph().getEndpoints(currentSourceEdge).getFirst()) {//currentSourceEdge.getSource()) {
134 Set<Number> pathsSeen = this.pathsSeenMap.get(destEdgeDest);
136 if (pathsSeen == null) {
137 newVertexEncountered(sourcePathIndex.intValue(), destEdgeDest, root);
138 } else if (roots.get(destEdgeDest) != root) {
139 roots.put(destEdgeDest,root);
141 pathsSeen.add(sourcePathIndex);
142 } else if (!pathsSeen.contains(sourcePathIndex)) {
143 pathsSeen.add(sourcePathIndex);
148 this.pathIndices.put(currentDestEdge, sourcePathIndex);
149 this.roots.put(currentDestEdge, root);
150 newEdges.add(currentDestEdge);
158 getGraph().removeVertex(virtualNode);
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);
170 for (V v : mPriors) {
171 computeWeightedPathsFromSource(v, mMaxDepth);
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
184 public String getRankScoreKey() {
185 return WEIGHTED_NIPATHS_KEY;
189 protected void onFinalize(Object udc) {
190 pathIndices.remove(udc);
192 pathsSeenMap.remove(udc);