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