Boost logo

Boost :

From: Me Here (rhjrjlbk2002_at_[hidden])
Date: 2005-02-01 07:48:43


Dear All,

Thank you for your support!

I succeed to attach BGL to multi_index_container
(MIC). You can find the code below. In addition to
compilation and linking, it also almost works :-).

Unfortunately, I met following problems:

1) Indexers used in "indexed_by" by MIC can do
reasonable job if they get input more sinsible
then "void* cont&". See my comments in ItemHolderKey.

2) to use additional indices of MIC I use public
visibility of m_vertices member. That is not good and
should hidden somehow, e.g. with a functions
like "put" and "get"

3) Ignoring item 2, to be able to use additional
indices in m_vertices, its type should be available
outside somehow. For this test program, I just hope
the keys are always found in the container. Real life
is different. I also commented this in the end of "main" function.

Probably, I should say why am I doing all that: I'm
not satisfied with vertex_descriptor being void* or
int because they are not stable enough. The former
breaks down if I copy the graph, the latter - if I
add or remove something.

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

struct ItemHolder
{
  ItemHolder(int id=0, const Item item=Item())
  : m_ID(id), m_item(item) {}

  int m_ID;
  Item m_item;
};

struct ItemHolderKey
{
  typedef int result_type;
  int operator()(const ItemHolder& v) const
  { return v.m_ID; }
  template<class P>
  int operator()(const typename P& p) const
  {
    // How can I convert
    // "void* const& p" to
    // "const ItemHolder& ih"?
    return 1;//(p);
  }
};

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

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

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:

  // It's important to be able to get the type of
  // mg.m_vertices out, to be able to to the
  // following:
  /*
  typedef MG::vertices_container::nth_index<1> Index;
  Index::type& idx = mg.m_vertices.get<1>();
  Index::iterator f = idx.find( key1 );
  if ( f != idx.end() )
  {
    MG::vertex_descriptor v1 =
        *mg.m_vertices.project<0>( f );

    depth_first_visit( mg, v1, ... );
  }

  // otherwise, we have to use as below:
  */

  MG::vertex_descriptor v1 =
        *mg.m_vertices.project<0>(
            mg.m_vertices.get<1>().find( key1 ) );

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk