Re: [boost] [graph] Efficiency of index map in dijkstra_shortest_paths

Subject: Re: [boost] [graph] Efficiency of index map in dijkstra_shortest_paths
From: Jan Hudec (bulb_at_[hidden])
Date: 2012-10-18 09:54:09

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_at_[hidden]>