Re: [boost] [pending] fibonacci_heap -- not working

From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2007-03-15 10:34:16

On Thu, 2007-03-15 at 12:52 +0100, Florian Teichert wrote:
> is there anybody out there using the fibonacci_heap.hpp?

Hopefully not :(

> I have a working implementation of dijkstra's shortest path algorithm
> and was trying to use fibonacci_heap from boost/pending to optimize its
> performance.
> To me it seems that it is not working properly. A key feature of this
> structure is that it should be possible to mix 'pop' and 'update' calls
> -- but, unfortunatly, after the first call to pop I get arbitrary
> indices from the heap. Some are even popped more than once.
> 
> I am using the most recent CVS version.

This unreviewed code has been languishing in Boost pending for years. I
was going to remove it, but hadn't done so yet. I see that Aaron Windsor
committed a fix to the RC_1_34_0 branch of CVS a few months ago: are you
using that Fibonacci heap? I've just put Aaron's fix into CVS HEAD as
well; an update might fix the problem you are seeing.

That said, a Fibonacci heap is unlikely to improve the performance of
Dijkstra's algorithm very much. It's asymptotically better than the
using a binary heap, but the operations themselves are more complicated.
More importantly, the operation that the Fibonacci heap is optimized
for--update--tends to happen only O(|V|) times in most classes of
graphs, so you don't get a win in the average case.

We've recently been experimenting with an implementation of a different
kind of priority queue for Dijkstra's algorithm, a multi-level bucket
data structure that only partially maintains the ordering property. The
papers we used as reference are:

  A. Goldberg. Shortest path algorithms: Engineering aspects. In  
  Proceedings of 12th International Symposium, ISAAC. Springer, 2001.

  A. Goldberg. A simple shortest path algorithm with linear average
  time. Technical report, STAR Lab., InterTrust Tech., Inc., 2001.
 
This data structure doesn't apply in all cases... it's limited to
traditional applications of Dijkstra's algorithm where one is using <
and + to order distances and accumulate distances, respectively, and
it's internal bit-twiddling means that it works best on built-in
integers and (through an extension) floats. That said, in some of our
test data--road maps of the USA, with ~24M vertices and ~58M edges--we
were getting results about 7x faster than with the current relaxed heap
implementation.

Our code isn't quite ready for inclusion in Boost. It needs to work with
more than built-in integers (that's all we handle now), needs wider
testing, and needs to be automatically enabled when the right
combination of parameters are provided to the existing Dijkstra's
algorithm. 

  Cheers,
  Doug