[Boost-users] BGL: d_ary_heap_indirect duplicated values

Subject: [Boost-users] BGL: d_ary_heap_indirect duplicated values
From: David Doria (daviddoria_at_[hidden])
Date: 2012-09-03 10:56:17

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.

Here is a demo:

http://programmingexamples.net/wiki/CPP/Boost/BGL/IndirectPriorityQueue

It simply sets random priority values for every vertex, and pushes
them all into the queue. It then does exactly the same thing again.
You can see that some vertices appear twice in the queue at different
positions.

For example, vertex (3,0) occurs at position 0 in the queue, and again
at position 6. Of course the priority values that are output are the
same because the demo simply outputs the values that are currently in
the priority property map, but I guess I would expect the two
instances of a vertex to appear at back-to-back positions in the queue
(as it should have used their current value to sort the queue)?

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)?

Thanks,

David