Bug in finding minimum spanning tree using Kruskal's algorithm

Question

I write the code from adding vertex into a graph and update the weight of edge and then find the minimum spanning tree. I think that I have done it but there seems to be some error in it but I cannot find it out.The system using Valgrind and indicate that "invalid write of size 4" and "invalid read of size 4 " in the call of MST, but I think it work fine.The whole error of Valgrind is https://docs.google.com/document/d/1_AhOdDkyZGNTBVHspyGtnSQoU1tYkm0nVA5UABmKljI/edit?usp=sharing

The following code is called by like

CreateNewGraph();
AddEdge(1, 2, 10);
AddEdge(2, 4, 10);
AddEdge(1, 3, 100);
AddEdge(3, 4, 10);
GetMST(mst_edges);

and the result will be (1,2) (2,4) (3,4).

and call

UpdateEdge(1, 3, 0.1);
GetMST(mst_edges);

and the result will be (1,2) (1,3) (2,4).

It is sent to a system to execute and it will be called like above but in a lot of time cycle above.

#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

namespace HOMEWORK{
    class Edge{
        public:
            Edge(unsigned int, unsigned int, double);
            unsigned int u;
            unsigned int v;
            double w;
        friend bool operator<(const Edge& a, const Edge& b){
         return a.w < b.w;
        }
    };
    Edge::Edge(unsigned int source = 0, unsigned int destination = 0, double weight = 0.0){
        u = source;
        v = destination;
        w = weight;
    }

    vector<Edge> graph(0);
    vector<int> parent(0);

    int findset(int x){
        if(x != parent[x])parent[x] = findset(parent[x]);
        return parent[x];
    }

    void CreateNewGraph(){
        graph.clear();
        parent.clear();
    }

    void AddEdge(unsigned int u, unsigned int v, double w){
        graph.push_back(Edge(u,v,w));
    }

    void UpdateEdge(unsigned int u, unsigned int v, double w){
        for(int i = 0; i < graph.size(); i ++){
            if(graph[i].u == u && graph[i].v == v)graph[i] = Edge(u,v,w);
        }
    }

    void GetMST(vector<pair<unsigned int, unsigned int> >& mst_edges){
        mst_edges.clear();
        parent.clear();
        int e = graph.size();
        for(int i = 0; i <= e + 1; i ++)parent.push_back(i);
        stable_sort(graph.begin(), graph.end());
        for(int i = 0; i < e; i ++){
            //cout << graph[i].u << ":" << graph[i].v << ":" << graph[i].w << ":" << parent[i + 1] << endl;
            int pu = findset(graph[i].u);
            int pv = findset(graph[i].v);
            if(pu != pv){
                parent[pu] = parent[pv];
                mst_edges.push_back(make_pair(graph[i].u, graph[i].v));
            }
        }
    }

    void Init(){
    }

    void Cleanup(){
    }
}

I suggest that you fire up your debugger. This is a critical tool for every aspiring programmer to learn. — Code-Apprentice
– Code-Apprentice, Commented Jun 25, 2013 at 1:15
In the Valgrind output, you have the file name and the line numbers of where the problem is. Look at that first. Or at least please indicate where in the source you provided that the problems are. — Some programmer dude
– Some programmer dude, Commented Jun 25, 2013 at 1:15
it says HOMEWORK::GetMST(std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > >&) (code.cpp:29)the line isn't the code and the above code seems right. — Jason
– Jason, Commented Jun 25, 2013 at 1:22
Also you might have potential access beyond the limits of the vector. For example in findset you access parent[x] without checking that x is a valid index. Incidentally it also happens to be line 29 if the code showed is the full file of code.cpp. — Some programmer dude
– Some programmer dude, Commented Jun 25, 2013 at 1:36

templatetypedef · Accepted Answer · 2013-06-25 01:39:55Z

I think the issue is how you're setting up parent pointers. Note that you've set up parents as

for(int i = 0; i <= e + 1; i ++) parent.push_back(i);

This creates one entry in the parent array for each edge in the graph, plus one extra one. However, each node has a parent, not each edge, and the number of nodes in a graph can be bigger than the number of edges plus one. For example, suppose you're given this set of edges:

1  2
3  4
5  6

This graph clearly has six nodes in it (numbered 1 ... 6), but your code would only make space for 4 entries in parents.

Try changing your code so that you set parents to be the proper size, probably by finding the maximum and minimum numbered node in the list of edges and sizing the array appropriately. Alternatively, consider using a std::unordered_map<int, int>, which is more flexible if the vertex numbers don't contiguously begin at 0.

Hope this helps!

Collectives™ on Stack Overflow

Bug in finding minimum spanning tree using Kruskal's algorithm

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related