Boost Graph Library — сбой в topological_sort с помощью remove_vertex
Следующий фрагмент кода вылетает в topological_sort с тем, что кажется повреждением. Может ли кто-нибудь определить в коде что-то, что может быть причиной этого? Или это вызывает ошибку в 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));
}
Обратный след от аварии выглядит следующим образом:
#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
Решение
Я считаю, что именно index_map вызывает вашу проблему. В соответствии с этот она должна отображать каждую вершину в целое число в диапазоне [0, num_vertices (g)) (от 0 до num_vertices — 1), а ваша — от 1 до num_vertices.
Что-то вроде этого работает нормально (игнорируя предупреждение о неиспользуемых переменных):
#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));
}
Другие решения
Других решений пока нет …