[boost] Re: BGL bfs and dfs

From: vladimir josef sykora (vladimir.sykora_at_[hidden])
Date: 2003-02-11 08:29:54

> > The point is that I have my own internal properties for vertices and
edges,
> > and I had to construct new color maps to pass to the algorithms
(providing
> > get() and put()). Does this mean a that shallow copy is a requirement
for
> > the concept of property map?
>
> The docs state that in quite vague terms and I don't remember where. I've
> asked Jeremy about that and he agreed more documentation is needed, but
I'm
> not sure what those docs should say :-(
>

If the algorithms' implementations receive color maps by value (which is the
case,) shallow copy is a requirement. The question is wheter this can
change. If shallow copy requirement is only needed in the algorithms, why
place more constraints on the concept if it can be solved by passing it as
reference?
Having internal properties means the mapping edge_descriptor -> 'edge color'
and vertex_descriptor -> 'vertex color' is needed. For vertex-color mapping
this is straightforward because vertex_descriptor is of type size_t (when
using vectS) and the mapping can be easily implemented with a random-access
container. However, for edge-color mapping this is not the case. I did it
using std::map<std::pair<size_t, size_t>, color_type>, and of course,
overloading put() and get(), not without first inspecting that
edge_descriptor type has two data-members: m_source, and m_target, so the
functions would look like:

  template <class Prop, class Graph>
  inline
  const Prop&
  get(my_edge_color_map<Prop,Graph>& i,
      const typename my_edge_color_map<Prop,Graph>::key_type& key)  // key
is edge_descriptor
  {

    unsigned int source=key.m_source;
    unsigned int target=key.m_target;
    if(source>target) std::swap(source,target);    // canonizing for
undirected graph

    return i.m_map[std::make_pair(source, target)];
  }

  template <class Prop, class Graph>
  inline
  void
  put(my_edge_color_map<Prop,Graph>& i,
      const typename my_edge_color_map<Prop,Graph>::key_type& key,  // key
is edge_descriptor
      Prop value)
  {

    unsigned int source=key.m_source;
    unsigned int target=key.m_target;
    if(source>target) std::swap(source,target);        // canonizing for
undirected graph

    i.m_map[std::make_pair(source, target)] = value;
  }

Note that std::pair<size_t, size_t> in this case achieves strict weak
ordering using std::less<>.
I think this case should be properly documented (and yes, I'm offering to do
the job,) but I'd like to know if it's the right solution. See also that
associative_property_map<> does not work here.