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_prope... for documentation on how to create one. -- Jeremiah Willcock