Boost logo

Boost :

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.

Boost list run by bdawes at, gregod at, cpdaniel at, john at