Boost logo

Boost Users :

Subject: [Boost-users] BGL: counting connected components subgraph
From: Arman Khalatyan (arm2arm_at_[hidden])
Date: 2009-11-24 08:08:35


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.



Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net