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

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.Iterator;`
13 |  | ``
14 |  | `import cern.colt.matrix.DoubleMatrix2D;`
15 |  | `import edu.uci.ics.jung.algorithms.GraphMatrixOperations;`
16 |  | `import edu.uci.ics.jung.graph.UndirectedGraph;`
17 |  | `import edu.uci.ics.jung.graph.Vertex;`
18 |  | `import edu.uci.ics.jung.graph.decorators.Indexer;`
19 |  | ``
20 |  | `/**`
21 |  | `* /**`
22 |  | `* Computes s-t betweenness centrality for each vertex in the graph. The betweenness values in this case`
23 |  | `* are based on random walks, measuring the expected number of times a node is traversed by a random walk`
24 |  | `* from s to t. The result is that each vertex has a UserData element of type`
25 |  | `* MutableDouble whose key is 'centrality.RandomWalkBetweennessCentrality'`
26 |  | `*`
27 |  | `* A simple example of usage is: <br>`
28 |  | `* RandomWalkSTBetweenness ranker = new RandomWalkBetweenness(someGraph,someSource,someTarget); <br>`
29 |  | `* ranker.evaluate(); <br>`
30 |  | `* ranker.printRankings(); <p>`
31 |  | `*`
32 |  | `* Running time is: O(n^3).`
33 |  | `* @see "Mark Newman: A measure of betweenness centrality based on random walks, 2002."`
34 |  | ``
35 |  | `* @author Scott White`
36 |  | `*/`
37 |  | `public class RandomWalkSTBetweenness extends AbstractRanker {`
38 |  | ``
39 |  | `public static final String CENTRALITY = "centrality.RandomWalkSTBetweennessCentrality";`
40 |  | `private DoubleMatrix2D mVoltageMatrix;`
41 |  | `private Indexer mIndexer;`
42 |  | `Vertex mSource;`
43 |  | `Vertex mTarget;`
44 |  | ``
45 |  | `/**`
46 |  | `* Constructor which initializes the algorithm`
47 |  | `* @param g the graph whose nodes are to be analyzed`
48 |  | `* @param s the source vertex`
49 |  | `* @param t the target vertex`
50 |  | `*/`
51 | 1 | `public RandomWalkSTBetweenness(UndirectedGraph g, Vertex s, Vertex t) {`
52 | 1 | `initialize(g, true, false);`
53 | 1 | `mSource = s;`
54 | 1 | `mTarget = t;`
55 | 1 | `}`
56 |  | ``
57 |  | `protected Indexer getIndexer() {`
58 | 1210 | `return mIndexer;`
59 |  | `}`
60 |  | ``
61 |  | `protected DoubleMatrix2D getVoltageMatrix() {`
62 | 0 | `return mVoltageMatrix;`
63 |  | `}`
64 |  | ``
65 |  | `protected void setUp() {`
66 | 1 | `mVoltageMatrix = GraphMatrixOperations.computeVoltagePotentialMatrix((UndirectedGraph) getGraph());`
67 | 1 | `mIndexer = Indexer.getIndexer(getGraph());`
68 | 1 | `}`
69 |  | ``
70 |  | `protected void computeBetweenness() {`
71 | 0 | `setUp();`
72 |  | ``
73 | 0 | `for (Iterator iIt = getGraph().getVertices().iterator();iIt.hasNext();) {`
74 | 0 | `Vertex ithVertex = (Vertex) iIt.next();`
75 |  | ``
76 | 0 | `setRankScore(ithVertex,computeSTBetweenness(ithVertex,mSource, mTarget));`
77 |  | `}`
78 | 0 | `}`
79 |  | ``
80 |  | `public double computeSTBetweenness(Vertex ithVertex, Vertex source, Vertex target) {`
81 | 605 | `if (ithVertex == source || ithVertex == target) return 1;`
82 | 495 | `if (mVoltageMatrix == null) {`
83 | 0 | `setUp();`
84 |  | `}`
85 | 495 | `int i = mIndexer.getIndex(ithVertex);`
86 | 495 | `int s = mIndexer.getIndex(source);`
87 | 495 | `int t = mIndexer.getIndex(target);`
88 |  | ``
89 | 495 | `double betweenness = 0;`
90 | 495 | `for (Iterator vIt = ithVertex.getSuccessors().iterator();vIt.hasNext();) {`
91 | 2070 | `Vertex jthVertex = (Vertex) vIt.next();`
92 | 2070 | `int j = mIndexer.getIndex(jthVertex);`
93 | 2070 | `double currentFlow = 0;`
94 | 2070 | `currentFlow += mVoltageMatrix.get(i,s);`
95 | 2070 | `currentFlow -= mVoltageMatrix.get(i,t);`
96 | 2070 | `currentFlow -= mVoltageMatrix.get(j,s);`
97 | 2070 | `currentFlow += mVoltageMatrix.get(j,t);`
98 | 2070 | `betweenness += Math.abs(currentFlow);`
99 |  | `}`
100 |  | ``
101 | 495 | `return betweenness/2.0;`
102 |  | ``
103 |  | `}`
104 |  | ``
105 |  | `/**`
106 |  | `* the user datum key used to store the rank scores`
107 |  | `* @return the key`
108 |  | `*/`
109 |  | `public String getRankScoreKey() {`
110 | 0 | `return CENTRALITY;`
111 |  | `}`
112 |  | ``
113 |  | `protected double evaluateIteration() {`
114 | 0 | `computeBetweenness();`
115 | 0 | `return 0;`
116 |  | `}`
117 |  | `}`

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.