Re: [Boost-users] BGL: counting connected components subgraph

Subject: Re: [Boost-users] BGL: counting connected components subgraph
From: Gábor Szuromi (kukkerman_at_[hidden])
Date: 2009-11-24 12:25:46

Hi!

> Hello, I wondered are there way to count connected components in the minimum
> spanning tree?
> Currently I just making copy of graph to be able to count and collect
> connected components are there more efficient way to do that?

If you just want to know the number of connected components define
your own predecessor_map for kruskal_minimum_spanning_tree. Then you
can count the vertices with themselves as predecessor. These vertices
are the roots of the spearate trees:

std::vector < Edge > spanning_tree;
Graph graphMST;
std::vector < Graph::vertex_descriptor > pred(num_vertices(graphMST));
// Use the vertex index map just in case of vertices are not numbered 0...n-1
property_map< Graph, vertex_index_t>::type vi_map =
get(vertex_index_t(), graphMST);

kruskal_minimum_spanning_tree(graphFOREST,
std::back_inserter(spanning_tree),
predecessor_map(make_iterator_property_map(pred.begin(), vi_map)) );

int   num_components = 0;
Graph::vertex_iterator  vi, vi_end;
for(tie(vi, vi_end) = vertices(graphMST); vi != vi_end; ++vi)
 if(*vi == pred[get(vi_map, *vi)])
   num_components++;

Cheers,
  Gabe