Boost logo

Boost :

Subject: Re: [boost] [graph] Efficiency of index map in dijkstra_shortest_paths
From: Alex Hagen-Zanker (ahh34_at_[hidden])
Date: 2012-10-18 12:41:36

On Oct 18 2012, Jan Hudec wrote:

>On Thu, Oct 18, 2012 at 11:54:15 +0100, Alex Hagen-Zanker wrote:
>> On Oct 17 2012, Jeremiah Willcock wrote:
>> >On Wed, 17 Oct 2012, Jan Hudec wrote:
>> >> [...]calculating shortest path trees with many times from each
>> >> vertex, but each tree only spanning small fraction of an otherwise
>> >> huge graph. [...] Is there an option to use associative container for
>> >> the queue indices? Or would it be useful to add it?
> I propably chose the wrong words as "indices" might mean the vertex
> indices. No, I mean the data structure mapping vertex to it's position in
> the priority queue.

The detail::d_ary_heap takes a index_in_heap property map as parameter and
template parameter. And, as far as I can tell, they don't need any
initialization. You can therefore easily set up your own heaps to reuse the
index_in_heap property map.

The problem you would run into is that the dijkstra_shortest_paths()
function does not take the priority queue as a parameter, so you would not
be able to specify your own recycling heaps.

You could however directly call the breadth_first_visit, which would only
still require you to create bfs_visitors from your dijkstra_visitors, if
you had any. Look at the code of dijkstra_shortest_path_no_init() to see
how it's done.

I hadn't thought of this and will adjust my own code to reuse the
index_in_heap property_maps too. Thanks.

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