Re: [Boost-users] (no subject)

Subject: Re: [Boost-users] (no subject)
From: Cedric Laczny (cedric.laczny_at_[hidden])
Date: 2011-04-07 14:03:29

On Thursday, 7. April 2011 13:31:56 Gabriel Marchand wrote:
> Thank you for this solution. It compiles. Nevertheless, I still don't
> achieve what I want to do and I don't understand a few things (I attached
> the code):
> 
> 1/ I run the connected_component() function after defining the graph
> graph_t G(num_nodes) and I expect that there should be as many components
> as num_nodes as I didn't add the edges yet. However the return of the
> function tells me there is 1 component ??
> 
> After adding the edges between all vertices, the number of components is 1,
> as it should be. But when I use the function clear_vertex(), I expect to
> create a new component as the vertex cleaned contain no more edges. The
> number of components is still one.
> 
> What I am doing wrong here?

Your forgot to fill the index map. Doing so, should make everything work as you 
expect it.

> 
> 2/I need to know the size in number of vertices of the components,
> therefore I need to use something like
> 
>  for (i = 0; i != num_nodes; ++i)
>      cout << "Vertex " << i <<" is in component " << component[i] << endl;
>      cout << endl;
> 
> but of course with our changings done this can't be used. Do you have an
> idea how I could extract this information.

You simply have to iterate over the vertices themself (instead of over the 
number of vertices) using vertex_iterator. You already have the necessary code 
when initializing the index map.
I would suggest you to have a deeper look at the introduction of BGL 
(again?!), especially the examples in order to get an idea about the versatile 
interfaces etc. that the BGL provides. Especially, when you plan to use the 
"not-so-common" listS vertex container. BTW, it might be worth a try to 
benchmark vecS against listS for a reasonable example in your situation. I 
would be interested in the performance differences and in case they prove to be 
negligible, perhaps think about using vecS instead, as I imagine this will 
save you some hard time figuring out the reason of unexpected behavior and 
waiting for help ;)

> 
> Gabriel

Hope that clears your questions so far.

Best,

Cedric

> 
> 
> --- En date de : Jeu 7.4.11, Cedric Laczny <cedric.laczny_at_[hidden]> a écrit :
> 
> De: Cedric Laczny <cedric.laczny_at_[hidden]>
> Objet: Re: [Boost-users] (no subject)
> À: boost-users_at_[hidden]
> Date: Jeudi 7 avril 2011, 6h50
> 
> 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
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users