Boost logo

Boost Users :

From: Doug Gregor (dgregor_at_[hidden])
Date: 2005-08-09 14:52:54


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


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