Hi there,

...

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.

and thanks a lot for your answer! I looked at the new version you uploaded and it seems identical to the one I used before -- but, if I get you right, it is not the best idea to use the fibonacci heap, anyways. At the moment I search an unsorted linear list O(|V|) times -- so I would benefit from every other structure ... what would you suggest? Some standard binary heap? The mutable_queue looked good to me but this one is pending, too ...

Thanks again Florian

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. In the beginning I tried to push vertices to the heap when I assign a path cost to them, instead of pushing all vertices (having infinite path cost then anyways) before I start the relaxing stuff -- doing this I saw the same kind of behaviour. The output of the code below executing, e.g. *A* only, results in: showing the *un-sorted* vector 10 9 8 7 6 5 4 3 2 1 smallest element w[9] == 1 call pop changing w[5] == 5 to -1, update Q showing the *sorted* vector -1 2 3 4 2 3 10 10 10 Any help would be appreciated! Thanks in advance Florian // filling a vector w with n descending numbers int N = 10; vector<float> w; for (int t = 0; t < N; ++t) w.push_back(N-t); cout << "showing the *un-sorted* vector" << endl; for (int i = 0; i < N; ++i) cout << w[i] << endl; // declaring the head (taken from an example on the web) typedef indirect_cmp<float*,std::less<float> > ICmp; ICmp cmp(&w[0], std::less<float>()); fibonacci_heap<int, ICmp> Q(N, cmp); // pushing all of w's indices to the Q for (int i = 0; i < N; ++i) Q.push(i); // top/pop smallest element (this is the last one in w) cout << "smallest element w[" << Q.top() << "] == " << w[Q.top()] << endl; cout << "call pop" << endl; Q.pop(); // change some elements in w and update Q // *A* cout << "changing w[5] == " << w[5] << " to -1, update Q" << endl; w[5] = -1.; Q.update(5); // *B* // cout << "changing w[8] == " << w[7] << " to -7, update Q" << endl; // w[7] = -7.; // Q.update(7); // *C* // cout << "changing w[3] == " << w[3] << " to -5, update Q" << endl; // w[3] = -5.; // Q.update(3); // *D* // cout << "changing w[0] == " << w[0] << " to -5, update Q" << endl; // w[0] = -5.; // Q.update(0); // output the rest of w, sorted cout << "showing the *sorted* vector" << endl; while (Q.size() > 0) { cout << w[Q.top()] << endl; Q.pop(); }

Hi Aaron

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.

After doing some tests with the new code you committed I integrated it into my program. As far as I can see it seems to work perfectly well! Having an assessment routine computing dijkstra's shortest path nearly 4000 time on different graphs I get *exactly* the same results I got before with my old implementation -- just faster :) Thank you very much for your fast response this takes me a big step further. Best wishes Florian