Re: [Boost-users] [BGL] how does automatic vertex_index creation work?

From: Daniel Mitchell (danmitchell_at_[hidden])
Date: 2006-05-23 12:24:31

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_at_[hidden]
> > > http://lists.boost.org/mailman/listinfo.cgi/boost-users
> >
> > _______________________________________________
> > Boost-users mailing list
> > Boost-users_at_[hidden]
> > http://lists.boost.org/mailman/listinfo.cgi/boost-users
>
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users