[BGL] how does automatic vertex_index creation work?
Hi folks! I defined a customary graph type which always uses integers in a bound range to adress the vertices. It is therefore as if one would use an adjacency_list with vecS as vertex storage set. Since I want to run an algorithm requiring a vertex_index property to be present on my custom graph, I was looking at the code of the adjacency_list graph. The docs say, that somewhere in the code the vertex_index map does get created automatically if the vertex set is vecS, but where and how is it done? The code is just too big or too advanced for me to find the appropiate lines. Could someone please enlighten me? Thanks in advance, Sebastian Weber
The vertex index property map for vecS is defined on line 2444 in detail/adjacency_list.hpp. Since vertices are integers in [0,num_vertices), the index of each vertex is the vertex itself. D. On Tuesday 23 May 2006 09:56, Sebastian Weber wrote:
Hi folks!
I defined a customary graph type which always uses integers in a bound range to adress the vertices. It is therefore as if one would use an adjacency_list with vecS as vertex storage set. Since I want to run an algorithm requiring a vertex_index property to be present on my custom graph, I was looking at the code of the adjacency_list graph. The docs say, that somewhere in the code the vertex_index map does get created automatically if the vertex set is vecS, but where and how is it done? The code is just too big or too advanced for me to find the appropiate lines. Could someone please enlighten me?
Thanks in advance,
Sebastian Weber
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Hi!
The vertex index property map for vecS is defined on line 2444 in detail/adjacency_list.hpp. Since vertices are integers in [0,num_vertices), the index of each vertex is the vertex itself.
Thanks for pointing out these lines. Nevertheless, I'm not a template pro in order to understand all those helper-classes and definitions. So, how do I code a vertex_index-map when I always have the case where the vertices are integers [0,num_vertices). Sorry, but the code on line 2444 is just too advanced for my C++ skill right now. Any help is greatly appreciated. Greetings, Sebastian Weber
D.
On Tuesday 23 May 2006 09:56, Sebastian Weber wrote:
Hi folks!
I defined a customary graph type which always uses integers in a bound range to adress the vertices. It is therefore as if one would use an adjacency_list with vecS as vertex storage set. Since I want to run an algorithm requiring a vertex_index property to be present on my custom graph, I was looking at the code of the adjacency_list graph. The docs say, that somewhere in the code the vertex_index map does get created automatically if the vertex set is vecS, but where and how is it done? The code is just too big or too advanced for me to find the appropiate lines. Could someone please enlighten me?
Thanks in advance,
Sebastian Weber
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
The property map definition will be something like: struct vertex_index_property_map : boost::put_get_helper< Graph::vertices_size_type,vertex_index_property_map> { public: typedef boost::readable_property_map_tag category; typedef Graph::vertex_descriptor key_type; typedef Graph::vertices_size_type value_type; typedef Graph::vertices_size_type reference; reference operator[]( key_type const& u ) const { return u; } }; You'll need to specialize boost::property_map: namespace boost { template<> struct property_map<Graph,vertex_index_t> { typedef vertex_index_property_map type; typedef vertex_index_property_map const_type; }; } Finally, you'll need a couple of get() functions: vertex_index_property_map get( boost::vertex_index_t, Graph const& ) { return vertex_index_property_map(); } Graph::vertices_size_type get( boost::vertex_index_t tag, Graph const& g, Graph::vertex_descriptor u ) { return get( get( tag, g), u ); } That's pretty much it. If Graph is a class template, you'll need to partially specialize boost::property_map. If you compiler doesn't support partial specialization, you'll need to use a workaround or get a better compiler. (Those helper classes you mentioned in detail/adjacency_list.hpp are part of a workaround for partial specialization.) D. P.S. In property_map.hpp there is a class called identity_property_map that maps integers to themselves. You could use that class instead vertex_index_property_map, if you prefer. On Tuesday 23 May 2006 10:25, Sebastian Weber wrote:
Hi!
The vertex index property map for vecS is defined on line 2444 in detail/adjacency_list.hpp. Since vertices are integers in [0,num_vertices), the index of each vertex is the vertex itself.
Thanks for pointing out these lines. Nevertheless, I'm not a template pro in order to understand all those helper-classes and definitions. So, how do I code a vertex_index-map when I always have the case where the vertices are integers [0,num_vertices).
Sorry, but the code on line 2444 is just too advanced for my C++ skill right now.
Any help is greatly appreciated.
Greetings,
Sebastian Weber
D.
On Tuesday 23 May 2006 09:56, Sebastian Weber wrote:
Hi folks!
I defined a customary graph type which always uses integers in a bound range to adress the vertices. It is therefore as if one would use an adjacency_list with vecS as vertex storage set. Since I want to run an algorithm requiring a vertex_index property to be present on my custom graph, I was looking at the code of the adjacency_list graph. The docs say, that somewhere in the code the vertex_index map does get created automatically if the vertex set is vecS, but where and how is it done? The code is just too big or too advanced for me to find the appropiate lines. Could someone please enlighten me?
Thanks in advance,
Sebastian Weber
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
participants (2)
-
Daniel Mitchell -
Sebastian Weber