[BGL] Help with Brandes' Betweenness

31 Aug 2005

      Hi,

I'm trying to write code to compute Brandes' Betweenness Centrality for a
very simple graph: a star. I'm doing this, as I haven't been able to find
simple examples in the documentation [hint :)] for vecS,vecS graphs and
still haven't grasped how edge property maps work.

I've got it running if all I want is to compute vertex BC (see below, also
attached), but can't get it to compute both vertex and edge BC. I'd
appreciate any suggestions -perhaps my example (or something similar) could
be corrected and included in the BGL?

Thanks,
Rui

#include <iostream>					// for std::dataout
#include <utility>					// for std::pair

#include <boost/utility.hpp>				// for boost::tie
#include <boost/graph/graph_traits.hpp>	// for boost::graph_traits
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/betweenness_centrality.hpp>//for
boost::brandes_betweenness_centrality

#include <boost/graph/adjacency_list.hpp>

using namespace boost;
using namespace std;

typedef adjacency_list < vecS,				//Store out-edges
vecS,
//Store vertex set
undirectedS,							//the graph
is undirected	
property<edge_index_t, int> > 			
Graph;

typedef graph_traits<Graph>::vertex_descriptor Vertex;
typedef graph_traits<Graph>::vertex_iterator Vertex_Iter;

typedef graph_traits<Graph>::edge_descriptor Edge;
typedef graph_traits<Graph>::edge_iterator Edge_Iter;		

typedef property_map<Graph, vertex_name_t>::type Name_Map_t;	
typedef property_map<Graph, edge_index_t>::type Edge_Map_t;

int main(int,char*[])
{
	int n_vrtx = 5;	

	//Builds graph with vertices, but no edges
	Graph g_star(n_vrtx);		

	//Add edges. Graph g_star is a star
	add_edge(vertex(0, g_star), vertex(4, g_star), g_star);
	add_edge(vertex(1, g_star), vertex(4, g_star), g_star);
	add_edge(vertex(2, g_star), vertex(4, g_star), g_star);
	add_edge(vertex(3, g_star), vertex(4, g_star), g_star);

	Vertex_Iter vertex_iterator_begin, vertex_iterator_end;

	std::vector<double> centrality(n_vrtx);

	brandes_betweenness_centrality(g_star,
centrality_map(make_iterator_property_map(centrality.begin(),
get(vertex_index, g_star),double())).vertex_index_map(get(vertex_index,
g_star)));

	for ( tie(vertex_iterator_begin, vertex_iterator_end) =
vertices(g_star); 			vertex_iterator_begin !=
vertex_iterator_end; ++vertex_iterator_begin)
	{		
		cout << "Vertex: " <<  *vertex_iterator_begin <<"\tBC: "<<
centrality[*vertex_iterator_begin] << endl;

	}	
}

Rui Carvalho