How to return structure array in C++

Question

So I've been trying to implement Kruskal's algorithm, first I want to make clear the question is not related to the implementation of the algorithm. I've created one graph.hpp file, one kruskalsAlgo.hpp and main.cpp as follows respectively:

#pragma once

struct Edge
{
    int source;
    int destination;
    int weight;
};

struct Graph
{
    int V;
    int E;

    Edge* edge;
};

Graph* create_graph(int V, int E)
{
    Graph* graph = new Graph;
    graph -> V = V;
    graph -> E = E;

    graph -> edge = new Edge[E];

    return graph;
}

#include <stdlib.h>
#include <tuple>

#include "../Graph/Graph.hpp"

class Kruskals_Algo
{
    private:
        struct subset
        {
            int parent;
            int rank;
        };

        void make_set(subset*, int);
        int find_set(subset*, int);
        void _union(subset*, int, int);
    
    public:
        Edge* kruskal(Graph*);
        void print_kruskals_MST(Edge*, int);
};

void Kruskals_Algo::make_set(subset* subsets, int V)
{
    subsets[V].parent = V;
    subsets[V].rank = 0;
}

int Kruskals_Algo::find_set(subset* subsets, int V)
{
    if(subsets[V].parent != V)
        subsets[V].parent = find_set(subsets, subsets[V].parent);
    
    return subsets[V].parent;
}

void Kruskals_Algo::_union(subset* subsets, int x, int y)
{
    int xroot = find_set(subsets, x);
    int yroot = find_set(subsets, y);

    if(subsets[xroot].rank < subsets[yroot].rank)
        subsets[xroot].parent = yroot;
    
    else if(subsets[xroot].rank > subsets[yroot].rank)
        subsets[yroot].parent = xroot;

    else
    {
        subsets[yroot].parent = xroot;
        subsets[xroot].rank++;
    }
}

inline int myComp(const void* a, const void* b)
{
    Edge* a1 = (Edge*)a;
    Edge* b1 = (Edge*)b;
    return a1 -> weight > b1 -> weight;
}

Edge* Kruskals_Algo::kruskal(Graph* graph)
{
    int V = graph -> V;
    Edge result[V];
    Edge* result_ptr = result;
    int e = 0;
    int i = 0;

    qsort(graph -> edge, graph -> E, sizeof(graph -> edge[0]), myComp);

    subset* subsets = new subset[(V * sizeof(subset))];

    for (int v = 0; v < V; ++v)
        make_set(subsets, v);

    while(e < V - 1 && i < graph -> E)
    {
        Edge next_edge = graph -> edge[i++];

        int x = find_set(subsets, next_edge.source);
        int y = find_set(subsets, next_edge.destination);

        if (x != y)
        {
            result[e++] = next_edge;
            _union(subsets, x, y);
        }
    }
    //return std::make_tuple(res, e);
    return result_ptr;
}

void Kruskals_Algo::print_kruskals_MST(Edge* r, int e)
{
    int minimumCost = 0;
    for(int i=0; i<e; ++i)
    {
        std::cout << r[i].source << " -- "
                  << r[i].destination << " == "
                  << r[i].weight << std::endl;
        minimumCost = minimumCost + r[i].weight;
    }
    
    std::cout << "Minimum Cost Spanning Tree: " << minimumCost << std::endl;
}

#include <iostream>

#include "Graph/Graph.hpp"

#include "Kruskals_Algo/kruskalsAlgo.hpp"
//#include "Prims_Algo/primsAlgo.hpp"

using namespace std;

class GreedyAlgos
{        
    public:
        void kruskals_mst();
        //void prims_mst();
};

void GreedyAlgos::kruskals_mst()
{
    Kruskals_Algo kr;
    int V;
    int E;
    int source, destination, weight;
    
    cout << "\nEnter the number of vertices: ";
    cin >> V;
    cout << "\nEnter the number of edges: ";
    cin >> E;
    
    Edge* res;

    Graph* graph = create_graph(V, E);

    for(int i=0; i<E; i++)
    {
        cout << "\nEnter source, destinstion and weight: ";
        cin >> source >> destination >> weight;
        graph -> edge[i].source = source;
        graph -> edge[i].destination = destination;
        graph -> edge[i].weight = weight;
    }

    //std::tie(result, E) = kr.kruskal(graph);
    res = kr.kruskal(graph);
    kr.print_kruskals_MST(res, E);
}

int main()
{
    int choice;
    GreedyAlgos greedy;
    greedy.kruskals_mst();
    
    return 0;
}

So my question here is when I debug the program the values in Edge result[V], which is a structure array, are calculated correctly, at position [0] [1] [2] as in the following picture:

but when the function print_kruskals_MST(res, E) is called from the main the values printed are different:

Is there any pointer thing that I'm doing wrong? Thanks in advance! P.S. Ignore the comments!

Marginally related: new subset[(V * sizeof(subset))] is rather suspicious. What's the sizeof for? new is not malloc, and new subset[V] will already allocate the right amount for V entries of type subset. — chi
– chi, Commented Apr 10, 2021 at 14:11
And when you used your debugger to run your program, one line at a time, and inspect the values of all objects, variables, and pointers, what did you see? — Sam Varshavchik
– Sam Varshavchik, Commented Apr 10, 2021 at 14:15

fritten · Accepted Answer · 2021-04-10 15:36:19Z

This answer might not answer your question directly but it should shed some light on the problem.

First of all, yes you have a lot of pointer problems...

Secondly, pair ANY use of the new operator with the delete operator. As it stands, you have a bunch of memory leaks.

Also, why create_graph? Create a constructor for Graph instead (and a destructor since the class has an Edge* edge it needs to take care of).

struct Graph
{
    int V;
    int E;

    Edge* edge;

    // constructor
    Graph(int V, int E)
    {
        this->V = V;
        this->E = E;
        this->edge = new Edge[E];
    }

    // destructor
    ~Graph()
    {
        // nullify the member variable before deleting its memory is just a safety measure pertaining to multithreading.
        Edge* _edge = this->edge;
        this->edge = nullptr;
        delete _edge;
    }
};

Then change Graph* graph = create_graph(V, E); into Graph* graph = new Graph(V, E); and do delete graph when you're done using it.

Make sure you remove all memory leaks and we can go on to discussing referencing the correct data (f.ex. by me changing my answer).

Collectives™ on Stack Overflow

How to return structure array in C++

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