# Boost Users :

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/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;
CentralityMap, WeightMap> UndirectedGraph;
UndirectedGraph g(N);
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