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

From: Doug Gregor (dgregor_at_[hidden])
Date: 2005-09-06 15:27:11

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