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-16 11:33:14

Hi everyone,

I finally found a solution by myself to get connected_components from a 
graph of type adjacency_list<listS, listS, undirectedS> with bundled 
properties for the vertices and edges. So I will post it here so that 
others can find it, to get feedback and make sure I am doing it right:

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

using namespace boost;
using namespace std;

struct FeatureConnection {
   float minDistance;
   float maxDistance;
};

struct VertexInformation {
   int featureId;
   int index;
};

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

int main() {
   UndirectedGraph g;
   UndirectedGraph::vertex_descriptor u, v, w, x, y;
   UndirectedGraph::edge_descriptor e, f;

   u = add_vertex(g);
   v = add_vertex(g);
   w = add_vertex(g);
   x = add_vertex(g);
   y = add_vertex(g);

   bool unused;
   tie(e, unused) = add_edge(u, v, g);
   tie(f, unused) = add_edge(x, y, g);

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

   graph_traits<UndirectedGraph>::vertex_iterator vi, vend;
   graph_traits<UndirectedGraph>::vertices_size_type cnt = 0;
   for(tie(vi,vend) = vertices(g); vi != vend; ++vi)
     g[*vi].index = cnt++;

   property_map<UndirectedGraph, int VertexInformation::*>::type 
components = get(&VertexInformation::index, g);

   int num = connected_components(g, components, 
vertex_index_map(get(&VertexInformation::index, g)));
   cout << num << endl;

   for(tie(vi,vend) = vertices(g); vi != vend; ++vi)
     cout << *vi << " " << components[*vi] << " " << g[*vi].index << endl;

   return 0;
}

Thanks,

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