The fibonacci heap is behaving strange
Hi, 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 :) #include <iostream> #include <cstdlib> #include <vector> #include <boost/pending/Fibonacci_heap.hpp> #include <boost/pending/relaxed_heap.hpp> #include <boost/graph/graph_utility.hpp> #include <boost/pending/indirect_cmp.hpp> using namespace std; using namespace boost; int main(int argc, char *argv[]) { typedef indirect_cmp<unsigned*,std::less<unsigned> > ICmp; unsigned current; const unsigned N=5; vector<unsigned> w(N); ICmp cmp(&w[0], std::less<unsigned>()); Fibonacci_heap<unsigned, ICmp> Q(N, cmp); //relaxed_heap<unsigned, ICmp> Q(N, cmp); Q.push(0); current=Q.top(); cout << current << " "; Q.pop(); w[1]=180428938; Q.push(1); w[2]=84693088; Q.push(2); w[3]=168169277; Q.push(3); w[4]=171463691; Q.push(4); current = Q.top(); cout << current << " "; Q.pop(); w[3]=164976049; Q.update(3); w[4]=59651664; Q.update(4); current = Q.top(); cout << current << " "; Q.pop(); w[1]=71988538; Q.update(1); w[3]=118964142; Q.update(3); current = Q.top(); cout << current << " "; Q.pop(); w[3]=42423833; Q.update(3); current = Q.top(); cout << current << " "; Q.pop(); return EXIT_SUCCESS; }
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
Douglas Gregor 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 ...
This answer works for me. I'll just use the relaxed heap then. :) /Magnus Ekdahl
On 7/19/06, Douglas Gregor <doug.gregor@gmail.com> 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
"Aaron Windsor" <aaron.windsor@gmail.com> writes:
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.
IMO critical bug fixes like this one ought to be mirrored to the RC_1_34_0 branch, unless they're very likely to break regression tests. But of course Thomas W. gets final say. -- Dave Abrahams Boost Consulting www.boost-consulting.com
On Fri, 2006-12-15 at 08:47 -0500, David Abrahams wrote:
"Aaron Windsor" <aaron.windsor@gmail.com> writes:
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.
IMO critical bug fixes like this one ought to be mirrored to the RC_1_34_0 branch, unless they're very likely to break regression tests. But of course Thomas W. gets final say.
The Fibonacci heap is completely unused and has been broken for eons. It can't hurt the release at all to put this fix in. Cheers, Doug
participants (4)
-
Aaron Windsor -
David Abrahams -
Douglas Gregor -
Magnus Ekdahl