Re: [boost] status of fibonnaci_heap and mutable_queue

From: David Abrahams (dave_at_[hidden])
Date: 2006-04-11 03:18:03

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.

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.

A couple years ago Jeremy and I had an argument because I couldn't
understand the need for this update operation (and its concommitant
inconveniences), whereas Jeremy, apparently, had never seen a Dijkstra
that didn't use it.  While I understand (or at least I eventually
understood at the time) how the update could save some computation,
not doing the update doesn't change the big-O performance of the
algorithm.  So I'm wondering if the library shouldn't have a version
of dijkstra that doesn't use the update... or, maybe better yet, if
update were a free function, maybe the library could provide a default
one that does nothing.

-- 
Dave Abrahams
Boost Consulting
www.boost-consulting.com