Boost logo

Boost :

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

Boost list run by bdawes at, gregod at, cpdaniel at, john at