[graph] Efficiency of index map in dijkstra_shortest_paths
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? Thanks Jan -- Jan 'Bulb' Hudec <bulb@ucw.cz>
On Oct 17 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?
One strategy that you could follow is to allocate the arrays only once and after each application of the shortest path algorithm only re-initialize the vertices that have been changed. You could for instance make use of a visitor that keeps a list of all discovered vertices. To apply the dijkstra_shortest_path without initialization, use the dijkstra_shortest_paths_no_init function. Best wishes, Alex
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
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.
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>
On Oct 18 2012, Jan Hudec wrote:
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.
The detail::d_ary_heap takes a index_in_heap property map as parameter and template parameter. And, as far as I can tell, they don't need any initialization. You can therefore easily set up your own heaps to reuse the index_in_heap property map. The problem you would run into is that the dijkstra_shortest_paths() function does not take the priority queue as a parameter, so you would not be able to specify your own recycling heaps. You could however directly call the breadth_first_visit, which would only still require you to create bfs_visitors from your dijkstra_visitors, if you had any. Look at the code of dijkstra_shortest_path_no_init() to see how it's done. I hadn't thought of this and will adjust my own code to reuse the index_in_heap property_maps too. Thanks.
participants (3)
-
Alex Hagen-Zanker -
Jan Hudec -
Jeremiah Willcock