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 06:54:15

On Oct 17 2012, Jeremiah Willcock wrote:

>On Wed, 17 Oct 2012, Jan Hudec wrote:
>
>> Hello,
>>
>> The dijkstra_shortest_paths function requires an index map that maps 
>> vertices to index in range [0, num_vertices(g)). However there are 
>> several practially important algorithms that requite 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?
>
>You can use an associative container (see associative_property_map). 
>Note that many graph types (such as adjacency_list with vecS as vertex 
>container) provide the vertex index map automatically, without actually 
>storing an array of indices.
>

I suppose that the real problem is not the index map. Because that is 
constant and can be re-used for each scan. The problem in my case was the 
property maps for vertex distance, color and predecessor. You could use 
associative property maps for those (be careful that you cannot use the 
named parameter version of dijkstra_shortest_paths() for this as it does 
not parse the color_map argument).

In my use case it was still more attractive to use array based property 
maps and re-initialize modified values after each scan.