jcoverage | summary | package | file

Coverage details for edu.uci.ics.jung.algorithms.importance.WeightedNIPaths

LineHitsSource
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.HashSet;
14 import java.util.Iterator;
15 import java.util.List;
16 import java.util.Set;
17  
18 import edu.uci.ics.jung.graph.DirectedEdge;
19 import edu.uci.ics.jung.graph.DirectedGraph;
20 import edu.uci.ics.jung.graph.Edge;
21 import edu.uci.ics.jung.graph.Element;
22 import edu.uci.ics.jung.graph.Vertex;
23 import edu.uci.ics.jung.graph.impl.SparseVertex;
24 import edu.uci.ics.jung.utils.GraphUtils;
25 import edu.uci.ics.jung.utils.MutableDouble;
26 import edu.uci.ics.jung.utils.UserData;
27  
28  
29 /**
30  * This algorithm measures the importance of nodes based upon both the number and length of disjoint paths that lead
31  * to a given node from each of the nodes in the root set. Specifically the formula for measuring the importance of a
32  * 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
33  * and P(r,t) is a set of maximum-sized node-disjoint paths from r to t.
34  * <p>
35  * This algorithm uses heuristic breadth-first search to try and find the maximum-sized set of node-disjoint paths
36  * between two nodes. As such, it is not guaranteed to give exact answers.
37  * <p>
38  * A simple example of usage is:
39  * <pre>
40  * WeightedNIPaths ranker = new WeightedNIPaths(someGraph,2.0,6,rootSet);
41  * ranker.evaluate();
42  * ranker.printRankings();
43  * </pre>
44  *
45  * @author Scott White
46  * @see "Algorithms for Estimating Relative Importance in Graphs by Scott White and Padhraic Smyth, 2003"
47  */
48 public class WeightedNIPaths extends AbstractRanker {
49     public final static String WEIGHTED_NIPATHS_KEY = "jung.algorithms.importance.WEIGHTED_NIPATHS_KEY";
50     private double mAlpha;
51     private int mMaxDepth;
52     private Set mPriors;
53  
54     /**
55      * Constructs and initializes the algorithm.
56      * @param graph the graph whose nodes are being measured for their importance
57      * @param alpha the path decay coefficient (>= 1); 2 is recommended
58      * @param maxDepth the maximal depth to search out from the root set
59      * @param priors the root set (starting vertices)
60      */
611    public WeightedNIPaths(DirectedGraph graph, double alpha, int maxDepth, Set priors) {
621        super.initialize(graph, true,false);
631        mAlpha = alpha;
641        mMaxDepth = maxDepth;
651        mPriors = priors;
661        for (Iterator vIt = graph.getVertices().iterator(); vIt.hasNext();) {
675            Vertex currentVertex = (Vertex) vIt.next();
685            currentVertex.setUserDatum(WEIGHTED_NIPATHS_KEY, new MutableDouble(0), UserData.SHARED);
69         }
701    }
71  
72     /**
73      * Given a node, returns the corresponding rank score. This implementation of <code>getRankScore</code> assumes
74      * the decoration representing the rank score is of type <code>MutableDouble</code>.
75      * @return the rank score for this node
76      */
77     public String getRankScoreKey() {
7851        return WEIGHTED_NIPATHS_KEY;
79     }
80  
81     protected void incrementRankScore(Element v, double rankValue) {
8213        setRankScore(v, getRankScore(v) + rankValue);
8313    }
84  
85     protected void computeWeightedPathsFromSource(Vertex root, int depth) {
86  
871        int pathIdx = 1;
881        for (Iterator rootEdgeIt = root.getOutEdges().iterator(); rootEdgeIt.hasNext();) {
893            DirectedEdge currentEdge = (DirectedEdge) rootEdgeIt.next();
903            Integer pathIdxValue = new Integer(pathIdx);
913            currentEdge.setUserDatum(PATH_INDEX_KEY, pathIdxValue, UserData.REMOVE);
923            currentEdge.setUserDatum(ROOT_KEY, root, UserData.REMOVE);
933            newVertexEncountered(pathIdxValue, currentEdge.getDest(), root);
943            pathIdx++;
95         }
96  
971        List edges = new ArrayList();
98  
991        Vertex virtualNode = getGraph().addVertex(new SparseVertex());
1001        Edge virtualSinkEdge = GraphUtils.addEdge(getGraph(), virtualNode, root);
1011        edges.add(virtualSinkEdge);
102  
1031        int currentDepth = 0;
1044        while (currentDepth <= depth) {
105  
1064            double currentWeight = Math.pow(mAlpha, -1.0 * currentDepth);
107  
1084            for (Iterator it = edges.iterator(); it.hasNext();) {
10913                DirectedEdge currentEdge = (DirectedEdge) it.next();
11013                incrementRankScore(currentEdge.getDest(), currentWeight);
111             }
112  
1134            if ((currentDepth == depth) || (edges.size() == 0)) break;
114  
1153            List newEdges = new ArrayList();
116  
1173            for (Iterator sourceEdgeIt = edges.iterator(); sourceEdgeIt.hasNext();) {
11811                DirectedEdge currentSourceEdge = (DirectedEdge) sourceEdgeIt.next();
11911                Integer sourcePathIndex = (Integer) currentSourceEdge.getUserDatum(PATH_INDEX_KEY);
120  
12111                for (Iterator edgeIt = currentSourceEdge.getDest().getOutEdges().iterator(); edgeIt.hasNext();) {
12227                    DirectedEdge currentDestEdge = (DirectedEdge) edgeIt.next();
12327                    Vertex destEdgeRoot = (Vertex) currentDestEdge.getUserDatum(ROOT_KEY);
12427                    Vertex destEdgeDest = currentDestEdge.getDest();
125  
12627                    if (currentSourceEdge == virtualSinkEdge) {
1273                        newEdges.add(currentDestEdge);
1283                        continue;
129                     }
13024                    if (destEdgeRoot == root) {
13111                        continue;
132                     }
13313                    if (destEdgeDest == currentSourceEdge.getSource()) {
1343                        continue;
135                     }
136  
13710                    Set pathsSeen = (Set) destEdgeDest.getUserDatum(PATHS_SEEN_KEY);
138  
139                     /*
140                     Set pathsSeen = new HashSet();
141         pathsSeen.add(sourcePathIndex);
142         dest.setUserDatum(PATHS_SEEN_KEY, pathsSeen, UserData.REMOVE);
143         dest.setUserDatum(ROOT_KEY, root, UserData.REMOVE);
144         */
145  
14610                    if (pathsSeen == null) {
1472                        newVertexEncountered(sourcePathIndex, destEdgeDest, root);
1488                    } else if (destEdgeDest.getUserDatum(ROOT_KEY) != root) {
1490                        destEdgeDest.setUserDatum(ROOT_KEY, root, UserData.REMOVE);
1500                        pathsSeen.clear();
1510                        pathsSeen.add(sourcePathIndex);
1528                    } else if (!pathsSeen.contains(sourcePathIndex)) {
1537                        pathsSeen.add(sourcePathIndex);
154                     } else {
155                         continue;
156                     }
157  
1589                    currentDestEdge.setUserDatum(PATH_INDEX_KEY, sourcePathIndex, UserData.REMOVE);
1599                    currentDestEdge.setUserDatum(ROOT_KEY, root, UserData.REMOVE);
1609                    newEdges.add(currentDestEdge);
161                 }
162             }
163  
1643            edges = newEdges;
1653            currentDepth++;
166         }
167  
1681        getGraph().removeVertex(virtualNode);
1691    }
170  
171     private void newVertexEncountered(Integer sourcePathIndex, Vertex dest, Vertex root) {
1725        Set pathsSeen = new HashSet();
1735        pathsSeen.add(sourcePathIndex);
1745        dest.setUserDatum(PATHS_SEEN_KEY, pathsSeen, UserData.REMOVE);
1755        dest.setUserDatum(ROOT_KEY, root, UserData.REMOVE);
1765    }
177  
178     protected double evaluateIteration() {
1791        for (Iterator it = mPriors.iterator(); it.hasNext();) {
1801            computeWeightedPathsFromSource((Vertex) it.next(), mMaxDepth);
181         }
182  
1831        normalizeRankings();
1841        return 0;
185     }
186  
187     protected void onFinalize(Element udc) {
1885        udc.removeUserDatum(PATH_INDEX_KEY);
1895        udc.removeUserDatum(ROOT_KEY);
1905        udc.removeUserDatum(PATHS_SEEN_KEY);
1915    }
192  
193     private static final String PATH_INDEX_KEY = "WeightedNIPathsII.PathIndexKey";
194     private static final String ROOT_KEY = "WeightedNIPathsII.RootKey";
195     private static final String PATHS_SEEN_KEY = "WeightedNIPathsII.PathsSeenKey";
196 }

jcoverage | summary | package | file

this report was generated by version 1.0.5 of jcoverage.
visit www.jcoverage.com for updates.

copyright © 2003, jcoverage ltd. all rights reserved.
Java is a trademark of Sun Microsystems, Inc. in the United States and other countries.