Re: [boost] [graph] Efficiency of index map in dijkstra_shortest_paths

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.