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-07 18:47:07

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?

Finally, how could I modify my initial code to make it work?

#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?

Thanks again!

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