Help needed with BGL & multi_index_container
Hi there, I need an advanced container which allows me to access my data over number of different indices. That is exactly what for boost::multi_index_container was made. But, my data items also have relationships with other data in the same container, which could be represented as directed graph. So, I have made a custom container, which aggregates multi_index_container (MIC) to store data items and a graph (BGL) to store relationships. To allow switching from MIC to walk over relationships, as an additional field of my item in MIC I store BGL vertex; as vertex property in graph I store the key of unique index in MIC. So, MIC and BGL refer to each other. But, it is difficult to have those two containers in sync. So, I made another attempt to have MIC as customized vertex storage. I succeed two write the code for it (see it below). It also compiles and links :-). Unfortunately, I can not add neither vertices not edges. If I try to add vertex as in commeted code below, an error errors that there is no convertion from vertex property to vertex descriptor (error message is below). What's wrong? My another question is: how can I get access to my MIC stored in graph? I would like to use its indices. Best wishes, Alexander --------- sample code ----------- #include <iostream> #include <boost/multi_index_container.hpp> #include <boost/multi_index/ordered_index.hpp> #include <boost/graph/adjacency_list.hpp> using namespace boost; using namespace boost::multi_index; using namespace std; struct MICSelector {}; 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 ValueType> struct MICWrapper { typedef multi_index_container < ValueType, indexed_by < ordered_unique< ItemHolderKey > > > type; }; namespace boost { // the specialization for your selector template<class ValueType> struct container_gen<MICSelector, ValueType> { typedef typename MICWrapper<ValueType>::type type; }; template <> struct parallel_edge_traits<MICSelector> { typedef allow_parallel_edge_tag type; }; }; typedef adjacency_list < listS, MICSelector, bidirectionalS, ItemHolder > MG; int tmain(int argc, char* argv[]) { MG mg; /* ItemHolder IH( 1, Item(1) ); add_vertex( &IH, mg ); // add_edge( // ItemHolder( 1, Item(1) ), // ItemHolder( 2, Item(2) ), // mg ); */ cout << typeid( boost::graph_traits<MG>::vertex_descriptor ).name(); return 0; } --------- sample code ----------- ----------- error message ------------- Compiling... MIC_BGL.cpp c:\test\MIC_BGL.cpp(87) : error C2664: 'boost::add_vertex' : cannot convert parameter 1 from 'ItemHolder *__w64 ' to 'const boost::detail::adj_list_gen<Graph,VertexListS,OutEdgeListS,DirectedS,VertexProperty,EdgeProperty,GraphProperty,EdgeListS>::config::vertex_property_type &' with [ Graph=boost::adjacency_list<boost::listS,MICSelector,boost::bidirectionalS,ItemHolder>, VertexListS=MICSelector, OutEdgeListS=boost::listS, DirectedS=boost::bidirectionalS, VertexProperty=boost::detail::retag_property_list<boost::vertex_bundle_t,ItemHolder>::type, EdgeProperty=boost::detail::retag_property_list<boost::edge_bundle_t,boost::no_property>::type, GraphProperty=boost::no_property, EdgeListS=boost::listS ] Reason: cannot convert from 'ItemHolder *__w64 ' to 'const boost::detail::adj_list_gen<Graph,VertexListS,OutEdgeListS,DirectedS,VertexProperty,EdgeProperty,GraphProperty,EdgeListS>::config::vertex_property_type' with [ Graph=boost::adjacency_list<boost::listS,MICSelector,boost::bidirectionalS,ItemHolder>, VertexListS=MICSelector, OutEdgeListS=boost::listS, DirectedS=boost::bidirectionalS, VertexProperty=boost::detail::retag_property_list<boost::vertex_bundle_t,ItemHolder>::type, EdgeProperty=boost::detail::retag_property_list<boost::edge_bundle_t,boost::no_property>::type, GraphProperty=boost::no_property, EdgeListS=boost::listS ] No constructor could take the source type, or constructor overload resolution was ambiguous ----------- error message ------------- __________________________________ Do you Yahoo!? Yahoo! Mail - Find what you need with new enhanced search. http://info.mail.yahoo.com/mail_250
In the docs http://www.boost.org/libs/graph/doc/using_adjacency_list.html #sec:choosing-graph-type it says that the container must meet the requirements of Sequence or RandomAccessContainer. Does multi_index_container meet these requirements? Also, the operations that are needed go through boost/pending/container_traits, so you may need to overload some functions like push() for multi_index_container. Also, don't pass the address of the property into add_vertex, just pass by value. Cheers, Jeremy
Jeremy Siek ha escrito:
In the docs
http://www.boost.org/libs/graph/doc/using_adjacency_list.html #sec:choosing-graph-type
it says that the container must meet the requirements of Sequence or RandomAccessContainer. Does multi_index_container meet these requirements? Also, the operations that are needed go through boost/pending/container_traits, so you may need to overload some functions like push() for multi_index_container.
From the POV of adjacency_list, multi_index_container can work as a sequence if its first index is of type sequenced. But I think this is not the OP's intention. What he has in mind (I think) is having multi_index_container function as a vertex store for adjacency_list while presenting additional indices for the user's convenience. And I
Hi Jeremy, think this cannot be done (in a simple manner) because adjacency_list chooses internally the type of the vertices (namely, some integer type from what I've been able to see in the source code): normally, one would want to store richer elements than that. What is wanted is a way to pass a predetermined instantiation of multi_index_container so that adjcacency_list can use it as is. One of the difficulties is that add_vertex is not passed an element at all, instead adjacency_list creates it internally. The intended mode of usage resembles more the following: typedef multi_index_container< element_type, indexed_by< sequenced<>, // to be used by the BGL ... // other indices
multi_index_t;
typedef adjacency_list< vecS, // some way to have adjcaceny_list accept multi_index_t ...
graph_t:
multi_index_t mic; // populate mic graph_t g; // bind mic to g: g won't be mutable. // use BGL with g See what I mean? I don't know if I came any close to explain myself clearly :) The first index of multi_index_t would act as the vertex store of g, while at the same time the user can access the elements through all the indices defined. If Alexander (OP) does not agree with my analysis please tell me so. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
Also, don't pass the address of the property into add_vertex, just pass by value.
Cheers, Jeremy
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
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 --------------
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
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 ----------------
participants (6)
-
Alexander -
Jeremy Siek -
Joaquin M Lopez Munoz -
Joaquín Mª López Muñoz
-
Me here
-
Me Here