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

Subject: Re: [boost] [graph] Efficiency of index map in dijkstra_shortest_paths
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2012-10-17 11:47:54

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.
>
> I am somewhat concerned about allocating arrays of the size of the graph
> (that has millions of vertices) over and over (hundred million or more times)
> when many scans will stop after hundreds of vertices. Note that filtering the
> graph is not an option, because the stopping condition is given by radius or
> number of scanned vertices, but you obviously don't know which vertices will
> be scanned.
>
> 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.

-- Jeremiah Willcock