On Mon, Sep 3, 2012 at 1:55 PM, Jeremiah Willcock
On Mon, 3 Sep 2012, David Doria wrote:
I am using a d_ary_heap_indirect as a priority queue using a property map to store the priorities. However, I when I change the values in the priority property map and push vertices that are already in the queue into the queue again, it results in kind of an invalid state where the vertex appears in the queue twice at different positions.
If you want to update priorities, change the priority map then call "update" on the d_ary_heap_indirect.
Is there a way to replace a vertex in the queue when it is pushed instead of adding a second one? (like an std::set instead of the current behavior which is like std::multiset)?
You pass in an IndexInHeapMap -- you should be able to check that to determine whether to call "push" or "update". You can also look into the kind of logic that is in dijkstra_shortest_paths_no_color_map for whether to do insertions or updates in that context.
-- Jeremiah Willcock
Hi Jeremiah, 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-... I would really appreciate it if you could help clarify these things! As usual, I'll submit a demo once we figure out how to use this, so future users don't have the same problem. Thanks, David