Re: [boost] Re: Help needed with BGL & multi_index_container

From: JOAQUIN LOPEZ MU?Z (joaquin_at_[hidden])
Date: 2005-02-02 16:27:46

Hi Alexander,

----- Mensaje original -----
De: Alexander <rhjrjlbk2002_at_[hidden]>
Fecha: Miércoles, Febrero 2, 2005 8:38 pm
Asunto: [boost] Re: Help needed with BGL & multi_index_container

> Hi Joaquin and Jeremy,
> 
> Below you may find latest version of my test program.
> This time it compiles, links and works :-). I have to
> say - it was not easy to make it working.
> 
> The only trouble I have is clumsy code in templated
> ItemHolder::operator()(const P&p) and correspondent call
> to template ItemHolder::get_int(...). See my comments
> below.
> 
> I'm looking for advice to make it nicer.

I think I've got something, please read below.

> 
> Replacement of "const P& p" to "void*" breaks VS 7.1.
> 
[...]
> 
> > From: Joaquin M Lopez Munoz <joaquin <at> tid.es>
> > Date: Tue, 01 Feb 2005 22:51:12 +0000
> >   MG::vertex_descriptor vd1 =
> >    add_vertex( ItemHolder( 1, Item(1) ), mg );
> 
> In this line following is happen:
> 
> 1. adjacency_list allocates (with new) a new
> stored_vertex structure to store property
> element of type ItemHolder (yes, using my initialization
> value), fields to store incoming, outgoing edges and
> other fields.
> 
> 2. This pointer is cast to a void *, to be used as
> the new vertex descriptor.
> 
> 3. The void * is fed to the multi_index_container used
> for vertex storage.
> 
> 4. Now, inside ItemHolderKey, that "void *" must be converted to back
> to stored_vertex type, defined in base class of adajcent_list. And 
> thisI find as a real threat to break everything. To my regret, I 
> can't spend
> more
> time - I have to put all that into my project.
> 
> > Well, all in all I must say this is a glorious hack :)
> 
> Thank you! Indeed, you did helped me.
> 
> > Probably, the only sensible approach is to write from
> > scratch a graph-compliant structure that uses
> 
> I already did that couple of times. I do not want that anymore.
> Writing, testing, documenting, helping colleques to numerous
> suboptimal versions of the same component, scattered through
> number of versions of different products... No, thank you.
> 
> > That said, the thing seems to work and may suffice
> > for your purposes.
> 
> I see that as a quite general use case.
> 
> > It'd be great if some BGL expert (Jeremy?) jumped
> > in and comment on this.
> 
> Yes, that would be great.
> 
> Kind Regards,
> Alexander
> 
> -------------- sample code --------------
> #include <iostream>
> 
> #include <boost/multi_index_container.hpp>
> #include <boost/multi_index/ordered_index.hpp>
> #include <boost/multi_index/sequenced_index.hpp>
> 
> #include <boost/graph/adjacency_list.hpp>
> 
> using namespace boost;
> using namespace boost::multi_index;
> 
> using namespace std;
> 
> template<class Index>
> struct MICSelector
> {
>  typedef Index index;
> };
> 
> struct Item
> {
>  Item(int _a=0, int _b=0, int _c=0)
>  : a(_a), b(_b), c(_c) {}
> 
>  int a,b,c;
> 
>  friend std::ostream& operator<<
>    (std::ostream& os, const Item& item)
>  {
>    return os << " a: " << item.a <<
>          " b: " << item.b << " c: " <<
>          item.c << " ";
>  }
> };
> 
> struct ItemHolder
> {
>  ItemHolder(int id=0, const Item item=Item())
>  : m_ID(id), m_item(item) {}
> 
>  int  m_ID;
>  Item m_item;
> 
>  friend std::ostream& operator<<
>    (std::ostream& os, const ItemHolder& item)
>  {
>    return os << " ID: " << item.m_ID
>          << " Item( " << item.m_item  << ") ";
>  }
> };
> 
> struct ItemHolderKey
> {
>  typedef int result_type;
>  int operator()(const ItemHolder& v) const  { return v.m_ID; }
> 
>  template<class P, class Derived, class Config, class Base>
>  int get_int(const P& p, const adj_list_impl<Derived, Config, Base>&)
> const;
> 
>  template<class P>
>  int operator()(const typename P& p) const;
> };

