c++ - Segmentation fault when using prim_minimum_spanning_tree in boost

Question

I want to run prim on a graph from a file, but with certain inputs prim_minimum_spanning_tree gives me a segmentation fault. The segfault doesn't occur when i run it with valgrind, but valgrind indicates that there are errors ("Invalid read of size 8"), but it only shows them on certain graphs.

Im very new to using boost, and i suspect that i initialized the graph wrong.

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;

i tried to debug it with gdb, but i couldn't find the error...

---

Update: Thank you for your help!

I have finally found the bug: It wasn't with the readin function. The problem is that prim in boost doesn't work when the graph contains self cycles... (or atleast only then that error occurs)

From the boost Documentation: " The algorithm as implemented in Boost.Graph does not produce correct results on graphs with parallel edges."

I didn't think that a segfault is regarded as a "not correct result"...

Answer 1

Like the commenter said, fix your valgrind errors. Most likely you're doing stuff out-of-bounds in the readin function.

You are operating on far too many raw pointers. This is not C, so why pretend that it is?

Here's my take on it, without using manual allocation, and without potentially getting wrong bounds. Note that I make sure the input is unsigned so we don't get mixed-sign integer comparisons. This also makes half the input checks redundant:

//assert(s >= 0            && "zero source");
assert(s < num_vertices(G) && "numvertices source");
//assert(t >= 0            && "zero target");
assert(t < num_vertices(G) && "numvertices target");

Live On Wandbox

#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);
}

With input.txt based on the 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

Prints:

0 <--> 2 4
1 <--> 3 4 2
2 <--> 0 1 3
3 <--> 1 2 4
4 <--> 1 3 0

And runs completely clean under -fsanitize=undefined,address as well as valgrind. Also has no memory leaks:

==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)