Re: [Boost-users] BGL: d_ary_heap_indirect duplicated values

Subject: Re: [Boost-users] BGL: d_ary_heap_indirect duplicated values
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2012-09-05 12:57:28

On Wed, 5 Sep 2012, David Doria wrote:

>> The heap's intention is to be used for Dijkstra's algorithm, where the
>> distances only decrease.  You might want to look at Boost.Heap as well,
>> since d_ary_heap_indirect is meant mostly for internal BGL use.
>
> The reason I was using d_ary_heap_indirect was for the "indirect"
> part. I want to store objects (vertices) in the priority queue, but
> prioritize them based on values in an external map (the
> PriorityMapType in my examples). From the documentation it doesn't
> look like Boost.Heap can do that
> (http://www.boost.org/doc/libs/1_51_0/doc/html/heap/concepts.html#heap.concepts.mutability)
> - am I missing it?
>
> (Also, Boost.Heap seems to have exactly the interface I was suggesting
> of an increase(), decrease(), and update() if you're not sure which of
> the two former functions to use.)

There is an indirect_cmp in the graph library; that might be usable with 
Boost.Heap.

>> If that
>> doesn't work, I can try putting in the update function you want as long as
>> it always correctly preserves the heap invariants.
>
> I don't know how we would prove that it always maintains the
> invariants, but it seems to make sense, right? It just (currently)
> goes up the queue, swapping if it is out of order, then goes down the
> queue (new addition), swapping if it is out of order.  If the first
> pass (_up() ) does find a reason to swap, then the down() pass would
> just do nothing (as the swapped item is guaranteed to be larger than
> any of the ones below the position of the item to update). If the up()
> pass does nothing, then the down() pass would work as normal.

I'll need to look into that issue further.

-- Jeremiah Willcock