--- /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.List;
+import java.util.Map;
+import java.util.Stack;
+
+import org.apache.commons.collections15.Buffer;
+import org.apache.commons.collections15.buffer.UnboundedFifoBuffer;
+
+import edu.uci.ics.jung.graph.Graph;
+import edu.uci.ics.jung.graph.UndirectedGraph;
+
+/**
+ * Computes betweenness centrality for each vertex and edge in the graph. The result is that each vertex
+ * and edge has a UserData element of type MutableDouble whose key is 'centrality.BetweennessCentrality'.
+ * Note: Many social network researchers like to normalize the betweenness values by dividing the values by
+ * (n-1)(n-2)/2. The values given here are unnormalized.<p>
+ *
+ * A simple example of usage is:
+ * <pre>
+ * BetweennessCentrality ranker = new BetweennessCentrality(someGraph);
+ * ranker.evaluate();
+ * ranker.printRankings();
+ * </pre>
+ *
+ * Running time is: O(n^2 + nm).
+ * @see "Ulrik Brandes: A Faster Algorithm for Betweenness Centrality. Journal of Mathematical Sociology 25(2):163-177, 2001."
+ * @author Scott White
+ * @author Tom Nelson converted to jung2
+ */
+
+public class BetweennessCentrality<V,E> extends AbstractRanker<V,E> {
+
+ public static final String CENTRALITY = "centrality.BetweennessCentrality";
+
+ /**
+ * Constructor which initializes the algorithm
+ * @param g the graph whose nodes are to be analyzed
+ */
+ public BetweennessCentrality(Graph<V,E> g) {
+ initialize(g, true, true);
+ }
+
+ public BetweennessCentrality(Graph<V,E> g, boolean rankNodes) {
+ initialize(g, rankNodes, true);
+ }
+
+ public BetweennessCentrality(Graph<V,E> g, boolean rankNodes, boolean rankEdges)
+ {
+ initialize(g, rankNodes, rankEdges);
+ }
+
+ protected void computeBetweenness(Graph<V,E> graph) {
+
+ Map<V,BetweennessData> decorator = new HashMap<V,BetweennessData>();
+ Map<V,Number> bcVertexDecorator =
+ vertexRankScores.get(getRankScoreKey());
+ bcVertexDecorator.clear();
+ Map<E,Number> bcEdgeDecorator =
+ edgeRankScores.get(getRankScoreKey());
+ bcEdgeDecorator.clear();
+
+ Collection<V> vertices = graph.getVertices();
+
+ for (V s : vertices) {
+
+ initializeData(graph,decorator);
+
+ decorator.get(s).numSPs = 1;
+ decorator.get(s).distance = 0;
+
+ Stack<V> stack = new Stack<V>();
+ Buffer<V> queue = new UnboundedFifoBuffer<V>();
+ queue.add(s);
+
+ while (!queue.isEmpty()) {
+ V v = queue.remove();
+ stack.push(v);
+
+ for(V w : getGraph().getSuccessors(v)) {
+
+ if (decorator.get(w).distance < 0) {
+ queue.add(w);
+ decorator.get(w).distance = decorator.get(v).distance + 1;
+ }
+
+ if (decorator.get(w).distance == decorator.get(v).distance + 1) {
+ decorator.get(w).numSPs += decorator.get(v).numSPs;
+ decorator.get(w).predecessors.add(v);
+ }
+ }
+ }
+
+ while (!stack.isEmpty()) {
+ V w = stack.pop();
+
+ for (V v : decorator.get(w).predecessors) {
+
+ double partialDependency = (decorator.get(v).numSPs / decorator.get(w).numSPs);
+ partialDependency *= (1.0 + decorator.get(w).dependency);
+ decorator.get(v).dependency += partialDependency;
+ E currentEdge = getGraph().findEdge(v, w);
+ double edgeValue = bcEdgeDecorator.get(currentEdge).doubleValue();
+ edgeValue += partialDependency;
+ bcEdgeDecorator.put(currentEdge, edgeValue);
+ }
+ if (w != s) {
+ double bcValue = bcVertexDecorator.get(w).doubleValue();
+ bcValue += decorator.get(w).dependency;
+ bcVertexDecorator.put(w, bcValue);
+ }
+ }
+ }
+
+ if(graph instanceof UndirectedGraph) {
+ for (V v : vertices) {
+ double bcValue = bcVertexDecorator.get(v).doubleValue();
+ bcValue /= 2.0;
+ bcVertexDecorator.put(v, bcValue);
+ }
+ for (E e : graph.getEdges()) {
+ double bcValue = bcEdgeDecorator.get(e).doubleValue();
+ bcValue /= 2.0;
+ bcEdgeDecorator.put(e, bcValue);
+ }
+ }
+
+ for (V vertex : vertices) {
+ decorator.remove(vertex);
+ }
+ }
+
+ private void initializeData(Graph<V,E> g, Map<V,BetweennessData> decorator) {
+ for (V vertex : g.getVertices()) {
+
+ Map<V,Number> bcVertexDecorator = vertexRankScores.get(getRankScoreKey());
+ if(bcVertexDecorator.containsKey(vertex) == false) {
+ bcVertexDecorator.put(vertex, 0.0);
+ }
+ decorator.put(vertex, new BetweennessData());
+ }
+ for (E e : g.getEdges()) {
+
+ Map<E,Number> bcEdgeDecorator = edgeRankScores.get(getRankScoreKey());
+ if(bcEdgeDecorator.containsKey(e) == false) {
+ bcEdgeDecorator.put(e, 0.0);
+ }
+ }
+ }
+
+ /**
+ * the user datum key used to store the rank scores
+ * @return the key
+ */
+ @Override
+ public String getRankScoreKey() {
+ return CENTRALITY;
+ }
+
+ @Override
+ public void step() {
+ computeBetweenness(getGraph());
+ }
+
+ class BetweennessData {
+ double distance;
+ double numSPs;
+ List<V> predecessors;
+ double dependency;
+
+ BetweennessData() {
+ distance = -1;
+ numSPs = 0;
+ predecessors = new ArrayList<V>();
+ dependency = 0;
+ }
+ }
+}
Code Review / controller.git / blobdiff