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-03 21:45:26

On Mon, 3 Sep 2012, David Doria wrote:

> I found a push_or_update(vertex) function of d_ary_heap_indirect that
> I thought would do the trick (it looks like it does the determining of
> whether to call push or update for us). Unfortunately, it does not
> behave as I would expect (it results in 7 items in the queue, not all
> of which are sorted). Neither does the update(vertex) function (there
> are only 4 items in the queue, but it is not sorted), and there does
> not appear to be a simply update() function like you recommended.
>
> I've detailed the outputs with each of these functions here:
> http://stackoverflow.com/questions/12251655/updating-priorities-in-a-boostd-ary-heap-indirect

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.

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?

-- Jeremiah Willcock