[boost] Re: Help needed with BGL & multi_index_container

From: Alexander (rhjrjlbk2002_at_[hidden])
Date: 2005-02-02 14:38:48

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.

Replacement of "const P& p" to "void*" breaks VS 7.1.

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.

> 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 this
I 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;
};

typedef indexed_by
  <
    sequenced<>
    ,ordered_unique< ItemHolderKey >
    // and other indices
  > Index;

typedef adjacency_list
  <
    listS, MICSelector<Index>,
    bidirectionalS, ItemHolder
  > MG;

template<class P, class Derived, class Config, class Base>
int ItemHolderKey::get_int(const P& p,
    const adj_list_impl<Derived, Config, Base>&) const
{
  typedef adj_list_impl
      <Derived, Config, Base>::stored_vertex SV;
  SV* sv = reinterpret_cast<SV*>(p);
  return sv->m_property.m_value.m_ID;
}

template<class P>
int ItemHolderKey::operator()(const P& p) const
{
  static MG m;
  return get_int(p, m );
}

namespace boost
{
  // the specialization for your selector
  template<class Index, class ValueType>
  struct container_gen<MICSelector<Index>, ValueType>
  {
    typedef multi_index_container<ValueType,Index> type;
  };

  namespace graph_detail
  {
  // I think, it is kind of std::list
  struct MIC_tag :
    virtual public reversible_container_tag,
    virtual public back_insertion_sequence_tag
    { };

  template <class T,class I>
  MIC_tag container_category(
      const multi_index_container<T,I> &)
    { return MIC_tag(); }

  template <class T,class I>
  stable_tag iterator_stability(
      const multi_index_container<T,I> &)
    { return stable_tag(); }

  template <class T,class I>
  struct container_traits<
      typename multi_index_container<T,I> > {
    typedef MIC_tag category;
    typedef stable_tag iterator_stability;
  };
  }
};

int main(int argc, char* argv[])
{
  MG mg;

  MG::vertex_descriptor vd1 =
    add_vertex( ItemHolder( 1, Item(1) ), mg );

  MG::vertex_descriptor vd2 =
    add_vertex( ItemHolder( 2, Item(2) ), mg );

  add_edge( vd1, vd2, mg );

  int key1 = mg[vd1].m_ID;
  int key2 = mg[vd2].m_ID;

  // Store key1, key2 to use to different views over mg.
  // Those views are going to use those keys as follows:
  int key = key2;
  MG::vertex_descriptor v1;

  // It's important to be able to get the type of
  // mg.m_vertices out, to be able to to the following:
#if 0
  typedef multi_index_container<void* const,Index> MG_cont;
  typedef MG_cont::nth_index<1> Index;
  const Index::type& idx = mg.m_vertices.get<1>();
  Index::iterator f = idx.find( key );
  if ( f != idx.end() )
  {
    v1 = *mg.m_vertices.project<0>( f );
  }
#else
  v1 = *mg.m_vertices.project<0>(
    mg.m_vertices.get<1>().find( key ) );
#endif

  cout << mg[v1] << "\n";

  return 0;
}
------------ sample code ----------------