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

From: Florian Teichert (floteich_at_[hidden])
Date: 2007-03-16 08:07:33

> 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();
    }