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

Subject: Re: [Boost-users] [BGL] Issue using connected_components
From: Nicolas Saunier (nicolas.saunier_at_[hidden])
Date: 2011-12-08 12:30:48

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?

>> I really find it difficult to find the information to use property maps in
>> the library: is there a tutorial or a more step by step documentation
>> somewhere?
> I forgot if the BGL book has any more details, but you can look in
> libs/graph/example in the Boost source tree and also in
> http://programmingexamples.net/wiki/Boost/BGL for code samples.

Thanks for the link and for the help!

Nicolas
-- 
Nicolas Saunier, ing. jr, Ph.D.
Professeur Adjoint / Assistant Professor
Département des génies civil, géologique et des mines (CGM)
École Polytechnique de Montréal
http://nicolas.saunier.confins.net