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

Line | Hits | Source
--- | --- | ---
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 |  | `*/`
61 | 1 | `public WeightedNIPaths(DirectedGraph graph, double alpha, int maxDepth, Set priors) {`
62 | 1 | `super.initialize(graph, true,false);`
63 | 1 | `mAlpha = alpha;`
64 | 1 | `mMaxDepth = maxDepth;`
65 | 1 | `mPriors = priors;`
66 | 1 | `for (Iterator vIt = graph.getVertices().iterator(); vIt.hasNext();) {`
67 | 5 | `Vertex currentVertex = (Vertex) vIt.next();`
68 | 5 | `currentVertex.setUserDatum(WEIGHTED_NIPATHS_KEY, new MutableDouble(0), UserData.SHARED);`
69 |  | `}`
70 | 1 | `}`
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() {`
78 | 51 | `return WEIGHTED_NIPATHS_KEY;`
79 |  | `}`
80 |  | ``
81 |  | `protected void incrementRankScore(Element v, double rankValue) {`
82 | 13 | `setRankScore(v, getRankScore(v) + rankValue);`
83 | 13 | `}`
84 |  | ``
85 |  | `protected void computeWeightedPathsFromSource(Vertex root, int depth) {`
86 |  | ``
87 | 1 | `int pathIdx = 1;`
88 | 1 | `for (Iterator rootEdgeIt = root.getOutEdges().iterator(); rootEdgeIt.hasNext();) {`
89 | 3 | `DirectedEdge currentEdge = (DirectedEdge) rootEdgeIt.next();`
90 | 3 | `Integer pathIdxValue = new Integer(pathIdx);`
91 | 3 | `currentEdge.setUserDatum(PATH_INDEX_KEY, pathIdxValue, UserData.REMOVE);`
92 | 3 | `currentEdge.setUserDatum(ROOT_KEY, root, UserData.REMOVE);`
93 | 3 | `newVertexEncountered(pathIdxValue, currentEdge.getDest(), root);`
94 | 3 | `pathIdx++;`
95 |  | `}`
96 |  | ``
97 | 1 | `List edges = new ArrayList();`
98 |  | ``
99 | 1 | `Vertex virtualNode = getGraph().addVertex(new SparseVertex());`
100 | 1 | `Edge virtualSinkEdge = GraphUtils.addEdge(getGraph(), virtualNode, root);`
101 | 1 | `edges.add(virtualSinkEdge);`
102 |  | ``
103 | 1 | `int currentDepth = 0;`
104 | 4 | `while (currentDepth <= depth) {`
105 |  | ``
106 | 4 | `double currentWeight = Math.pow(mAlpha, -1.0 * currentDepth);`
107 |  | ``
108 | 4 | `for (Iterator it = edges.iterator(); it.hasNext();) {`
109 | 13 | `DirectedEdge currentEdge = (DirectedEdge) it.next();`
110 | 13 | `incrementRankScore(currentEdge.getDest(), currentWeight);`
111 |  | `}`
112 |  | ``
113 | 4 | `if ((currentDepth == depth) || (edges.size() == 0)) break;`
114 |  | ``
115 | 3 | `List newEdges = new ArrayList();`
116 |  | ``
117 | 3 | `for (Iterator sourceEdgeIt = edges.iterator(); sourceEdgeIt.hasNext();) {`
118 | 11 | `DirectedEdge currentSourceEdge = (DirectedEdge) sourceEdgeIt.next();`
119 | 11 | `Integer sourcePathIndex = (Integer) currentSourceEdge.getUserDatum(PATH_INDEX_KEY);`
120 |  | ``
121 | 11 | `for (Iterator edgeIt = currentSourceEdge.getDest().getOutEdges().iterator(); edgeIt.hasNext();) {`
122 | 27 | `DirectedEdge currentDestEdge = (DirectedEdge) edgeIt.next();`
123 | 27 | `Vertex destEdgeRoot = (Vertex) currentDestEdge.getUserDatum(ROOT_KEY);`
124 | 27 | `Vertex destEdgeDest = currentDestEdge.getDest();`
125 |  | ``
126 | 27 | `if (currentSourceEdge == virtualSinkEdge) {`
127 | 3 | `newEdges.add(currentDestEdge);`
128 | 3 | `continue;`
129 |  | `}`
130 | 24 | `if (destEdgeRoot == root) {`
131 | 11 | `continue;`
132 |  | `}`
133 | 13 | `if (destEdgeDest == currentSourceEdge.getSource()) {`
134 | 3 | `continue;`
135 |  | `}`
136 |  | ``
137 | 10 | `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 |  | ``
146 | 10 | `if (pathsSeen == null) {`
147 | 2 | `newVertexEncountered(sourcePathIndex, destEdgeDest, root);`
148 | 8 | `} else if (destEdgeDest.getUserDatum(ROOT_KEY) != root) {`
149 | 0 | `destEdgeDest.setUserDatum(ROOT_KEY, root, UserData.REMOVE);`
150 | 0 | `pathsSeen.clear();`
151 | 0 | `pathsSeen.add(sourcePathIndex);`
152 | 8 | `} else if (!pathsSeen.contains(sourcePathIndex)) {`
153 | 7 | `pathsSeen.add(sourcePathIndex);`
154 |  | `} else {`
155 |  | `continue;`
156 |  | `}`
157 |  | ``
158 | 9 | `currentDestEdge.setUserDatum(PATH_INDEX_KEY, sourcePathIndex, UserData.REMOVE);`
159 | 9 | `currentDestEdge.setUserDatum(ROOT_KEY, root, UserData.REMOVE);`
160 | 9 | `newEdges.add(currentDestEdge);`
161 |  | `}`
162 |  | `}`
163 |  | ``
164 | 3 | `edges = newEdges;`
165 | 3 | `currentDepth++;`
166 |  | `}`
167 |  | ``
168 | 1 | `getGraph().removeVertex(virtualNode);`
169 | 1 | `}`
170 |  | ``
171 |  | `private void newVertexEncountered(Integer sourcePathIndex, Vertex dest, Vertex root) {`
172 | 5 | `Set pathsSeen = new HashSet();`
173 | 5 | `pathsSeen.add(sourcePathIndex);`
174 | 5 | `dest.setUserDatum(PATHS_SEEN_KEY, pathsSeen, UserData.REMOVE);`
175 | 5 | `dest.setUserDatum(ROOT_KEY, root, UserData.REMOVE);`
176 | 5 | `}`
177 |  | ``
178 |  | `protected double evaluateIteration() {`
179 | 1 | `for (Iterator it = mPriors.iterator(); it.hasNext();) {`
180 | 1 | `computeWeightedPathsFromSource((Vertex) it.next(), mMaxDepth);`
181 |  | `}`
182 |  | ``
183 | 1 | `normalizeRankings();`
184 | 1 | `return 0;`
185 |  | `}`
186 |  | ``
187 |  | `protected void onFinalize(Element udc) {`
188 | 5 | `udc.removeUserDatum(PATH_INDEX_KEY);`
189 | 5 | `udc.removeUserDatum(ROOT_KEY);`
190 | 5 | `udc.removeUserDatum(PATHS_SEEN_KEY);`
191 | 5 | `}`
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 |  | `}`

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.