The problem with your approach to implementing this
oeprator() is that you've got a circular dependency
between ItemHolderKey, which is nasty to say the least.
Since you're hacking your way through this, I guess
you won't mind relying on just another undocumented
feature to solve this in a nicer manner. Reviewing the
BGL source, seems like the container is not instantiated
with void*s but rather with the actual stored_vertex pointer.
stored_vertex must be one of the following types:

boost::graph::detail::adj_list_gen<...>::config::seq_stored_vertex;
boost::graph::detail::adj_list_gen<...>::config::bidir_seq_stored_vertex
;
boost::graph::detail::adj_list_gen<...>::config::rand_stored_vertex;
boost::graph::detail::adj_list_gen<...>::config::bidir_rand_stored_verte
x;

So you just can provide overloads for all of them and
get rid of the "static MG m" dependency and the get_int() memfun:

template <class Graph, class VertexListS, class OutEdgeListS,
          class DirectedS, class VertexProperty, class EdgeProperty, 
          class GraphProperty, class EdgeListS>
int operator()(
  const 
boost::graph::detail::adj_list_gen<...>::config::seq_stored_vertex* p) 
const
{
  return p->m_property.m_value.m_ID;
}

//etc for the other stored_vertex types

See what I mean? You can even do better and provide
an adaptor that takes a general key extractor and performs
the surgery:

template<typename KeyExtractor>
struct from_adjacency_list: private KeyExtractor
{
  typedef KeyExtractor::result_type result_type;

  // we forward to KeyExtractor for the general case
  template<typename Value>
  const result_type& operator()(const Value& v)
  {
    return KeyExtractor::operator()(v);
  }

  // overloads for the various stored_vertex types
  template <class Graph, class VertexListS, class OutEdgeListS,
            class DirectedS, class VertexProperty, class EdgeProperty, 
            class GraphProperty, class EdgeListS>
  const result_type& operator()(
    const 
boost::graph::detail::adj_list_gen<...>::config::seq_stored_vertex* p) 
const
  {
    return KeyExtractor::operator()(p->m_property.m_value);
  }

  // etc
};

Now you can use this adaptor in a fairly general way:

// No need to define ItemHolderKey.
// No dependecies from the particular adjacency_list you're
// instantiating.
typedef indexed_by
<
  sequenced<>,
  ordered_unique<
    from_adjacency_list<member<ItemHolder,int,&ItemHolder::m_ID> >
  >
  // and other indices
> Index;

I haven't actually tried this, but I think it should work and
provide with a much more comfortable way to define your
embedded MICs.

[...]
> It is correct that I use undocumented features of BGL to
> fuse MIC and BGL. OTOH, it is the way how std::list,
> std::vector etc. are used. It would be a surprise if it
> is gonna change. One could say that it is
> documentation issue, rather then the code.

Well, the thing should work but won't be surprised if
everthing goes to heck when ugrading to Boost 1.3x.
As for this being a documentation issue, I'm afraid
too much detail is relied on to think realistically
BGL authors will concede to open it to the public.

A most viable solution (applicable not only to
MIC but also to any other container) would be
to have a graph class modeled after adjacency_list
with the following aspect:

template<
  typename ElementType,
  typename EdgeList,
  typename VertexList,
   ...
>
element_adjacency_list;

so that it guarantees that the edge container is
instantiated with elements of type ElementType*.
This is not very hard to achieve if the actual
stored_vertex is defined like this:

template<typename ElementType>
struct element_pointer
{
  ElementType* ptr;
};
template<typename ElementType,...>
struct stored_vertex: public element_pointer<ElementType>
{
  // rest of the payload (properties, pointer to edge list, etc.
};

// from stored_vertex* to ElementType*

stored_vertex<...>* sv;
ElementType* ptr=sv->ptr;

// from ElementType* to stored_vertex
// this is portable!

ElementType* ptr;
element_pointer<ElementType>* eptr=
  reinterpret_cast<element_pointer<ElementType>*>(
    reinterpret_cast<char*>(ptr)-
    offsetof(element_pointer<ElementType>,ptr)
  );
stored_vertex<...>* sv=static_cast<stored_vertex<...>*>(eptr);

Implementing this should be mostly cut&paste from the
original adjacency_list, so, who knows, maybe you can
convince BGL authors to do it :)

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo