BGL: counting connected components subgraph
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.
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
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);??? /// }
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. Gabe
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. Gabe
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.
On Wed, Nov 25, 2009 at 2:07 PM, 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.
Gabe _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
participants (2)
-
Arman Khalatyan -
Gábor Szuromi