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!
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
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
participants (2)
-
Arman Khalatyan -
Gábor Szuromi