Re: [Boost-users] [BGL] Issue using connected_components
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
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
participants (2)
-
Jeremiah Willcock
-
Nicolas Saunier