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