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 13:55:33

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