Вы сталкиваетесь с проверками отладки итератора из MSVC.Это ХОРОШО, потому что в противном случае вы могли бы не знать об этом, и ваша программа имела бы (молчит?) Неопределенное поведение .
Теперь позвольте мне взглянуть на код.
Это выглядитподозреваемый:
double minEdgeWeight =
subGraph[*out_edges(u, subGraph).first].weight; // initialize minEdgeWeight to weight of first out edge
Это подразумевает неявное предположение, что u имеет хотя бы один исходящий фронт.это может быть правдой, но вы должны действительно проверить это.
Далее проверка с помощью UbSan :
/home/sehe/custom/boost_1_67_0/boost/graph/breadth_first_search.hpp:82:30: runtime error: load of value 3200171710, which is not a valid value for type 'boost::default_color_type'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /home/sehe/custom/boost_1_67_0/boost/graph/breadth_first_search.hpp:82:30 in
/home/sehe/custom/boost_1_67_0/boost/graph/breadth_first_search.hpp:83:13: runtime error: load of value 3200171710, which is not a valid value for type 'ColorValue' (aka 'boost::default_color_type')
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /home/sehe/custom/boost_1_67_0/boost/graph/breadth_first_search.hpp:83:13 in
/home/sehe/custom/boost_1_67_0/boost/graph/breadth_first_search.hpp:87:15: runtime error: load of value 3200171710, which is not a valid value for type 'ColorValue' (aka 'boost::default_color_type')
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /home/sehe/custom/boost_1_67_0/boost/graph/breadth_first_search.hpp:87:15 in
sotest: /home/sehe/custom/boost_1_67_0/boost/graph/two_bit_color_map.hpp:86: void boost::put(const two_bit_color_map<IndexMap> &, typename property_traits<IndexMap>::key_type, boost::two_bit_color_type) [IndexMap = boost::associative_property_map<std::map<void *, unsigned long, std::less<void *>, std::allocator<std::pair<void *const, unsigned long> > > >]: Assertion `(std::size_t)i < pm.n' failed.
Возможно, это хорошая идея для инициализации этой карты цветов.Я понятия не имею, относится ли это к вашему коду, потому что вы не включили соответствующий код ( снова ).
Поэтому я изменяю это:
struct VertexData {
vertex_descriptor pred;
double dist = 0, dist2 = 0;
boost::default_color_type color = {};
};
Нет, все та же ошибка.Читая код сейчас.
... 20 минут спустя.Ага.Вы копируете график в subGraph.Однако вы также передаете параметр u.Как это может быть правильно?Вершина u, скорее всего, , а не будет из subGraph.Вероятно, это еще один источник ошибки.
Давайте исправим это тоже:
msth(msth.vertex(2));
С новым участником доступа:
vertex_descriptor vertex(std::size_t n) const {
return boost::vertex(n, subGraph);
}
Достигнув вашего комментария
// Problem here; The problem has to do with removing vertices/edges and destabilizing the graph, thereby making
// it impossible to iterate through the graph
Становится довольно очевидно, что у вас была вершина u снаружи графика.Ничего о «дестабилизации» (это не то, как это работает. Итераторы иногда становятся недействительными, но из-за этого ничего не становится нестабильным: вы можете просто вызвать неопределенное поведение, если не будете осторожны).
По крайней мере, при передачедействительные u UbSan и ASan здесь не жалуются, что является хорошим признаком.Скорее всего, итераторы отладки вашего компилятора также не будут жаловаться.
Теперь обратите внимание:
listS делает не недействительными любые другиеитераторы на remove (это также в правилах аннулирования итераторов ).Очевидно, только удаленный.
m_goal страдает той же проблемой, что и u: вряд ли он может быть из правого графа, поскольку вы копируете весь граф
Несмотря на то, что remove делает недействительным только этот конкретный дескриптор вершины, похоже, вы пытаетесь сделать это внутри обратного вызова для поиска A *.Это вполне может сломать инварианты, принятые этим алгоритмом (я не проверял документацию, но вы должны это сделать! Опять же, это потому, что вы не показываете код, связанный с A *).
Ваш код все еще кажется разорванным, является ли Weight или нет, double.(Почему static_cast?)
Конечный результат
Это то, что я получил в итоге, включая различные очистки.
Live On Coliru
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/astar_search.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/prim_minimum_spanning_tree.hpp>
#include <boost/graph/graph_utility.hpp>
#include <iomanip>
#include <numeric>
typedef boost::adjacency_list_traits<boost::listS, boost::listS, boost::undirectedS>
GraphTraits; // to simplify the next definition
typedef GraphTraits::vertex_descriptor vertex_descriptor; // vertex descriptor for the graph
typedef GraphTraits::edge_descriptor edge_descriptor; // edge descriptor for the graph
typedef double Weight;
struct VertexData {
std::string name;
VertexData(std::string name = "") : name(std::move(name)) {}
//
vertex_descriptor pred {};
Weight dist = 0, dist2 = 0;
boost::default_color_type color = {};
friend std::ostream& operator<<(std::ostream &os, VertexData const &vd) {
return os << "{name:" << std::quoted(vd.name) << "}";
}
};
struct EdgeData {
Weight weight = 1;
};
typedef boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, VertexData, EdgeData>
MyGraphType; // graph type
class MST_Heuristic : public boost::astar_heuristic<MyGraphType, Weight> {
struct do_nothing_dijkstra_visitor : boost::default_dijkstra_visitor {};
auto make_index() const {
std::map<vertex_descriptor, size_t> m;
size_t n=0;
for (auto vd : boost::make_iterator_range(vertices(subGraph)))
m[vd] = n++;
return m;
}
public:
MST_Heuristic(MyGraphType g) : subGraph(g), firstRun(true) {}
Weight operator()(vertex_descriptor u) {
if (firstRun) {
auto idx = make_index();
dijkstra_shortest_paths(
subGraph, u,
get(&VertexData::pred, subGraph), // calculate the shortest path from the start for each vertex
get(&VertexData::dist2, subGraph),
get(&EdgeData::weight, subGraph),
boost::make_assoc_property_map(idx), std::less<Weight>(),
std::plus<Weight>(), std::numeric_limits<Weight>::infinity(), 0, do_nothing_dijkstra_visitor(),
get(&VertexData::color, subGraph));
}
Weight minEdgeWeight = std::numeric_limits<Weight>::max(); // initialize minEdgeWeight to weight of first out edge
for (auto ed : make_iterator_range(out_edges(u, subGraph))) {
minEdgeWeight = std::min(subGraph[ed].weight, minEdgeWeight); // find distance from nearest unvisited vertex to the current vertex
}
clear_vertex(u, subGraph);
remove_vertex(u, subGraph);
{
auto idx = make_index();
prim_minimum_spanning_tree(subGraph, vertex(0), // calculate the minimum spanning tree
get(&VertexData::pred, subGraph), get(&VertexData::dist, subGraph),
get(&EdgeData::weight, subGraph), boost::make_assoc_property_map(idx),
do_nothing_dijkstra_visitor());
}
//// combine
Weight MSTDist = 0.0;
Weight startDist = std::numeric_limits<Weight>::infinity();
for (auto vd : boost::make_iterator_range(vertices(subGraph))) // estimate distance to travel all the unvisited vertices
{
MSTDist += subGraph[vd].dist;
startDist = std::min(startDist, subGraph[vd].dist2);
}
firstRun = false;
return minEdgeWeight + MSTDist + startDist; // return the result of the heuristic function
}
vertex_descriptor vertex(std::size_t n) const {
return boost::vertex(n, subGraph);
}
private:
MyGraphType subGraph;
bool firstRun;
};
int main() {
MyGraphType g;
auto v1 = add_vertex({"one"}, g);
auto v2 = add_vertex({"two"}, g);
auto v3 = add_vertex({"three"}, g);
auto v4 = add_vertex({"four"}, g);
auto v5 = add_vertex({"five"}, g);
add_edge(v1, v2, g);
add_edge(v2, v3, g);
add_edge(v3, v4, g);
add_edge(v4, v5, g);
print_graph(g, get(&VertexData::name, g));
MST_Heuristic msth(g);
msth(msth.vertex(2));
}
Печать
one <--> two
two <--> one three
three <--> two four
four <--> three five
five <--> four