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:31:35

On Wed, 5 Sep 2012, David Doria wrote:

> On Wed, Sep 5, 2012 at 11:59 AM, Alex Hagen-Zanker <ahh34_at_[hidden]> wrote:
>> On 05/09/2012 16:14, David Doria wrote:
>>>
>>> but the output is still really wacky
>>
>>
>> I am not sure, but it appears that when you update the priority of a vertex,
>> it might just as well be an increased or a decreased priority.
>>
>> The algorithm on the other hand appears to expect that priorities only
>> increase.
>>
>> update() as well as push_or_update() only call
>> preserve_heap_property_up(index) and not preserve_heap_property_down(index).
>>
>> Again, I am not sure... do check.
>>
>> I would like the heap to remain copyable!
>>
>> Alex
>
> Ah, you got it! This code produces the problem repeatably:
> http://codepad.org/H2Mnqt8j
>
> (no randomness, the values that were producing an incorrect result are
> hard-coded). The output with the existing algorithm is:
>
> The priority queue is:
> vertex: 1 1 priority: 514
> vertex: 0 1 priority: 793
> vertex: 0 0 priority: 355
> vertex: 1 0 priority: 12
>
> Then I changed the update function from:
>
>      preserve_heap_property_up(index);
>
> to
>      preserve_heap_property_up(index);
>      preserve_heap_property_down();
>
> and ran it again. The output is now correct!:
>
> The priority queue is:
> vertex: 0 1 priority: 793
> vertex: 1 1 priority: 514
> vertex: 0 0 priority: 355
> vertex: 1 0 priority: 12
>
> Can we add a function that does this? In fact, the update() function
> seems like it could be renamed to increase_priority() or something,
> while the new function (with update up and down) would be just
> "update()". Thoughts?

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.  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.

-- Jeremiah Willcock