Boost logo

Boost :

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

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>>
> 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
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,

-------------- 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>&)

  template<class P>
  int operator()(const typename P& p) const;

typedef indexed_by
    ,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 );
  v1 = *mg.m_vertices.project<0>(
    mg.m_vertices.get<1>().find( key ) );

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

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

Boost list run by bdawes at, gregod at, cpdaniel at, john at