On 3/17/06, Roman Dementiev <dementiev@ira.uka.de> wrote:
Hi,
I have found the bug. When a vertex is being moved to another bucket (degree reduces) the 'update' method of the bucket sorter is called. This method deletes the vertex from the bucket sorter and then pushes it back. However, during the deletion, the NEW degree of the vertex is used for calculations, and not the old degree value. This is wrong and leads to the wrong output I had reported.
My bug fix avoids using the 'update' method, instead it removes the vertex from the bucket sorter before the degree has been changed, and then reinserts the vertex again when the degree is updated.
Now, the (correct) order computed by the test looks like this:
Smallest-last vertex order: 2 6 5 1 9 7 4 3 10 0 13 11 8 12
Can anyone integrate this fix into the main trunk (diff file attached)?
Thank you
With best regards, Roman Dementiev
Hi Roman, Thanks so much for the bug fix. I've just integrated it. Can I add the test program you included in your original email to the BGL test suite? It doesn't look like we have a test for smallest_last_ordering.hpp at the moment. Aaron Windsor