Hi Alexander, ----- Mensaje original ----- De: Alexander <rhjrjlbk2002@yahoo.com> Fecha: Miércoles, Febrero 2, 2005 8:38 pm Asunto: [boost] Re: Help needed with BGL & multi_index_container

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.

I think I've got something, please read below.

Replacement of "const P& p" to "void*" breaks VS 7.1.

[...]

...

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

The problem with your approach to implementing this oeprator() is that you've got a circular dependency between ItemHolderKey, which is nasty to say the least. Since you're hacking your way through this, I guess you won't mind relying on just another undocumented feature to solve this in a nicer manner. Reviewing the BGL source, seems like the container is not instantiated with void*s but rather with the actual stored_vertex pointer. stored_vertex must be one of the following types: boost::graph::detail::adj_list_gen<...>::config::seq_stored_vertex; boost::graph::detail::adj_list_gen<...>::config::bidir_seq_stored_vertex ; boost::graph::detail::adj_list_gen<...>::config::rand_stored_vertex; boost::graph::detail::adj_list_gen<...>::config::bidir_rand_stored_verte x; So you just can provide overloads for all of them and get rid of the "static MG m" dependency and the get_int() memfun: template <class Graph, class VertexListS, class OutEdgeListS, class DirectedS, class VertexProperty, class EdgeProperty, class GraphProperty, class EdgeListS> int operator()( const boost::graph::detail::adj_list_gen<...>::config::seq_stored_vertex* p) const { return p->m_property.m_value.m_ID; } //etc for the other stored_vertex types See what I mean? You can even do better and provide an adaptor that takes a general key extractor and performs the surgery: template<typename KeyExtractor> struct from_adjacency_list: private KeyExtractor { typedef KeyExtractor::result_type result_type; // we forward to KeyExtractor for the general case template<typename Value> const result_type& operator()(const Value& v) { return KeyExtractor::operator()(v); } // overloads for the various stored_vertex types template <class Graph, class VertexListS, class OutEdgeListS, class DirectedS, class VertexProperty, class EdgeProperty, class GraphProperty, class EdgeListS> const result_type& operator()( const boost::graph::detail::adj_list_gen<...>::config::seq_stored_vertex* p) const { return KeyExtractor::operator()(p->m_property.m_value); } // etc }; Now you can use this adaptor in a fairly general way: // No need to define ItemHolderKey. // No dependecies from the particular adjacency_list you're // instantiating. typedef indexed_by < sequenced<>, ordered_unique< from_adjacency_list<member<ItemHolder,int,&ItemHolder::m_ID> >

// and other indices

Index;

I haven't actually tried this, but I think it should work and provide with a much more comfortable way to define your embedded MICs. [...]

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.

Well, the thing should work but won't be surprised if everthing goes to heck when ugrading to Boost 1.3x. As for this being a documentation issue, I'm afraid too much detail is relied on to think realistically BGL authors will concede to open it to the public. A most viable solution (applicable not only to MIC but also to any other container) would be to have a graph class modeled after adjacency_list with the following aspect: template< typename ElementType, typename EdgeList, typename VertexList, ...

element_adjacency_list; so that it guarantees that the edge container is instantiated with elements of type ElementType*. This is not very hard to achieve if the actual stored_vertex is defined like this: template<typename ElementType> struct element_pointer { ElementType* ptr; }; template<typename ElementType,...> struct stored_vertex: public element_pointer<ElementType> { // rest of the payload (properties, pointer to edge list, etc. }; // from stored_vertex* to ElementType* stored_vertex<...>* sv; ElementType* ptr=sv->ptr; // from ElementType* to stored_vertex // this is portable! ElementType* ptr; element_pointer<ElementType>* eptr= reinterpret_cast<element_pointer<ElementType>*>( reinterpret_cast<char*>(ptr)- offsetof(element_pointer<ElementType>,ptr) ); stored_vertex<...>* sv=static_cast<stored_vertex<...>*>(eptr); Implementing this should be mostly cut&paste from the original adjacency_list, so, who knows, maybe you can convince BGL authors to do it :) Joaquín M López Muñoz Telefónica, Investigación y Desarrollo