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.