Boost Graph Library - crash in topological_sort with remove_vertex

Question

The following piece of code crashes in topological_sort with what appears to be corruption. Can anyone spot something in the code that could be causing this ? Or is it triggering a bug in BGL ?

#include <boost/graph/graph_traits.hpp>                                         
#include <boost/graph/adjacency_list.hpp>                                       
#include <boost/graph/topological_sort.hpp>                                     

using namespace boost;                                                          

typedef boost::adjacency_list <listS, listS, bidirectionalS,                    
        boost::property<boost::vertex_index_t, int > > Graph;                   
typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;                   
typedef boost::graph_traits<Graph>::edge_descriptor Edge;                       

int main(int,char*[])                                                           
{                                                                               
    Graph graph;                                                                
    std::list<Vertex> vertex_list;                                              
    typedef property_map<Graph, vertex_index_t>::type index_map_t;              
    index_map_t index_map = get(vertex_index, graph);                           
    Vertex a, b, c, d, e, f, g;                                                 
    graph_traits<Graph>::vertices_size_type current_index = 0;                  

    a = add_vertex(graph);                                                      
    index_map[a] = current_index++;                                             
    b = add_vertex(graph);                                                      
    index_map[b] = current_index++;                                             
    c = add_vertex(graph);                                                      
    index_map[c] = current_index++;                                             
    d = add_vertex(graph);                                                      
    index_map[d] = current_index++;                                             
    e = add_vertex(graph);                                                      
    index_map[e] = current_index++;                                             
    clear_vertex(a, graph);                                                     
    remove_vertex(a, graph);                                                    
    f = add_vertex(graph);                                                      
    index_map[f] = current_index++;                                             
    g = add_vertex(graph);                                                      
    index_map[g] = current_index++;                                             
    topological_sort(graph, std::front_inserter(vertex_list));                  
}                                                                               

Backtrace from the crash is as follows:

#0  0x00007ffff7538425 in raise () from /lib/x86_64-linux-gnu/libc.so.6
#1  0x00007ffff753bb8b in abort () from /lib/x86_64-linux-gnu/libc.so.6
#2  0x00007ffff757639e in ?? () from /lib/x86_64-linux-gnu/libc.so.6
#3  0x00007ffff7580b96 in ?? () from /lib/x86_64-linux-gnu/libc.so.6
#4  0x0000000000407e58 in boost::checked_array_delete<boost::default_color_type> (x=0x610290) at /usr/include/boost/checked_delete.hpp:41
#5  0x0000000000407d54 in boost::checked_array_deleter<boost::default_color_type>::operator() (this=0x6102c8, x=0x610290)
    at /usr/include/boost/checked_delete.hpp:63
#6  0x0000000000407f45 in boost::detail::sp_counted_impl_pd<boost::default_color_type*, boost::checked_array_deleter<boost::default_color_type> >::dispose (
    this=0x6102b0)
    at /usr/include/boost/smart_ptr/detail/sp_counted_impl.hpp:148
#7  0x0000000000401ab6 in boost::detail::sp_counted_base::release (
    this=0x6102b0)
    at /usr/include/boost/smart_ptr/detail/sp_counted_base_gcc_x86.hpp:145
#8  0x0000000000401b2f in boost::detail::shared_count::~shared_count (
    this=0x7fffffffe418, __in_chrg=<optimized out>)
    at /usr/include/boost/smart_ptr/detail/shared_count.hpp:305
#9  0x0000000000403786 in boost::shared_array<boost::default_color_type>::~shared_array (this=0x7fffffffe410, __in_chrg=<optimized out>)
    at /usr/include/boost/smart_ptr/shared_array.hpp:46
#10 0x00000000004037a0 in boost::shared_array_property_map<boost::default_color_type, boost::adj_list_vertex_property_map<boost::adjacency_list<boost::listS, boost::listS, boost::bidirectionalS, boost::property<boost::vertex_index_t, int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, int, int const&, boost::vertex_index_t> >::~shared_array_property_map (
    this=0x7fffffffe410, __in_chrg=<optimized out>)
    at /usr/include/boost/property_map/shared_array_property_map.hpp:19
#11 0x0000000000403997 in boost::depth_first_search<boost::adjacency_list<boost::listS, boost::listS, boost::bidirectionalS, boost::property<boost::vertex_index_t, int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, boost::topo_sort_visitor<std::front_insert_iterator<std::list<void*, std::allocator<void*> > > >, boost::graph_visitor_t, boost::bgl_named_params<int, boost::buffer_param_t, boost::no_property> > (g=..., params=...)
    at /usr/include/boost/graph/depth_first_search.hpp:298
#12 0x0000000000402e6f in boost::topological_sort<boost::adjacency_list<boost::listS, boost::listS, boost::bidirectionalS, boost::property<boost::vertex_index_t, int, boost::no_property>, boost::no_property, boost::no_property, boost::listS---Type <return> to continue, or q <return> to quit---
>, std::front_insert_iterator<std::list<void*, std::allocator<void*> > >, int, boost::buffer_param_t, boost::no_property> (g=..., result=..., params=...)
    at /usr/include/boost/graph/topological_sort.hpp:65
#13 0x00000000004024d6 in boost::topological_sort<boost::adjacency_list<boost::listS, boost::listS, boost::bidirectionalS, boost::property<boost::vertex_index_t, int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, std::front_insert_iterator<std::list<void*, std::allocator<void*> > > > (
    g=..., result=...) at /usr/include/boost/graph/topological_sort.hpp:71
#14 0x00000000004015c5 in main () at bgl_try.cc:40

Answer 1

I believe it is the index_map what causes your problem. According to this it should map each vertex to an integer in the range [ 0, num_vertices(g) ) (from 0 to num_vertices - 1) and yours goes from 1 to num_vertices.

Something like this works fine (ignoring the warning about unused variables):

#include <boost/graph/graph_traits.hpp>                                         
#include <boost/graph/adjacency_list.hpp>                                       
#include <boost/graph/topological_sort.hpp>  
#include <boost/graph/iteration_macros.hpp>                                   

using namespace boost;                                                          

typedef boost::adjacency_list <listS, listS, bidirectionalS,                    
        boost::property<boost::vertex_index_t, int > > Graph;                   
typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;                   
typedef boost::graph_traits<Graph>::edge_descriptor Edge;                       

int main(int,char*[])                                                           
{                                                                               
    Graph graph;                                                                
    std::list<Vertex> vertex_list;                                              
    typedef property_map<Graph, vertex_index_t>::type index_map_t;              
    index_map_t index_map = get(vertex_index, graph);                           
    Vertex a, b, c, d, e, f, g;                                                 

    a = add_vertex(graph);                                                      
    b = add_vertex(graph);                                                      
    c = add_vertex(graph);                                                      
    d = add_vertex(graph);                                                      
    e = add_vertex(graph);                                                      
    clear_vertex(a, graph);                                                     
    remove_vertex(a, graph);                                                    
    f = add_vertex(graph);                                                      
    g = add_vertex(graph);  

    graph_traits<Graph>::vertices_size_type current_index = 0;                  

    BGL_FORALL_VERTICES(v,graph,Graph)
        index_map[v]=current_index++;

    topological_sort(graph, std::front_inserter(vertex_list));  
}