Re: [Boost-users] boost::graph issues.

From: Raindog (raindog_at_[hidden])
Date: 2008-08-18 19:33:43

David Abrahams wrote:
> on Mon Aug 18 2008, Raindog <raindog-AT-macrohmasheen.com> wrote:
>
>   
>>>> Because of the use of free functions, it's hard to quickly distinguish
>>>> "get" calls on a property_map from "get" calls on a
>>>> graph.     
>>>>         
>>> The use of the same name for both functions is an annoying design
>>> decision (partially my fault for encouraging it way back when), but I
>>> don't think using member functions would make a huge difference.  One of
>>> the reasons it's hard to understand is that the latter kind of "get" is
>>> just a special "convenience" feature of boost::graph::adjacency_list, so
>>> you can't really use it in generic algorithms, while the former is
>>> actually part of the property map concept.
>>>
>>> In any case, the use of free functions in generic libraries is essential
>>> for allowing the non-intrusive concept adaptation I mentioned above.
>>>       
>
> A small request: if you could leave a blank line between the text you're
> quoting and your newly-inserted stuff, it would greatly aid readability
> (for me).
>   

ok

>> Perhaps there is some lookup magic that I don't understand that
>> requires free functions.
>>     
>
> [snip]
>
> then you could easily and non-intrusively write these begin/end
> overloads:
>
>      template <class T, std::size_t N>
>      T const* begin(T (&a)[N]) { return a; }
>
>      template <class T, std::size_t N>
>      T const* end(T (&a)[N]) { return a + N; }
>
> and now builtin arrays satisfy the Container requirements and can be
> used with your algorithms.
>   

Ahh, this seems obvious now...

>   
>>>> Another example is the following:
>>>>
>>>>        get(vertex_color_t(), g, vertex(2,g))
>>>> [snip]
>> Secondly, it appears to have different semantics than using
>> get(property,graph); get(key,property); 
>>     
>
>
> How so?
>   

Because in the 3 argument get, you construct an object, in the 2 arg 
call that operates on a property_map, you pass in an enum.
>   
>> A key thing I find hard to
>> track is how expensive are these operations. It seems that some
>> properties can be stored and retrieved in O(1) space/time, yet others
>> are obviously more expensive to work with. 
>>     
>
> Generally speaking, property access should be at most O(log N).
>
>   
>> After going through the bgl documentation again
>>     

Meant to say that I had realized that I could have implemented a 
property_map and property that were O(1) in size/time

>>>> How does "BOOST_DEF_PROPERTY(edge,
>>>> index)" work exactly?
>>>>     
>>>>         
>>> My advice: don't ask.  I don't know the answer, but it doesn't inhibit
>>> my ability to use the library.
>>>
>>>   
>>>       
>> It inhibited my understanding of how to best go about creating my own
>> property.
>>     
>
> One problem you may be running into is that the BGL book hasn't been
> updated since bundled properties were added to the library.
>
> <schnipp>
>
>   
>> [snip]
>>
>> The reason I was unable to just "use" the bgl as you mentioned was
>> because of the performance issues I was having. I needed to know why
>> for example, so many copies of 400,000 element vectors were being
>> made, which required better understandings of the implementation
>> details of BGL.
>>     
>
> Nothing in the BGL that I know of would make *any* copies of vectors.
> If you need a paging structure like the one you described, you certainly
> don't want to use boost::graph::adjacency_list as your top-level graph
> structure, but you should be able to build a conforming model of the BGL
> graph concepts that does what you need and still works with the BGL
> algorithms.
>
>   

I believe now that the copies were created by calls to a* in that it 
apparently needed to create temporaries for whatever purpose, or perhaps 
it needed to create some separate lists in order to track visited nodes, 
either way, it was a very long pause in execution when under the debugger.

Thanks,
Josh