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.