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

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2007-03-18 12:28:33

On 3/16/07, Florian Teichert <floteich_at_[hidden]> wrote:
>
> > Hi Florian,
> >
> > Do you have a few lines of code you could share that show the bug you're
> > seeing? I'd like to trace through and see what's going on...
> >
> ... sure! I inlined some test code for basic operations. Depending on
> the activated parts (*A* - *D*) I see all sorts of strange behaviour.
> Sorting could be just wrong, some elements are shown more than once
> (somewhere within the sequence, or like repeating the largest element in
> the end, as below). In some cases (I think when updating first or last
> elements of w) the program hangs.

<snip code>

Hi Florian,

Thanks for your test code - it was very helpful in fixing a few more bugs.
The fibonacci heap code is based very closely on Knuth's implementation
from "The Stanford GraphBase" - but he uses some bit-level tricks, a few
of which got lost in the translation.

I just committed a fix to HEAD that I hope clears up the remaining bugs. Will
you please pull it down and let us know? It would be great to have the
fibonacci heap working to compare against mutable_queue and relaxed_heap.

Regards,
Aaron