Re: [boost] [BGL] bundled properties and their restrictions (particularly default constructibility).

Subject: Re: [boost] [BGL] bundled properties and their restrictions (particularly default constructibility).
From: Geoff Hilton (geoff.hilton_at_[hidden])
Date: 2008-10-29 16:01:04

Geoff Hilton wrote:
> Andrew Sutton wrote:
>>> This is just a bump of sorts, I'm still very much in need of a reply. 
>>> Note,
>>> in [2], I meant the boost.user list, not boost.devel.
>>>
>>
>> Geoff,
>>
>> Sorry I missed this, my mail filter didn't pick up the BGL subject...
>>
>> Given that a custom container selector may be created and push/erase 
>> must be
>>>> overloaded for the given custom container (for my purposes, this 
>>>> would be to
>>>> specify a custom allocator as in the example)[3], how safe would it 
>>>> be to
>>>> say that the container selector entirely dictates the restrictions in
>>>> question?
>>>>
>>>> If the answer is "very", presuming we weren't to change these 
>>>> restrictions
>>>> for existing provided selectors would it be possible for an explicit
>>>> exception to be made for custom containers and their selectors (created
>>>> using boost::container_gen<>)? This exception might say that the
>>>> restrictions in question are then dictated by the custom container.
>>>> I figure this shouldn't affect existing user code since the current
>>>> restrictions are already at their most strict.
>>>>
>>>> Thanks very much,
>>>> Geoff
>>>>
>> I'm not entirely sure what restrictions you're referring to with 
>> regard to
>> the selectors... that the containers within your bundled properties are
>> grown at run time (as with a list or vector) or fixed at compile time (as
>> with array)?
> 
> By restrictions I was referring to the requirements of bundled 
> properties as mentioned in my previous e-mails:
> 
>> I know the documentation requires that bundled properties be all of 
>> default  > constructible, assignable and copy constructible[1][2] 
>> because of 
> how the
>> containers (as specified by selectors) store them.
> 
> I realize now that using the word "restrictions" is probably what 
> confused you, sorry about that. When I said "as specified by selectors" 
> I was merely stating the fact that the containers that the 
> boost::adjacency_list uses are specified using the selectors.
> 
> The requirements imposed on the bundled properties exist because of 
> requirements imposed by the containers represented by the respective 
> selectors (vecS for std::vector, listS for std::list, etc) in the 
> boost::adjacency_list type parameters OutEdgeList, VertexList, and 
> EdgeList (see footnote 2 of previous e-mails).
> 
> My wanting to create a custom selector (an somewhat unrelated issue 
> which I was mentioning as a side note) for the purposes of specifying a 
> custom allocator are because the graphs can and will get quite large 
> (read: several gigabytes of RAM in size for relatively medium-sized 
> graphs), the custom allocator will help ease performance bottlenecks 
> through preallocation of large blocks of memory.
> 
>> In general, the selectors have a little to do with vertex/edge
>> properties (including bundles) as possible, so the impact on generic
>> algorithms is probably negligible - unless you're doing something
>> interesting like parallel or distributed graphs.
>> My feeling is that if you're considering building your own selector, then
>> you may be over-thinking the problem. Of course, I could also be 
>> completely
>> misunderstanding the point of your question. Is there any way to give an
>> example of what you're trying to do?
>>
>> Andrew Sutton
>> andrew.n.sutton_at_[hidden]
> 
> A simple example of how it is currently:
> 
> template<size_t Count>
> struct EdgeProperty
> {
>     boost::array<int,Count + 1> Weights;
> };
> 
> This approach respects all bundled property requirements, however the 
> number of weights must be known at compilation.
> 
> struct EdgeProperty
> {
>     EdgeProperty(size_t weightCount):Weights(weightCount + 1){}
> 
>     std::vector<int> Weights;
> };
> 
> This approach respects copy constructible and assignable, but not 
> default constructible. However the parameter passed in will never change 
> once it has been determined upon reading the graph information from the 
> file or database.
> 
> I don't know why I didn't think of this sooner, but something similar to 
> this should work for me:
> 
> struct EdgeProperty
> {
>     EdgeProperty():Weights(_count){}
>     std::vector<int> Weights;
>     static void SetInitialCount(size_t count)
>     {
>         _count = count;
>     }
> private:
>     static size_t _count;
> };
> 
> This is rather hacky in that our code would only work as long as 
> SetInitialCount is called once before the first EdgeProperty instance is 
> created but oh well, whatever works!
> 
> I think that renders my question/request moot, so never mind and thanks 
> for listening to my rambling thought process. :)

Oh, a further explanation on this bit:

 > The requirements imposed on the bundled properties exist because of
 > requirements imposed by the containers represented by the respective
 > selectors (vecS for std::vector, listS for std::list, etc) in the
 > boost::adjacency_list type parameters OutEdgeList, VertexList, and
 > EdgeList (see footnote 2 of previous e-mails).

Prior to thinking of the simple static function, the only thing I could 
think of to make sure that the container (called "Weights" in my 
examples) was the proper size was through the use of the first (current) 
  implementation using boost::array. Since I have something akin to the 
following defined:

template<size_t Count>
struct edge_prop_gen
{
typedef boost::property_map<Graph,
     boost::array<int, Count> EdgeProp::*>::type           edge_prop_t;
};
(where EdgeProp is the EdgeProperty struct, and Graph is the 
boost::adjacency_list<..>)

This meant that the arrays contained in the DistanceMap (among other 
things?) are properly sized automatically. Please correct me if I'm 
wrong, but if I understand correctly, is this what renders the bundled 
property subject to the requirements?