[boost] Re: Help needed with BGL & multi_index_container

From: Joaquin M Lopez Munoz (joaquin_at_[hidden])
Date: 2005-02-01 17:51:12

Me Here <rhjrjlbk2002 <at> yahoo.com> writes:

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

Amazing! 

I see  you're relying in some non-documented
internal features of adjacency list to hack this togheter.
Is this correct? I've got some comments below trying to
elucidate what's going on, I'd appreciate your comments
about them.

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

See my comments at the end of the post.

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

I don't get this. Care to elaborate?

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

I guess the following suffices (no need to templatize
operator(), from what I see):

    int operator(void * p)const
    {
      return static_cast<ItemHolder*>(p)->m_ID;
    }

>   }
> };
> 
> typedef indexed_by
>   <
>     sequenced<>
>     ,ordered_non_unique< ItemHolderKey >
>     // and other indices
>   > Index;
> 
> typedef adjacency_list
>   < listS, MICSelector<Index>,
>     bidirectionalS, ItemHolder
>   > MG;

Here, seems like you're specifying ItemHolder as
a property so as to force adjacency_list to
use ItemHolder pointers as the vertex descriptors, right?
So, seems like the final vertex container is something
like

multi_index_container<
  void *,
  Index
>;

hence the solution to the ItemHolderKey problem
I proposed above.

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

What I understand it's going in this call is the following:

1. adjacency_list allocates (with new) a new property
element of type ItemHolder (using your initialization value.)
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.

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

OK, I think I got your point about the type of m_vertices
and agree with you. As you say, the nested
vertices_container typedef is not publicly documented.

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

Well, all in all I must say this is a glorious hack :)
IMHO, your concern about visibility of m_vertices
is negligible compared with the amounts of undocumented
features you're relying on --to name one, nobody guarantees
that vertex descriptors are really pointers to
property values, which is the key point of your technique.

Probably, the only sensible approach is to write from
scratch a graph-compliant structure that uses
multi_index_container, as adjacency_list is not designed
to work as you've forced it to. This is no small task,
compared with what you've got now.

That said, the thing seems to work and may suffice for your
purposes. It'd be great if some BGL expert (Jeremy?) jumped
in and comment on this.

Best,

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