[Boost-users] BGL: counting connected components subgraph

[Arman Khalatyan]

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?

______________________________

std::vector < Edge > spanning_tree;

Graph graphMST;

kruskal_minimum_spanning_tree(graphFOREST, std::back_inserter(spanning_tree));

for (std::vector < Edge >::iterator ei = spanning_tree.begin();

ei != spanning_tree.end(); ++ei) {

if(get(edge_weight, graphFOREST, *ei)<1.0)//lets cut the MTS by given threshold

add_edge(source(*ei, graphFOREST),target(*ei, graphFOREST),get(edge_weight, graphFOREST, *ei),graphMST);

}

num = connected_components(graphMST, &component[0]);

// Use components...

_______________________________

Thank you beforehand

Arman.

[Gábor Szuromi]

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
_______________________________________________
Boost-users mailing list
Boost...@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Arman Khalatyan]

Thanks for explanation, 

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:

 How to walk over those separate trees?

 Is it should be something like this?

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++;

else

{

 WriteOutTree(num_components);??? ///

}

[Gábor Szuromi]

Hi!

>  How to walk over those separate trees?

If you need the trees too I suggest using prim_minimum_spanning_tree
becuse the predecessor map in Kruskal's algorithm is used for the
disjoint-set data structure to indicate which set a particular vertex
is in so it cannot be used walking the tree. I think
prim_minimum_spanning_tree is a better choice here because it supports
dijkstra visitors so you can mark tree edges on-the-fly and then use a
filtered_graph to hide every non-marked edges to walk the trees. You
can use the predecessor map exactly like in the first method to
identify root vertices.

[Gábor Szuromi]

On second thought Prim's algorithm computes only the spanning tree of
the component the starting vertex belongs to. So instead you can use
the edge list returned by Kruskal's algorithm to mark tree edges and
then use filtered_graph to hide non-marked edges and transform the
original graph into a forest without creating a new graph. The
predecessor map can be used to identify the root node of trees.

[Arman Khalatyan]

Thanks, Kruskal's algorithm works nice, 

I would be nice to have in the BGL examples list how to cut and traverse over the disconnected subgraphs/components.