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