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