[BGL] Help with Brandes' Betweenness

Hi Doug, This is quite helpful -thanks a lot. Cheers, Rui

-----Original Message----- From: Doug Gregor [mailto:dgregor@cs.indiana.edu] Sent: 06 September 2005 21:27 To: boost-users@lists.boost.org Subject: Re: [Boost-users] [BGL] Help with Brandes' Betweenness

Hi Rui,

I just sent a reply about "using biconnected_components" that addresses the same issue. You can create an associative_property_map from an std::map and the following function object:

struct order_edges { template<typename T> bool operator()(const T& x, const T& y) const { return x.get_property() < y.get_property(); } };

The map (base_map) and property map ("edge_centrality") will look like this:

typedef std::map< graph_traits<graph_t>::edge_descriptor, double, order_edges> map_t; map_t base_map; associative_property_map< map_t > edge_centrality(base_map);

We'll try to make this easier in subsequent releases.

Doug

On Aug 31, 2005, at 11:05 AM, Rui Carvalho wrote:

...

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;

} } <BCexample.cpp>_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users