[Boost-users] [BGL] connected_components of filtered_graph

From: Yoshi Fujiwara (yfujiwar_at_[hidden])
Date: 2005-08-09 03:29:31

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