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-03 22:30:51

> One thing in there that might be an issue is that you change the priorities
> of multiple vertices without running update() on the queue for each one
> separately.  That may not work because the heap might get too far from
> satisfying the correct invariants.

I see what you're saying. Unfortunately that doesn't seem to do it
either. In this demo:
http://ideone.com/gfEMp

I update(vertex) the queue after each priority is changed, but the
output results in an unsorted (though correctly length 4) queue:

There are 0 items in the queue.
New priority for 0, 0 784
New priority for 1, 0 676
New priority for 0, 1 350
New priority for 1, 1 8
There are 4 items in the queue.
The priority queue is:
vertex: 0 0 priority: 784
vertex: 1 0 priority: 676
vertex: 0 1 priority: 350
vertex: 1 1 priority: 8
New priority for 0, 0 231
New priority for 1, 0 547
New priority for 0, 1 653
New priority for 1, 1 314
There are 4 items in the queue.
The priority queue is:
vertex: 0 0 priority: 231
vertex: 0 1 priority: 653
vertex: 1 0 priority: 547
vertex: 1 1 priority: 314

> If that isn't the issue, could you please post or send me the exact, raw
> contents of the heap data (the internal vector) and the related property
> maps (IndexInHeap, priorities) before and after push_or_update operations
> that don't work correctly?  The push_or_update function should do exactly
> what you are looking for, and so I'm surprised it isn't working correctly.
> Does the test at libs/graph/test/dijkstra_no_color_map_compare.cpp pass for
> you?

The test appears to pass (or at least the output is as follows):

------
Running dijkstra shortest paths test with 10 vertices and 500 edges

**** no errors detected
------

I tried to output the index_in_heap, but it seems to be garbage (I
just used get(index_in_heap, u)?):

http://ideone.com/uj2lM

produces:
vertex: 1 1 priority: 234 indexInHeap: 4294967295
vertex: 0 1 priority: 828 indexInHeap: 0
vertex: 0 0 priority: 260 indexInHeap: 0
vertex: 1 0 priority: 46 indexInHeap: 0

The container/vector you mentioned seems to be private - how would I
output its contents?

Can you reproduce the unsorted result using the demo code?

Thanks for your help,

David