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

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.Iterator;`
14 |  | `import java.util.List;`
15 |  | `import java.util.Set;`
16 |  | `import java.util.Stack;`
17 |  | ``
18 |  | `import org.apache.commons.collections.Buffer;`
19 |  | `import org.apache.commons.collections.buffer.UnboundedFifoBuffer;`
20 |  | ``
21 |  | `import edu.uci.ics.jung.graph.Edge;`
22 |  | `import edu.uci.ics.jung.graph.Element;`
23 |  | `import edu.uci.ics.jung.graph.Graph;`
24 |  | `import edu.uci.ics.jung.graph.Vertex;`
25 |  | `import edu.uci.ics.jung.graph.decorators.Decorator;`
26 |  | `import edu.uci.ics.jung.graph.decorators.NumericDecorator;`
27 |  | `import edu.uci.ics.jung.utils.MutableDouble;`
28 |  | `import edu.uci.ics.jung.utils.PredicateUtils;`
29 |  | `import edu.uci.ics.jung.utils.UserData;`
30 |  | `import edu.uci.ics.jung.utils.UserDataUtils;`
31 |  | ``
32 |  | `/**`
33 |  | `* Computes betweenness centrality for each vertex and edge in the graph. The result is that each vertex`
34 |  | `* and edge has a UserData element of type MutableDouble whose key is 'centrality.BetweennessCentrality'.`
35 |  | `* Note: Many social network researchers like to normalize the betweenness values by dividing the values by`
36 |  | `* (n-1)(n-2)/2. The values given here are unnormalized.<p>`
37 |  | `*`
38 |  | `* A simple example of usage is:`
39 |  | `* <pre>`
40 |  | `* BetweennessCentrality ranker = new BetweennessCentrality(someGraph);`
41 |  | `* ranker.evaluate();`
42 |  | `* ranker.printRankings();`
43 |  | `* </pre>`
44 |  | `*`
45 |  | `* Running time is: O(n^2 + nm).`
46 |  | `* @see "Ulrik Brandes: A Faster Algorithm for Betweenness Centrality. Journal of Mathematical Sociology 25(2):163-177, 2001."`
47 |  | `* @author Scott White`
48 |  | `*/`
49 |  | ``
50 |  | `public class BetweennessCentrality extends AbstractRanker {`
51 |  | ``
52 |  | `public static final String CENTRALITY = "centrality.BetweennessCentrality";`
53 |  | ``
54 |  | `/**`
55 |  | `* Constructor which initializes the algorithm`
56 |  | `* @param g the graph whose nodes are to be analyzed`
57 |  | `*/`
58 | 2 | `public BetweennessCentrality(Graph g) {`
59 | 2 | `initialize(g, true, true);`
60 | 2 | `}`
61 |  | ``
62 | 5 | `public BetweennessCentrality(Graph g, boolean rankNodes) {`
63 | 5 | `initialize(g, rankNodes, true);`
64 | 5 | `}`
65 |  | ``
66 |  | `public BetweennessCentrality(Graph g, boolean rankNodes, boolean rankEdges)`
67 | 0 | `{`
68 | 0 | `initialize(g, rankNodes, rankEdges);`
69 | 0 | `}`
70 |  | ``
71 |  | `protected void computeBetweenness(Graph graph) {`
72 |  | ``
73 | 7 | `BetweennessDataDecorator decorator = new BetweennessDataDecorator();`
74 | 7 | `NumericDecorator bcDecorator = new NumericDecorator(CENTRALITY, UserData.SHARED);`
75 |  | ``
76 |  | ``
77 | 7 | `Set vertices = graph.getVertices();`
78 |  | ``
79 |  | `// clean up previous decorations, if any; otherwise the new calculations will`
80 |  | `// incorporate the old data`
81 | 7 | `UserDataUtils.cleanup(vertices, getRankScoreKey());`
82 | 7 | `UserDataUtils.cleanup(graph.getEdges(), getRankScoreKey());`
83 |  | ``
84 | 7 | `for (Iterator vIt = vertices.iterator(); vIt.hasNext();) {`
85 | 62 | `Vertex s = (Vertex) vIt.next();`
86 |  | ``
87 | 62 | `initializeData(graph,decorator);`
88 |  | ``
89 | 62 | `decorator.data(s).numSPs = 1;`
90 | 62 | `decorator.data(s).distance = 0;`
91 |  | ``
92 | 62 | `Stack stack = new Stack();`
93 | 62 | `Buffer queue = new UnboundedFifoBuffer();`
94 | 62 | `queue.add(s);`
95 |  | ``
96 | 420 | `while (!queue.isEmpty()) {`
97 | 358 | `Vertex v = (Vertex) queue.remove();`
98 | 358 | `stack.push(v);`
99 |  | ``
100 | 358 | `for (Iterator nIt = v.getSuccessors().iterator(); nIt.hasNext();) {`
101 | 780 | `Vertex w = (Vertex) nIt.next();`
102 |  | ``
103 | 780 | `if (decorator.data(w).distance < 0) {`
104 | 296 | `queue.add(w);`
105 | 296 | `decorator.data(w).distance = decorator.data(v).distance + 1;`
106 |  | `}`
107 |  | ``
108 | 780 | `if (decorator.data(w).distance == decorator.data(v).distance + 1) {`
109 | 327 | `decorator.data(w).numSPs += decorator.data(v).numSPs;`
110 | 327 | `decorator.data(w).predecessors.add(v);`
111 |  | `}`
112 |  | `}`
113 |  | `}`
114 |  | ``
115 | 420 | `while (!stack.isEmpty()) {`
116 | 358 | `Vertex w = (Vertex) stack.pop();`
117 |  | ``
118 | 358 | `for (Iterator v2It = decorator.data(w).predecessors.iterator(); v2It.hasNext();) {`
119 | 327 | `Vertex v = (Vertex) v2It.next();`
120 | 327 | `double partialDependency = (decorator.data(v).numSPs / decorator.data(w).numSPs);`
121 | 327 | `partialDependency *= (1.0 + decorator.data(w).dependency);`
122 | 327 | `decorator.data(v).dependency += partialDependency;`
123 | 327 | `Edge currentEdge = v.findEdge(w);`
124 | 327 | `MutableDouble edgeValue = (MutableDouble) bcDecorator.getValue(currentEdge);`
125 | 327 | `edgeValue.add(partialDependency);`
126 |  | `}`
127 | 358 | `if (w != s) {`
128 | 296 | `MutableDouble bcValue = (MutableDouble) bcDecorator.getValue(w);`
129 | 296 | `bcValue.add(decorator.data(w).dependency);`
130 |  | `}`
131 |  | `}`
132 |  | `}`
133 |  | ``
134 | 7 | `if (PredicateUtils.enforcesEdgeConstraint(graph, Graph.UNDIRECTED_EDGE)) {`
135 | 3 | `for (Iterator v3It = vertices.iterator(); v3It.hasNext();) {`
136 | 27 | `MutableDouble bcValue = (MutableDouble) bcDecorator.getValue((Vertex) v3It.next());`
137 | 27 | `bcValue.setDoubleValue(bcValue.doubleValue() / 2.0);`
138 |  | `}`
139 | 3 | `for (Iterator eIt = graph.getEdges().iterator(); eIt.hasNext();) {`
140 | 23 | `MutableDouble bcValue = (MutableDouble) bcDecorator.getValue((Edge) eIt.next());`
141 | 23 | `bcValue.setDoubleValue(bcValue.doubleValue() / 2.0);`
142 |  | `}`
143 |  | `}`
144 |  | ``
145 | 7 | `for (Iterator vIt = vertices.iterator(); vIt.hasNext();) {`
146 | 62 | `Vertex vertex = (Vertex) vIt.next();`
147 | 62 | `decorator.removeValue(vertex);`
148 |  | `}`
149 |  | ``
150 | 7 | `}`
151 |  | ``
152 |  | `private void initializeData(Graph g, BetweennessDataDecorator decorator) {`
153 | 62 | `for (Iterator vIt = g.getVertices().iterator(); vIt.hasNext();) {`
154 | 568 | `Vertex vertex = (Vertex) vIt.next();`
155 |  | ``
156 | 568 | `if (vertex.getUserDatum(CENTRALITY) == null) {`
157 | 62 | `vertex.addUserDatum(CENTRALITY, new MutableDouble(), UserData.SHARED);`
158 |  | `}`
159 |  | ``
160 | 568 | `decorator.setData(new BetweennessData(), vertex);`
161 |  | `}`
162 | 62 | `for (Iterator eIt = g.getEdges().iterator(); eIt.hasNext();) {`
163 | 557 | `Edge e = (Edge) eIt.next();`
164 |  | ``
165 | 557 | `if (e.getUserDatum(CENTRALITY) == null) {`
166 | 60 | `e.addUserDatum(CENTRALITY, new MutableDouble(), UserData.SHARED);`
167 |  | `}`
168 |  | `}`
169 | 62 | `}`
170 |  | ``
171 |  | `/**`
172 |  | `* the user datum key used to store the rank scores`
173 |  | `* @return the key`
174 |  | `*/`
175 |  | `public String getRankScoreKey() {`
176 | 167 | `return CENTRALITY;`
177 |  | `}`
178 |  | ``
179 |  | `protected double evaluateIteration() {`
180 | 7 | `computeBetweenness(getGraph());`
181 | 7 | `return 0;`
182 |  | `}`
183 |  | ``
184 |  | `class BetweennessDataDecorator extends Decorator {`
185 |  | `public BetweennessDataDecorator() {`
186 |  | `super("centrality.BetwennessData", UserData.REMOVE);`
187 |  | `}`
188 |  | ``
189 |  | `public BetweennessData data(Element udc) {`
190 |  | `return (BetweennessData) udc.getUserDatum(getKey());`
191 |  | `}`
192 |  | ``
193 |  | `public void setData(BetweennessData value, Element udc) {`
194 |  | `udc.setUserDatum(getKey(), value, getCopyAction());`
195 |  | `}`
196 |  | ``
197 |  | `}`
198 |  | ``
199 |  | `class BetweennessData {`
200 |  | `double distance;`
201 |  | `double numSPs;`
202 |  | `List predecessors;`
203 |  | `double dependency;`
204 |  | ``
205 |  | `BetweennessData() {`
206 |  | `distance = -1;`
207 |  | `numSPs = 0;`
208 |  | `predecessors = new ArrayList();`
209 |  | `dependency = 0;`
210 |  | `}`
211 |  | `}`
212 |  | `}`

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.