--- /dev/null
+/*
+* 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.
+ * <p>
+ * 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.
+ * <p>
+ * A simple example of usage is:
+ * <pre>
+ * WeightedNIPaths ranker = new WeightedNIPaths(someGraph,2.0,6,rootSet);
+ * ranker.evaluate();
+ * ranker.printRankings();
+ * </pre>
+ *
+ * @author Scott White
+ * @see "Algorithms for Estimating Relative Importance in Graphs by Scott White and Padhraic Smyth, 2003"
+ */
+public class WeightedNIPaths<V,E> extends AbstractRanker<V,E> {
+ public final static String WEIGHTED_NIPATHS_KEY = "jung.algorithms.importance.WEIGHTED_NIPATHS_KEY";
+ private double mAlpha;
+ private int mMaxDepth;
+ private Set<V> mPriors;
+ private Map<E,Number> pathIndices = new HashMap<E,Number>();
+ private Map<Object,V> roots = new HashMap<Object,V>();
+ private Map<V,Set<Number>> pathsSeenMap = new HashMap<V,Set<Number>>();
+ private Factory<V> vertexFactory;
+ private Factory<E> 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<V,E> graph, Factory<V> vertexFactory,
+ Factory<E> edgeFactory, double alpha, int maxDepth, Set<V> 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<E> edges = new ArrayList<E>();
+
+ 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<E> newEdges = new ArrayList<E>();
+
+ 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<E> 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<Number> 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<Number> pathsSeen = new HashSet<Number>();
+ 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 <code>getRankScore</code> assumes
+ * the decoration representing the rank score is of type <code>MutableDouble</code>.
+ * @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);
+ }
+}
Code Review / controller.git / blobdiff