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

From: Roman Dementiev (dementiev_at_[hidden])
Date: 2006-03-17 11:15:37

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

Roman Dementiev wrote:
> Hi,
> 
> I believe that boost::smallest_last_vertex_ordering has a bug. I tested 
> the implementation with the CVS version from today. This is one of the 
> graphs where it produces the wrong output:
> 
>     int n = 14;
> 
>         Edge edge_array[] = {
>                 Edge(0, 13),
>                 Edge(1, 5),
>                 Edge(1, 9),
>                 Edge(2, 6),
>                 Edge(3, 10),
>                 Edge(3, 4),
>                 Edge(7, 9),
>                 Edge(8, 12),
>                 Edge(11, 13)
>         };
> 
> The attached picture bad_graph.jpg (ignore the directions) is a drawing 
> of this graph. I have attached also a source file with a program that 
> computes a smallest-last vertex ordering. Its output:
> 
> 
> Smallest-last vertex order: 2 6 10 4 3 5 1 7 9 0 13 11 8 12
> 
> 
> The algorithm implementation removes nodes 12, then 8, 11, 12, 13, 0.
> But then it removes node 9 that has degree 2 at that moment, which is 
> wrong, because nodes with a smaller degree exist (nodes 10,4,2,6,7,5).
> 
> 
> Can anyone fix this bug?
> 
> 
> With best regards,
> Roman
> 
> 
> 
> 
> 
> 
> 
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost