Re: [Boost-users] [BGL] Issue using connected_components

Subject: Re: [Boost-users] [BGL] Issue using connected_components
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2011-12-07 20:50:45

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