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