Re: [Boost-users] BGL: d_ary_heap_indirect duplicated values

Subject: Re: [Boost-users] BGL: d_ary_heap_indirect duplicated values
From: David Doria (daviddoria_at_[hidden])
Date: 2012-09-03 20:21:23

On Mon, Sep 3, 2012 at 1:55 PM, Jeremiah Willcock <jewillco_at_[hidden]> wrote:
> 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-ary-heap-indirect

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