Re: [boost] [graph] PATCH for Re: A bug in smallest_last_vertex_ordering

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2006-03-18 12:37:30

On 3/17/06, Roman Dementiev <dementiev_at_[hidden]> 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