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

On Wed, 5 Sep 2012, David Doria wrote:

On Wed, Sep 5, 2012 at 11:59 AM, Alex Hagen-Zanker 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