Re: [boost] [graph][heap][coroutine] interruptable dijkstra shortest path function

Subject: Re: [boost] [graph][heap][coroutine] interruptable dijkstra shortest path function
From: Alex Hagen-Zanker (ahh34_at_[hidden])
Date: 2012-09-24 06:31:34

On 24/09/2012 10:21, Rob Stewart wrote:
> On Sep 23, 2012, at 7:04 PM, Alex Hagen-Zanker <ahh34_at_[hidden]> wrote:
>
>> On 23/09/2012 17:25, Jeremiah Willcock wrote:
>>> On Sun, 23 Sep 2012, Tim Blechmann wrote:
>>>
>>>>> c. Boost.Heap mutable queues can be used with Boost.Graph via the named
>>>>> parameter interface. It doesn't help performance now,  but may be a good
>>>>> base for experimentation.
>>>> afaict, boost.heap should perform worse than the bgl heaps. its
>>>> implementation is much more generic, while bgl heaps are optimized by
>>>> assuming integer keys.
>>> Actually, the BGL heaps can use arbitrary keys, as long as there is a way to map them to integers (which might involve some other lookup table).
>>>
>>> -- Jeremiah Willcock
>>>
>> The main difference that I see is in the storage type that is used to get handles for values and to retrieve values from handles. The boost graph library typically uses an array of values (hidden in a shared_array_property_map) where the index in the array is the handle. That is possible because the number of values is limited by the number of vertices in the graph.
>>
>> Boost heap uses a std::list, where the handle is an iterator to an element in the list and the value is stored in the list. This makes sense because for Boost.Heap the number of values may be infinite, and an array for all values would explode.
>>
>> However, it also seems that a list provides more functionality and overhead than necessary as it keeps its values sorted. I would therefore expect that using an unordered list instead of a std::list would improve performance of boost.heap without sacrificing generality.
> Are you thinking of set/map versus unordered_set/map? list isn't sorted by default.
It is not sorted, but it is ordered. The iterators go through the 
elements in the same order that they are added to the list. For the sole 
purpose of handle fetching and retrieving that is not a necessary 
requirement. So there are is potential for some gains to be made 
(probably minute). In particular the insert() and erase() functions can 
be simpler.