Re: [Boost-users] (no subject)

Subject: Re: [Boost-users] (no subject)
From: Cedric Laczny (cedric.laczny_at_[hidden])
Date: 2011-04-07 02:50:44

Alright, now that was a somehow tricky one...
Details s. below.

On Wednesday, 6. April 2011 12:55:52 Gabriel Marchand wrote:
> Hi, I am new to boost and I face the same problem mentioned here with
> "connected_components()" using a mutable graph (hence using a list for  the
> vertex container). I try the detailed solution of Aaron Windsor in the 
> previous post but I still get some errors at compilation. Here is my 
> little code:
> 
> 
> 
>     #include <boost/graph/adjacency_list.hpp>
>     #include <boost/graph/connected_components.hpp>
> 
>     using namespace std;
>     using namespace boost;
> 
>     Box& b = conf.GetBox();
> 
> 
>     if (!ai) {
>         ai = new AtomList();
>         *ai = conf.GetAtoms().AtomSelector(selecti, b);
>     }
> 
>     typedef boost::adjacency_list<
>             listS,
>             listS,
>             undirectedS,
>     	    property<vertex_index_t, size_t>,
>     	    no_property>
> 
>     > graph_t;
> 
>     graph_t g(ai->size());
>     property_map<graph_t, vertex_index_t>::type index = get(vertex_index,
> g); graph_traits<graph_t>::vertex_iterator vi, vi_end;
>     graph_traits<graph_t>::vertices_size_type cnt = 0;
>     for(tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
>         put(index, *vi, cnt++);
> 
>     for (unsigned int i = 0; i < ai->size(); ++i) {
>         Cartesian& crdi = ai->GetElement(i)->pos;
>         for (unsigned int j = i + 1; j < ai->size(); ++j) {
>             Cartesian& crdj = ai->GetElement(j)->pos;
>             double r = conf.GetBox().CartesianDistance(crdi, crdj);
>             if (r < rcut) {
>                 add_edge(vertex(i,g), vertex(j,g), g); // Add edge to Map
> if distance criteria is satisfied
> 
>             }
>         }
>     }
> 
>     vector<int> component(num_vertices(g));
>     int num_clusters = connected_components(g, &component[0],
> vertex_index_map(index));
> 

In the example for connected_components() you used, you probably found the 
"&component[0]" notation and simply used it. However, this does _not_ work for 
graphs with listS, only for vecS. So basically what you have to do is to define 
your own components map and _not_ use that wrapper around a vector. As boost 
seems to model vertices with listS as void* this can hardly work as it is 
missing the index that it would normally have when using vecS. Also, for vecS, 
vertices seem to be modeled as int and therefore can serve as indices for 
vectors directly.

So, to make your code compiles, you should use:
  typedef graph_traits<graph_t>::vertex_descriptor Vertex;
  map< Vertex, unsigned int > index_std_map;

  typedef associative_property_map< map< Vertex, unsigned int > > IndexMap;
  IndexMap index( index_std_map ); 

  // put() the values by iterating over all vertices

instead of getting the vertex_index from the graph via "get(vertex_index, G)".
With this, you can define your own components-map:
  vector<int> v_component(num_vertices(G));
  iterator_property_map< vector<int>::iterator, IndexMap >
   component( v_component.begin(), index );

and call connected_components() via:
int num_clusters = connected_components(G, component, 
vertex_index_map(index));

> 
> 
> 
> The compilation is successfull until I add the last line:
>  int num_clusters = connected_components(g, &component[0],
> vertex_index_map(index));
> 
> 
> Hope somebody can give a hint
> gabriel

Hope that I could help and that this solution will be correct for you.
Please, of course, test the whole approach in order to make sure it works as 
you expect it to. 
Generally it should, as long as the mapping from vertex to index/offset is 
correct.
If there are further questions about the problem or my solution, feel free to 
mail again.

Best,

Cedric