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