Re: [Boost-users] [BGL] Help with Brandes' Betweenness

From: Rui Carvalho (rui.carvalho_at_[hidden])
Date: 2005-09-09 12:20:40

Hi Doug,

This is quite helpful -thanks a lot.

Cheers,
Rui

> -----Original Message-----
> From: Doug Gregor [mailto:dgregor_at_[hidden]]
> Sent: 06 September 2005 21:27
> To: boost-users_at_[hidden]
> 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_at_[hidden]
> > http://lists.boost.org/mailman/listinfo.cgi/boost-users
>