[Boost-users] [BGL] brandes betweenness vs networkx

Subject: [Boost-users] [BGL] brandes betweenness vs networkx
From: Matthew Galati (magh_at_[hidden])
Date: 2008-11-11 14:27:09

What is the rationale behind division by 2 for the undirected Brandes 
calcuation?

Also, can someone show me how to get the weighted version of brandes? 
The following code calculates the unweighted version.

#include "boost/graph/adjacency_list.hpp"
#include "boost/graph/graph_utility.hpp"
#include "boost/graph/betweenness_centrality.hpp"

using namespace boost;

int main(int argc, char * argv[]){
  const int N = 6;

  typedef property < edge_weight_t, double > WeightMap;
  typedef property < vertex_centrality_t, double > CentralityMap;
  typedef adjacency_list<vecS, vecS, undirectedS,
     CentralityMap, WeightMap> UndirectedGraph;
  UndirectedGraph g(N);
  add_edge(0, 1, 3, g);
  add_edge(0, 2, 2, g);
  add_edge(0, 3, 6, g);
  add_edge(0, 4, 4, g);
  add_edge(1, 3, 5, g);
  add_edge(1, 5, 5, g);
  add_edge(2, 4, 1, g);
  add_edge(3, 4, 2, g);
  add_edge(3, 5, 1, g);
  add_edge(4, 5, 4, g);
  print_graph(g);

  brandes_betweenness_centrality(g,
                                 get(vertex_centrality,g),
                                 get(edge_weight, g)
                                 );

  boost::property_map<UndirectedGraph, vertex_centrality_t>::type
     b = get(vertex_centrality, g);

  graph_traits < UndirectedGraph  >::vertex_iterator vi, vi_end;
  for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
     printf("BRANDES centr[%d] = %g\n",
            *vi,
            b[*vi]);
  }
}

Boost/graph gives the following:
0 <--> 1 2 3 4
1 <--> 0 3 5
2 <--> 0 4
3 <--> 0 1 4 5
4 <--> 0 2 3 5
5 <--> 1 3 4
I AM HERE dispatch2
CALLING UNWEIGHTED
BRANDES centr[0] = 1.83333
BRANDES centr[1] = 0.333333
BRANDES centr[2] = 0
BRANDES centr[3] = 0.666667
BRANDES centr[4] = 1.83333
BRANDES centr[5] = 0.333333

While networkx gives:
http://networkx.lanl.gov/reference/generated/networkx.betweenness_centrality.html?highlight=brandes
{0: 3.6666666666666665, 1: 0.66666666666666663, 2: 0.0, 3: 
1.3333333333333333, 4: 3.6666666666666661, 5: 0.66666666666666663}

So, boost is exactly 1/2 of networkx's solution.

Is one version wrong? Or is this some kind of convention that boost and 
networkx disagree on?

Thanks,
Matt