[BGL] connected_components of filtered_graph
With boost_1_32_0, i want to find connected components of a filtered graph. What is an appropriate second argument of algorithm, connected_components, which is applied to a filtered graph? The following obviously fails for finding components' ID for each vertex of filtered graph. // Filtered graph Graph g; // graph to be filtered typedef property_map<Graph, vertex_flag_t>::type VertexFlagMap; filter_vertex_flag<VertexFlagMap> v_filter(v_flag); typedef property_map<Graph, edge_flag_t>::type EdgeFlagMap; filter_edge_flag<EdgeFlagMap> e_filter(e_flag); typedef filtered_graph< Graph, filter_edge_flag<EdgeFlagMap>, filter_vertex_flag<VertexFlagMap> > FGraph; FGraph fg(g, e_filter, v_filter); // Connected components std::vector<int> comp(n_fg); int n_comp = connected_components(fg, make_iterator_property_map(comp.begin(), get(vertex_index,fg))); where n_fg is the number of vertices in the filtered graph. Instead make std::vector<int> comp(num_vertices(g)); and iterates over vertices in the filtered graph to see assigned components' ID, it's fine, but then i need to have extra space than necessary when a graph to be filtered is large but the filtered one is quite small. wondering what is appropriate for the second argument in my case. Though i tried to find an example in tutorial samples and checked the ML archive, i could not find a similar question before. i appreciate any help or "look at here". Yoshi
On Aug 9, 2005, at 3:29 AM, Yoshi Fujiwara wrote:
With boost_1_32_0, i want to find connected components of a filtered graph. What is an appropriate second argument of algorithm, connected_components, which is applied to a filtered graph?
The following obviously fails for finding components' ID for each vertex of filtered graph. [snip example] where n_fg is the number of vertices in the filtered graph.
Instead make std::vector<int> comp(num_vertices(g)); and iterates over vertices in the filtered graph to see assigned components' ID, it's fine, but then i need to have extra space than necessary when a graph to be filtered is large but the filtered one is quite small.
wondering what is appropriate for the second argument in my case.
Typically to create a property map you need a mapping from vertices to indices in [0, n), where n is the number of vertices. However, since you've filtered the graph, the vertex indices of the filtered graph are still in [0, n) and not in [0, n_fg). You could attach a property to the graph that gives vertex indices in [0, n_fg) to each of the vertices in the filtered graph, then use that vertex index map instead. Doug
participants (2)
-
Doug Gregor -
Yoshi Fujiwara