在 boost 中使用 prim_minimum_spanning_tree 时出现分段错误
Segmentation fault when using prim_minimum_spanning_tree in boost
我想 运行 从文件中提取图表，但某些输入 prim_minimum_spanning_tree 给我一个分段错误。
当我 运行 使用 valgrind 时，不会发生段错误，但 valgrind 指示存在错误（“大小 8 的无效读取”），但它仅在某些图表上显示它们。
我对使用 boost 很陌生，我怀疑我初始化图表有误。
std::pair<int,int> *edges = new std::pair<int,int>[num_edges];
double *weights = new double[num_edges];
// read edges and weights into arrays
readin(argc, argv, edges, weights);
typedef adjacency_list<vecS, vecS, undirectedS, no_property, property<edge_weight_t, mat_t>> Graph;
Graph G(num_nodes);
for(int i = 0; i < num_edges; i++){
// check input
assert(edges[i].first >= 0 && "zero first");
assert(edges[i].first < num_nodes && "numvertices first");
assert(edges[i].second >= 0 && "zero second");
assert(edges[i].second < num_nodes && "numvertices second");
// add edge
auto edge_iterator = add_edge( edges[i].first,edges[i].second, weights[i], G);
}
//create parent vector to store solution
std::vector<graph_traits<Graph>::vertex_descriptor> *parents =
new std::vector<graph_traits<Graph>::vertex_descriptor>(num_vertices(G));
//run prim
prim_minimum_spanning_tree(G, &(parents->at(0)));
delete parents;
delete[] edges;
delete[] weights;
我尝试用 gdb 调试它，但我找不到错误...
更新：
感谢您的帮助！
我终于找到了错误：它与 readin 函数无关。
问题是当图表包含自循环时，boost 中的 prim 不起作用......
（或者至少只有那时才会发生错误）
来自 boost 文档：
“Boost.Graph 中实现的算法不会在具有平行边的图形上产生正确的结果。”
我不认为段错误会被视为“不正确的结果”...
正如评论者所说，修复您的 valgrind 错误。您很可能在 readin 函数中做一些越界的事情。
您操作的原始指针过多。这不是C，为什么要假装是？
这是我的看法，没有使用手动分配，也没有可能出现错误的界限。请注意，我确保输入是无符号的，因此我们不会进行混合符号整数比较。这也使得一半的输入检查变得多余：
//assert(s >= 0 && "zero source");
assert(s < num_vertices(G) && "numvertices source");
//assert(t >= 0 && "zero target");
assert(t < num_vertices(G) && "numvertices target");
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/prim_minimum_spanning_tree.hpp>
#include <boost/graph/graph_utility.hpp>
#include <iostream>
#include <fstream>
using mat_t = double;
struct input { unsigned source, target; mat_t weight; };
static auto readin(std::string filename) {
std::vector<input> lines;
input line;
std::ifstream ifs(filename);
while (ifs >> line.source >> line.target >> line.weight) {
lines.push_back(line);
}
return lines;
}
int main() {
// read edges and weights into arrays
auto input = readin("input.txt");
using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, boost::no_property,
boost::property<boost::edge_weight_t, mat_t>>;
unsigned highest_vertex = 0;
for (auto [s,t,w]: input)
highest_vertex = std::max({highest_vertex, s, t});
Graph G(highest_vertex + 1);
for (auto [s,t,w]: input) {
//assert(s >= 0 && "zero source");
assert(s < num_vertices(G) && "numvertices source");
//assert(t >= 0 && "zero target");
assert(t < num_vertices(G) && "numvertices target");
// add edge
add_edge(s, t, w, G);
}
//create parent vector to store solution
std::vector<Graph::vertex_descriptor> parents(num_vertices(G));
//run prim
prim_minimum_spanning_tree(G, parents.data());
print_graph(G);
}
与input.txt基于documentation example:
0 2 0.1
1 3 0.1
1 4 0.2
2 1 0.7
2 3 0.3
3 4 0.1
4 0 0.1
打印：
0 <--> 2 4
1 <--> 3 4 2
2 <--> 0 1 3
3 <--> 1 2 4
4 <--> 1 3 0
并在 -fsanitize=undefined,address 和 valgrind 下完全干净地运行。也没有内存泄漏：
==9025== Memcheck, a memory error detector
==9025== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==9025== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==9025== Command: ./sotest
==9025==
0 <--> 2 4
1 <--> 3 4 2
2 <--> 0 1 3
3 <--> 1 2 4
4 <--> 1 3 0
==9025==
==9025== HEAP SUMMARY:
==9025== in use at exit: 0 bytes in 0 blocks
==9025== total heap usage: 46 allocs, 46 frees, 84,314 bytes allocated
==9025==
==9025== All heap blocks were freed -- no leaks are possible
==9025==
==9025== For counts of detected and suppressed errors, rerun with: -v
==9025== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
我想 运行 从文件中提取图表，但某些输入 prim_minimum_spanning_tree 给我一个分段错误。 当我 运行 使用 valgrind 时，不会发生段错误，但 valgrind 指示存在错误（“大小 8 的无效读取”），但它仅在某些图表上显示它们。
我对使用 boost 很陌生，我怀疑我初始化图表有误。
std::pair<int,int> *edges = new std::pair<int,int>[num_edges];
double *weights = new double[num_edges];
// read edges and weights into arrays
readin(argc, argv, edges, weights);
typedef adjacency_list<vecS, vecS, undirectedS, no_property, property<edge_weight_t, mat_t>> Graph;
Graph G(num_nodes);
for(int i = 0; i < num_edges; i++){
// check input
assert(edges[i].first >= 0 && "zero first");
assert(edges[i].first < num_nodes && "numvertices first");
assert(edges[i].second >= 0 && "zero second");
assert(edges[i].second < num_nodes && "numvertices second");
// add edge
auto edge_iterator = add_edge( edges[i].first,edges[i].second, weights[i], G);
}
//create parent vector to store solution
std::vector<graph_traits<Graph>::vertex_descriptor> *parents =
new std::vector<graph_traits<Graph>::vertex_descriptor>(num_vertices(G));
//run prim
prim_minimum_spanning_tree(G, &(parents->at(0)));
delete parents;
delete[] edges;
delete[] weights;
我尝试用 gdb 调试它，但我找不到错误...
更新： 感谢您的帮助！
我终于找到了错误：它与 readin 函数无关。 问题是当图表包含自循环时，boost 中的 prim 不起作用...... （或者至少只有那时才会发生错误）
来自 boost 文档： “Boost.Graph 中实现的算法不会在具有平行边的图形上产生正确的结果。”
我不认为段错误会被视为“不正确的结果”...
正如评论者所说，修复您的 valgrind 错误。您很可能在 readin 函数中做一些越界的事情。
您操作的原始指针过多。这不是C，为什么要假装是？
这是我的看法，没有使用手动分配，也没有可能出现错误的界限。请注意，我确保输入是无符号的，因此我们不会进行混合符号整数比较。这也使得一半的输入检查变得多余：
//assert(s >= 0 && "zero source");
assert(s < num_vertices(G) && "numvertices source");
//assert(t >= 0 && "zero target");
assert(t < num_vertices(G) && "numvertices target");
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/prim_minimum_spanning_tree.hpp>
#include <boost/graph/graph_utility.hpp>
#include <iostream>
#include <fstream>
using mat_t = double;
struct input { unsigned source, target; mat_t weight; };
static auto readin(std::string filename) {
std::vector<input> lines;
input line;
std::ifstream ifs(filename);
while (ifs >> line.source >> line.target >> line.weight) {
lines.push_back(line);
}
return lines;
}
int main() {
// read edges and weights into arrays
auto input = readin("input.txt");
using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, boost::no_property,
boost::property<boost::edge_weight_t, mat_t>>;
unsigned highest_vertex = 0;
for (auto [s,t,w]: input)
highest_vertex = std::max({highest_vertex, s, t});
Graph G(highest_vertex + 1);
for (auto [s,t,w]: input) {
//assert(s >= 0 && "zero source");
assert(s < num_vertices(G) && "numvertices source");
//assert(t >= 0 && "zero target");
assert(t < num_vertices(G) && "numvertices target");
// add edge
add_edge(s, t, w, G);
}
//create parent vector to store solution
std::vector<Graph::vertex_descriptor> parents(num_vertices(G));
//run prim
prim_minimum_spanning_tree(G, parents.data());
print_graph(G);
}
与input.txt基于documentation example:
0 2 0.1
1 3 0.1
1 4 0.2
2 1 0.7
2 3 0.3
3 4 0.1
4 0 0.1
打印：
0 <--> 2 4
1 <--> 3 4 2
2 <--> 0 1 3
3 <--> 1 2 4
4 <--> 1 3 0
并在 -fsanitize=undefined,address 和 valgrind 下完全干净地运行。也没有内存泄漏：
==9025== Memcheck, a memory error detector
==9025== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==9025== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==9025== Command: ./sotest
==9025==
0 <--> 2 4
1 <--> 3 4 2
2 <--> 0 1 3
3 <--> 1 2 4
4 <--> 1 3 0
==9025==
==9025== HEAP SUMMARY:
==9025== in use at exit: 0 bytes in 0 blocks
==9025== total heap usage: 46 allocs, 46 frees, 84,314 bytes allocated
==9025==
==9025== All heap blocks were freed -- no leaks are possible
==9025==
==9025== For counts of detected and suppressed errors, rerun with: -v
==9025== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)