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