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-23 19:04:41

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.