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

Subject: Re: [Boost-users] BGL: d_ary_heap_indirect duplicated values
From: David Doria (daviddoria_at_[hidden])
Date: 2012-09-05 12:29:15

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?

David