Re: [Boost-users] [BGL] Issue using connected_components

Subject: Re: [Boost-users] [BGL] Issue using connected_components
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2011-12-08 14:00:45

On Thu, 8 Dec 2011, Nicolas Saunier wrote:

> Hi Jeremiah,
>
>>> Ok, I understand now that vertex_descriptor are integers if one uses a 
>>> vecS
>>> for the vertex list. I have changed the type of my undirected graph to
>>> boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS,
>>> VertexInformation, FeatureConnection> and used a simple
>>> vector<FeatureGraph::vertex_descriptor> for the component map and it works
>>> nicely.
>>> 
>>> Another question is about efficiency: what are the 
>>> advantages/disadvantages
>>> to use vecS or listS for the list of vertices?
>> The main difference is the speed of inserting and removing vertices, with
>> a secondary difference being when vertex descriptors and iterators are
>> invalidated.  Look on the adjacency_list documentation page for more
>> detail on exactly which operations are affected.
>> 
>>> Finally, how could I modify my initial code to make it work?
>> How much of it do you want to keep?  The solution I gave you before
>> requires two changes (to the graph and to the definition of the component
>> map).  If you want to keep the listS vertex container, you could also use
>> associative_property_map for your components, or add a vertex_index
>> property to your graph and fill it in before you create your property map.
>> Are you looking for one of those options?
>
> My requirements are a undirected graph, with frequent additions and removals 
> of vertices/edges, and frequent computation of connected components. That is 
> why I thought that listS vextex container was more appropriate. I would 
> expect that the component map could then be some associative map from 
> vertex_descriptors to component id: what is the exact type? Is it necessary 
> to compute a vertex index (what is it exactly), how do I do so and is is 
> computationally intensive?

If you use an associative property map, you will not need a vertex index 
map.  See 
http://www.boost.org/doc/libs/1_48_0/libs/property_map/doc/associative_property_map.html 
for documentation on how to create one.

-- Jeremiah Willcock