On Wed, 7 Dec 2011, Nicolas Saunier wrote:

Hi,

...

...

Thanks for replying. The problem, and that may seem too simple or silly to people familiar with the library, is that I have no idea what should be the type of the component map to pass. I tried to declare the components variable as:

vector< graph_traits<FeatureGraph>::vertices_size_type > components(num_vertices(g));

And it does not work either. What is the type of the component map, the second argument of connected_components? Can you give me an example of a type that would work (compile and return the correct results)?

Try:

shared_array_property_map< ...::vertices_size_type, property_map<FeatureGraph, vertex_index_t>::const_type

...

components(num_vertices(g), get(vertex_index, g));

This requires a vecS vertex container, though.

-- Jeremiah Willcock

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?

#include <boost/graph/adjacency_list.hpp> #include <boost/shared_ptr.hpp> #include <boost/graph/connected_components.hpp>

using namespace boost; using namespace std;

struct FeatureTrajectory { int id; };

struct FeatureConnection { float minDistance; float maxDistance; };

struct VertexInformation { shared_ptr<FeatureTrajectory> feature; };

typedef adjacency_list < listS, listS, undirectedS, VertexInformation, FeatureConnection> FeatureGraph;

int main() { FeatureGraph g; FeatureGraph::vertex_descriptor u, v; FeatureGraph::edge_descriptor e;

u = add_vertex(g); v = add_vertex(g); bool unused; tie(e, unused) = add_edge(u, v, g);

g[e].minDistance = 0.; g[e].maxDistance = 1.;

g[u].feature = shared_ptr<FeatureTrajectory>(new FeatureTrajectory()); g[u].feature->id =11; g[v].feature = shared_ptr<FeatureTrajectory>(new FeatureTrajectory()); g[v].feature->id =12;

cout << num_vertices(g) << " " << num_edges(g) << endl;

vector_property_map< graph_traits<FeatureGraph>::vertices_size_type > components(num_vertices(g));

int num = connected_components(g, &components[0]);

return 0; }

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. -- Jeremiah Willcock