[boost] A bug in smallest_last_vertex_ordering

From: Roman Dementiev (dementiev_at_[hidden])
Date: 2006-03-15 06:29:47

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(&degree_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;
}