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 11:22:57

On Wed, 5 Sep 2012, David Doria wrote:

>> std::vector elements are normally initialized to zero when they are created.  push() does ignore the values; push_or_update() needs them to be correct.
>
> But I am calling push() on every vertex first, right (so the automatic
> initialization shouldn't ever be seen by the update() )? And you are
> saying the queue expects them to be initialized to (size_t)(-1)? I
> tried initializing it explicitly:

Initialization is required only if you use push_or_update(), not push().

> http://ideone.com/OgWF6
>
> but the output is still really wacky:
>
> There are 0 items in the queue.
> Original priority for 0, 0 744
> Index added: 0
> Index added caller: 0
> Original priority for 1, 0 562
> Index added: 1
> Index added caller: 1
> Original priority for 0, 1 824
> Index added: 2
> Index added caller: 0 (THIS 0 SEEMS WRONG)
> Original priority for 1, 1 156
> Index added: 3
> Index added caller: 3
> There are 4 items in the queue.
> New priority for 0, 0 890
> New priority for 1, 0 851
> New priority for 0, 1 55
> New priority for 1, 1 284
> There are 4 items in the queue.
> vertex: 0 0 priority: 890 indexInHeap: 0  (THIS 0 SEEMS WRONG)
> vertex: 1 0 priority: 851 indexInHeap: 0  (THIS 0 SEEMS WRONG)
> vertex: 1 1 priority: 284 indexInHeap: 0  (THIS 0 SEEMS WRONG)
> vertex: 0 1 priority: 55 indexInHeap: 0  (THIS 0 SEEMS WRONG)

Elements being removed from the heap always have index 0 (see the 
definition of top() in d_ary_heap_indirect).  Remember that elements are 
moved around in the heap as insertions and deletions occur to maintain the 
heap invariants.  If you dump the raw index_in_heap_map data at any single 
point during program execution (without mutating the heap in the middle of 
printing), you should get consistent values.

> Sorry to be a pain, but I've stepped though all of this and can't
> figure out why the index_in_heap map isn't returning the same values
> inside and outside the loop, and zero for every vertex at the end of
> the program?

That's a side effect of elements moving around within the heap.

-- Jeremiah Willcock