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

From: Roman Dementiev (dementiev_at_[hidden])
Date: 2006-03-20 05:20:11

Hi Aaron,

Aaron Windsor wrote:
> 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?

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