Re: [boost] status of fibonnaci_heap and mutable_queue

From: Fernando Cacciola (fernando_cacciola_at_[hidden])
Date: 2006-04-11 13:11:55

Douglas Gregor wrote:
> On Apr 11, 2006, at 3:18 AM, David Abrahams wrote:
>
>> Doug Gregor <dgregor_at_[hidden]> writes:
>>
>>>> If I understand the propery maps library correctly, I'll need to
>>>> create a map, or hash_map, associating each and every possible
>>>> value
>>>> with an int, and wrap that into an associative_property_map<> to
>>>> input into the relaxed_heap DS.
>>>> Is that right?
>>>
>>> That sounds right.
>>
OK.

>> I don't have the context for this discussion (I'm on a plane right
>> now
>> and can't see back in time), but I'm going to hazard a wild guess
>> that
>> the need to index the nodes is due to the need for a priority queue
>> with an update() operation, and that is due to the fact that what
>> you're doing is based on dijkstra_shortest_paths.
>

Well, I don't know about Doug, but FWIW I need the update() for something 
else:

I'm implementing the Lindstrom-Turk triangulated surface mesh simplification 
algorithm.

This algorithm keeps the edges of the triangulation in a PQ based on some 
"collapsing cost" per edge, then it removes the edges as they are poped from 
the PQ. However, after each edge has been removed from the surface, the cost 
of the neighboring edges must be updated.

Of course this can done using set<> but IIUC the relaxed_heap is much more 
efficient.
Specially since I put in the heap not the edges themselves but explicitely 
indexed wrappers mapped from the actual edges via a hash map.
This way, each edge "actual" update is roughly O(1): get the wrapper from 
the edge via the hash_map (O(1)) and update the PQ (O(1) from Doug's report)
[plues the wrapper is needed anyway to keep other per-edge data used by the 
agorithm].

Best

Fernando Cacciola