[boost] A bug in smallest_last_vertex_ordering

15 Mar 2006

      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;
}

[boost] A bug in smallest_last_vertex_ordering

Roman Dementiev