Re: [Boost-users] connected_components

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2008-06-03 08:11:04

On Mon, Jun 2, 2008 at 1:28 PM, Imran A. Pirwani <pirwani_at_[hidden]> wrote:
> Hi,
>
> I am new to boost. I would like to use the following:
>
> typedef adjacency_list< listS, listS > Graph;
>
> Using a graph defined as above will allow me to call "remove_vertex".  I
> would also like to use "connected_components()" to get connected
> components after I have removed a bunch of vertices (by calling
> "remove_vertex").
>
> The example at:
> http://www.boost.org/doc/libs/1_35_0/libs/graph/example/connected_components.cpp
> doesn't work for me because of the difference in adjacency lists used. Any
> help will be greatly appreciated!

Hi Imran,

First, you won't be able to add vertices by referencing integers like
the example does, but you can do something like:

graph_traits<Graph>::vertex_descriptor v1 = add_vertex(G);
graph_traits<Graph>::vertex_descriptor v2 = add_vertex(G);
...
add_edge(v1,v2,G);

You'll also need to create and populate your own vertex index map.
When you use a vecS as the vertex storage selector, a vertex index map
is implicitly defined for you (the actual index of each vertex in the
vector is used as the vertex index), but with a listS, you'll need to
index the vertices manually. See
http://www.boost.org/doc/libs/1_35_0/libs/graph/doc/faq.html, #5 for
how to do this. Next, you need to pass this vertex index map to the
connected components function. If you have the vertex index map in a
variable called "index", as in the example from the FAQ, you can do
this by calling "connected_components(G, &component[0],
vertex_index_map(index))" in place of the connected_components call in
the example you linked to.

Regards,
Aaron