Hi Aaron, Aaron Windsor wrote:
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?
sure
It doesn't look like we have a test for smallest_last_ordering.hpp at the moment.
I have noticed that that the implementation starts removing vertices with degree 1, assuming that there are no isolated vertices. Therefore for graphs with degree-zero vertices the computed ordering will be wrong. Starting from minimum_degree = 0 solves the problem. See the attached patch. With best regards, Roman