
Boost : 
Subject: Re: [boost] [graph] Efficiency of index map in dijkstra_shortest_paths
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 20121017 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk