Re: [Boost-users] The fibonacci heap is behaving strange

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2006-12-14 21:37:53

On 7/19/06, Douglas Gregor <doug.gregor_at_[hidden]> wrote:
>
> On Jul 19, 2006, at 4:28 AM, Magnus Ekdahl wrote:
> > I put in 0,1,2,3,4 into a Fibonacci heap, manipulate some and get
> > 0,2,4,1,25
> > back. With the relaxed heap I get 0,2,4,1,3 back, which is as
> > expected with my
> > code. AFAIK this is due to a bug in the Fibonacci heap?
> >
> > Anyway here is code adopted from the cvs (fibonacci_heap.cpp) that
> > reproduces
> > the result on two different machines (intel/amd), where the
> > programs are
> > compiled using g++ 4.0.4. Any help in clearing out this confusing
> > result is
> > appreciated  :)
>
> Oh, yuck. The Fibonacci heap code has been sitting in "pending" for
> years; I never came forward for real acceptance as a Boost library.
>
> Actually, back when I was working on the relaxed heap code, I'd run
> into similar problems with the Fibonacci heap. I never bothered to
> debug the issue, because relaxed heaps are "supposed" to be faster.
>
> So, I don't have an answer for you, other than perhaps "don't use the
> Fibonacci" heap. We might just deprecate it for the upcoming Boost
> release and remove it thereafter, unless someone is willing to fix it
> and bring it forward. Sorry :(
>
>         Doug

Hi Magnus, Doug,

There was indeed a bug in the fibonacci heap code - the parent pointers
weren't being updated in the make_child function. I just committed a fix
for this to HEAD. I'd be grateful to hear from someone who has some
heavy-duty code using the relaxed heap as to whether or not the
fibonacci heap code works as a drop-in replacement now.

Regards,
Aaron