A bug in smallest_last_vertex_ordering
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 #include <iostream> #include <boost/graph/adjacency_list.hpp> #include <boost/vector_property_map.hpp> #include <boost/graph/smallest_last_ordering.hpp> //#include <boost/graph/sequential_vertex_coloring.hpp> using namespace boost; typedef int Node; typedef std::pair<Node, Node> Edge; int main(int argc, char * argv[]) { typedef adjacency_list<listS, vecS, undirectedS> Graph; typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor; typedef graph_traits<Graph>::vertices_size_type vertices_size_type; typedef property_map<Graph, vertex_index_t>::const_type vertex_index_map; 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) }; int m = sizeof(edge_array) / sizeof(Edge); Graph g(edge_array, edge_array + m, n); std::cout <<"Number of nodes: "<<num_vertices(g) << std::endl; std::cout <<"Number of edges: "<<num_edges(g) << std::endl; std::vector<vertices_size_type> degree_vec(num_vertices(g)); std::vector<vertices_size_type> marker_vec(num_vertices(g)); vector_property_map<vertex_descriptor> order(num_vertices(g)); typedef iterator_property_map<vertices_size_type*, vertex_index_map> degree_i_map_type; iterator_property_map<vertices_size_type*, vertex_index_map> degree(°ree_vec.front(), get(vertex_index, g)); iterator_property_map<vertices_size_type*, vertex_index_map> marker(&marker_vec.front(), get(vertex_index, g)); typedef boost::detail::vertex_property_map<Graph, vertex_index_t>::type ID; typedef bucket_sorter<vertices_size_type, vertex_descriptor, degree_i_map_type, ID> BucketSorter; BucketSorter degree_bucket_sorter(n, n, degree, get(vertex_index, g)); smallest_last_vertex_ordering(g, order, degree, marker, degree_bucket_sorter); std::cout << "Smallest-last vertex order: "; for(int i=0;i<n;++i) std::cout << get(order,i) <<" "; std::cout << std::endl; return 0; }
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
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? It doesn't look like we have a test for smallest_last_ordering.hpp at the moment. Aaron Windsor
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
On 3/20/06, Roman Dementiev <dementiev@ira.uka.de> wrote:
Hi Aaron,
<snip>
Aaron Windsor wrote:
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
Roman, I just put the fix in for isolated vertices, but I'll have to wait until after the Boost 1.34 release branch to add the test. Thanks again for both. Aaron
participants (2)
-
Aaron Windsor -
Roman Dementiev