On Thu, Oct 18, 2012 at 11:54:15 +0100, Alex Hagen-Zanker wrote:
On Oct 17 2012, Jeremiah Willcock wrote:
On Wed, 17 Oct 2012, Jan Hudec wrote:
[...]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?
I propably chose the wrong words as "indices" might mean the vertex indices. No, I mean the data structure mapping vertex to it's position in the priority queue.
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).
I was primarily meaning the priority queue itself. The d-ary heap is an array of index descriptors and another array that maps vertex index to it's position in the queue. As this is internal to the algorithm, it's the most problematic to replace or reuse or anything.
In my use case it was still more attractive to use array based property maps and re-initialize modified values after each scan.
Yes, it might be. It does not matter how the memory gets saved or reused, but I want to apply it to the priority queue too. -- Jan 'Bulb' Hudec <bulb@ucw.cz>