Неожиданная ошибка отрицательного веса ребра в boost::prim_minimum_spanning_tree

Следующий код выдает "отрицательный вес ребра" в prim_minimum_spanning_treecall, хотя я использую только положительные числа. Что нужно изменить, чтобы все заработало?

typedef boost::property<vertex_distance_t, int> VertexProperty;
typedef boost::property<edge_weight_t, int> EdgeProperty;
typedef adjacency_list<vecS, vecS, undirectedS, VertexProperty, EdgeProperty> Graph;

typedef pair<int, int> Edge;

Edge edges[] =      {Edge(0, 1), Edge(1, 2)};
int weights[] =     {2, 1}; // this works: int weights[] =   {1, 2}; 

Graph g(edges, edges + sizeof(edges)/sizeof(Edge), weights, 3);
std::vector<Graph::vertex_descriptor> predecessors(num_vertices(g));
boost::prim_minimum_spanning_tree(g, &predecessors[0]);

Примечание. Я могу добиться успеха, изменив значения веса.

Компилятор: MS Visual Studio 2010 C++ Boost версии: 1.54


c++ boost-graph
person alexm    schedule 17.08.2013    source источник
comment
Не похоже, чтобы они были, но, возможно, веса являются кумулятивными, поэтому любое снижение веса будет означать, что ребро имеет отрицательный вес? Очевидный тест: всегда ли это удается, если веса возрастают, и всегда ли они терпят неудачу, если они убывают?   -  person Jerry Coffin    schedule 17.08.2013
comment
@Jerry Coffin: Да, это чувствительно к порядку. Поскольку приведенный выше код правильно работает с версией boost 1.53, я склонен полагать, что это ошибка в последней версии boost (1.54).   -  person alexm    schedule 18.08.2013
comment
@alexm Я вижу, что вы уже сообщили об ошибке, и она была исправлено (невероятно быстро!).   -  person llonesmiz    schedule 18.08.2013

Ответы (1)


arrow_upward
0
arrow_downward

Это была ошибка Boost, и она уже исправлена: если кто-то еще увидит такое поведение начиная с 1.54, просто обновите до 1.55 или новее.

person LThode    schedule 06.11.2014