+++ /dev/null
-/**
- * Copyright (c) 2008, 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.
- * Created on Sep 16, 2008
- *
- */
-package edu.uci.ics.jung.algorithms.scoring;
-
-import java.util.ArrayList;
-import java.util.Comparator;
-import java.util.HashMap;
-import java.util.LinkedList;
-import java.util.List;
-import java.util.Map;
-import java.util.Queue;
-import java.util.Stack;
-
-import org.apache.commons.collections15.Transformer;
-import org.apache.commons.collections15.functors.ConstantTransformer;
-
-import edu.uci.ics.jung.algorithms.util.MapBinaryHeap;
-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.
- *
- * @see "Ulrik Brandes: A Faster Algorithm for Betweenness Centrality. Journal of Mathematical Sociology 25(2):163-177, 2001."
- */
-public class BetweennessCentrality<V, E>
- implements VertexScorer<V, Double>, EdgeScorer<E, Double>
-{
- protected Graph<V,E> graph;
- protected Map<V, Double> vertex_scores;
- protected Map<E, Double> edge_scores;
- protected Map<V, BetweennessData> vertex_data;
-
- /**
- * Calculates betweenness scores based on the all-pairs unweighted shortest paths
- * in the graph.
- * @param graph the graph for which the scores are to be calculated
- */
- @SuppressWarnings("unchecked")
- public BetweennessCentrality(Graph<V, E> graph)
- {
- initialize(graph);
- computeBetweenness(new LinkedList<V>(), new ConstantTransformer(1));
- }
-
- /**
- * Calculates betweenness scores based on the all-pairs weighted shortest paths in the
- * graph.
- *
- * <p>NOTE: This version of the algorithm may not work correctly on all graphs; we're still
- * working out the bugs. Use at your own risk.
- * @param graph the graph for which the scores are to be calculated
- * @param edge_weights the edge weights to be used in the path length calculations
- */
- public BetweennessCentrality(Graph<V, E> graph,
- Transformer<E, ? extends Number> edge_weights)
- {
- // reject negative-weight edges up front
- for (E e : graph.getEdges())
- {
- double e_weight = edge_weights.transform(e).doubleValue();
- if (e_weight < 0)
- throw new IllegalArgumentException(String.format(
- "Weight for edge '%s' is < 0: %d", e, e_weight));
- }
-
- initialize(graph);
- computeBetweenness(new MapBinaryHeap<V>(new BetweennessComparator()),
- edge_weights);
- }
-
- protected void initialize(Graph<V,E> graph)
- {
- this.graph = graph;
- this.vertex_scores = new HashMap<V, Double>();
- this.edge_scores = new HashMap<E, Double>();
- this.vertex_data = new HashMap<V, BetweennessData>();
-
- for (V v : graph.getVertices())
- this.vertex_scores.put(v, 0.0);
-
- for (E e : graph.getEdges())
- this.edge_scores.put(e, 0.0);
- }
-
- protected void computeBetweenness(Queue<V> queue,
- Transformer<E, ? extends Number> edge_weights)
- {
- for (V v : graph.getVertices())
- {
- // initialize the betweenness data for this new vertex
- for (V s : graph.getVertices())
- this.vertex_data.put(s, new BetweennessData());
-
-// if (v.equals(new Integer(0)))
-// System.out.println("pause");
-
- vertex_data.get(v).numSPs = 1;
- vertex_data.get(v).distance = 0;
-
- Stack<V> stack = new Stack<V>();
-// Buffer<V> queue = new UnboundedFifoBuffer<V>();
-// queue.add(v);
- queue.offer(v);
-
- while (!queue.isEmpty())
- {
-// V w = queue.remove();
- V w = queue.poll();
- stack.push(w);
- BetweennessData w_data = vertex_data.get(w);
-
- for (E e : graph.getOutEdges(w))
- {
- // TODO (jrtom): change this to getOtherVertices(w, e)
- V x = graph.getOpposite(w, e);
- if (x.equals(w))
- continue;
- double wx_weight = edge_weights.transform(e).doubleValue();
-
-
-// for(V x : graph.getSuccessors(w))
-// {
-// if (x.equals(w))
-// continue;
-
- // FIXME: the other problem is that I need to
- // keep putting the neighbors of things we've just
- // discovered in the queue, if they're undiscovered or
- // at greater distance.
-
- // FIXME: this is the problem, right here, I think:
- // need to update position in queue if distance changes
- // (which can only happen with weighted edges).
- // for each outgoing edge e from w, get other end x
- // if x not already visited (dist x < 0)
- // set x's distance to w's dist + edge weight
- // add x to queue; pri in queue is x's dist
- // if w's dist + edge weight < x's dist
- // update x's dist
- // update x in queue (MapBinaryHeap)
- // clear x's incoming edge list
- // if w's dist + edge weight = x's dist
- // add e to x's incoming edge list
-
- BetweennessData x_data = vertex_data.get(x);
- double x_potential_dist = w_data.distance + wx_weight;
-
- if (x_data.distance < 0)
- {
-// queue.add(x);
-// vertex_data.get(x).distance = vertex_data.get(w).distance + 1;
- x_data.distance = x_potential_dist;
- queue.offer(x);
- }
-
- // note:
- // (1) this can only happen with weighted edges
- // (2) x's SP count and incoming edges are updated below
- if (x_data.distance > x_potential_dist)
- {
- x_data.distance = x_potential_dist;
- // invalidate previously identified incoming edges
- // (we have a new shortest path distance to x)
- x_data.incomingEdges.clear();
- // update x's position in queue
- ((MapBinaryHeap<V>)queue).update(x);
- }
-// if (vertex_data.get(x).distance == vertex_data.get(w).distance + 1)
- //
-// if (x_data.distance == x_potential_dist)
-// {
-// x_data.numSPs += w_data.numSPs;
-//// vertex_data.get(x).predecessors.add(w);
-// x_data.incomingEdges.add(e);
-// }
- }
- for (E e: graph.getOutEdges(w))
- {
- V x = graph.getOpposite(w, e);
- if (x.equals(w))
- continue;
- double e_weight = edge_weights.transform(e).doubleValue();
- BetweennessData x_data = vertex_data.get(x);
- double x_potential_dist = w_data.distance + e_weight;
- if (x_data.distance == x_potential_dist)
- {
- x_data.numSPs += w_data.numSPs;
-// vertex_data.get(x).predecessors.add(w);
- x_data.incomingEdges.add(e);
- }
- }
- }
- while (!stack.isEmpty())
- {
- V x = stack.pop();
-
-// for (V w : vertex_data.get(x).predecessors)
- for (E e : vertex_data.get(x).incomingEdges)
- {
- V w = graph.getOpposite(x, e);
- double partialDependency =
- vertex_data.get(w).numSPs / vertex_data.get(x).numSPs *
- (1.0 + vertex_data.get(x).dependency);
- vertex_data.get(w).dependency += partialDependency;
-// E w_x = graph.findEdge(w, x);
-// double w_x_score = edge_scores.get(w_x).doubleValue();
-// w_x_score += partialDependency;
-// edge_scores.put(w_x, w_x_score);
- double e_score = edge_scores.get(e).doubleValue();
- edge_scores.put(e, e_score + partialDependency);
- }
- if (!x.equals(v))
- {
- double x_score = vertex_scores.get(x).doubleValue();
- x_score += vertex_data.get(x).dependency;
- vertex_scores.put(x, x_score);
- }
- }
- }
-
- if(graph instanceof UndirectedGraph)
- {
- for (V v : graph.getVertices()) {
- double v_score = vertex_scores.get(v).doubleValue();
- v_score /= 2.0;
- vertex_scores.put(v, v_score);
- }
- for (E e : graph.getEdges()) {
- double e_score = edge_scores.get(e).doubleValue();
- e_score /= 2.0;
- edge_scores.put(e, e_score);
- }
- }
-
- vertex_data.clear();
- }
-
-// protected void computeWeightedBetweenness(Transformer<E, ? extends Number> edge_weights)
-// {
-// for (V v : graph.getVertices())
-// {
-// // initialize the betweenness data for this new vertex
-// for (V s : graph.getVertices())
-// this.vertex_data.put(s, new BetweennessData());
-// vertex_data.get(v).numSPs = 1;
-// vertex_data.get(v).distance = 0;
-//
-// Stack<V> stack = new Stack<V>();
-//// Buffer<V> queue = new UnboundedFifoBuffer<V>();
-// SortedSet<V> pqueue = new TreeSet<V>(new BetweennessComparator());
-//// queue.add(v);
-// pqueue.add(v);
-//
-//// while (!queue.isEmpty())
-// while (!pqueue.isEmpty())
-// {
-//// V w = queue.remove();
-// V w = pqueue.first();
-// pqueue.remove(w);
-// stack.push(w);
-//
-//// for(V x : graph.getSuccessors(w))
-// for (E e : graph.getOutEdges(w))
-// {
-// // TODO (jrtom): change this to getOtherVertices(w, e)
-// V x = graph.getOpposite(w, e);
-// if (x.equals(w))
-// continue;
-// double e_weight = edge_weights.transform(e).doubleValue();
-//
-// if (vertex_data.get(x).distance < 0)
-// {
-//// queue.add(x);
-// pqueue.add(v);
-//// vertex_data.get(x).distance = vertex_data.get(w).distance + 1;
-// vertex_data.get(x).distance =
-// vertex_data.get(w).distance + e_weight;
-// }
-//
-//// if (vertex_data.get(x).distance == vertex_data.get(w).distance + 1)
-// if (vertex_data.get(x).distance ==
-// vertex_data.get(w).distance + e_weight)
-// {
-// vertex_data.get(x).numSPs += vertex_data.get(w).numSPs;
-// vertex_data.get(x).predecessors.add(w);
-// }
-// }
-// }
-// updateScores(v, stack);
-// }
-//
-// if(graph instanceof UndirectedGraph)
-// adjustUndirectedScores();
-//
-// vertex_data.clear();
-// }
-
- public Double getVertexScore(V v)
- {
- return vertex_scores.get(v);
- }
-
- public Double getEdgeScore(E e)
- {
- return edge_scores.get(e);
- }
-
- private class BetweennessData
- {
- double distance;
- double numSPs;
-// List<V> predecessors;
- List<E> incomingEdges;
- double dependency;
-
- BetweennessData()
- {
- distance = -1;
- numSPs = 0;
-// predecessors = new ArrayList<V>();
- incomingEdges = new ArrayList<E>();
- dependency = 0;
- }
-
- @Override
- public String toString()
- {
- return "[d:" + distance + ", sp:" + numSPs +
- ", p:" + incomingEdges + ", d:" + dependency + "]\n";
-// ", p:" + predecessors + ", d:" + dependency + "]\n";
- }
- }
-
- private class BetweennessComparator implements Comparator<V>
- {
- public int compare(V v1, V v2)
- {
- return vertex_data.get(v1).distance > vertex_data.get(v2).distance ? 1 : -1;
- }
- }
-}
Code Review / controller.git / blobdiff