-1

I was writing some code that converts a adjacency matrix into an adjacency list, and ran into a problem. I traced it down to a memory error, but when I step through with my debugger, it passes right over the error, and does not throw an exception. When the program runs without breakpoints, it throws the exception. I have a feeling it is due to heap corruption, but I'm no expert.

#include <string>
#include <limits>
#include <iostream>

using namespace std;

class NodeAM {
public:
    NodeAM() : v(0), weight(0), next(nullptr) {}
    NodeAM(int v1, double weight1) : v(v1), weight(weight1), next(nullptr) {}
    ~NodeAM() {}
    int v;
    double weight;
    NodeAM* next;
};

class matrix {
public:
    matrix();
    matrix(int m, int n);
    ~matrix();

    void setCurrentVertex(int u);
    void setAdjacencyMatrix(map* mapMatrix);
    void setDirectEdge(int u, int v, double w);

private:
    NodeAM** aMatrix;
    NodeAM** curr;
    int numVertices;
    int infinity = std::numeric_limits<int>::max(); //displayed as INF
};


matrix::matrix() {
    numVertices = 0;
}

matrix::matrix(int m, int n) {
    numVertices = m * n;
    aMatrix = new NodeAM * [n]; //n is columns
    curr = new NodeAM * [n];
    for (int i = 0; i < n; ++i) {
        aMatrix[i] = nullptr;
        curr[i] = nullptr;
    }
}

matrix::~matrix() {
    for (int i = 0; i < numVertices; ++i) {
        NodeAM* curr = aMatrix[i];
        while (curr) {
            NodeAM* next = curr->next;
            delete curr;
            curr = next;
        }
    }
    delete[] aMatrix;
    delete[] curr;
}

void matrix::setAdjacencyMatrix(map* mapMatrix) {
    double weightArr;

    for (int i = 0; i < numVertices; ++i) {
        for (int j = 0; j < numVertices; ++j) {
            if (mapMatrix->valueAt(i, j) != infinity) {
                weightArr = mapMatrix->valueAt(i, j);
                setDirectEdge(i, j, weightArr);
            }

        }
    }
}

void matrix::setDirectEdge(int u, int v, double w) {
    NodeAM* tmp = new NodeAM(v, w); //exception thrown when u is 22 and v is 23
    tmp->next = aMatrix[u];
    aMatrix[u] = tmp;
}

double map::valueAt(int row, int cols) {
    return adjMatrixCopy[row][cols];
}
/*
for the sake of not posting tons of code, adjMatrixCopy is an adjacency
matrix, which either has infinity as the edge or the edge weight (1, 4, 7, etc.) as
the edge, like this:

INF, INF, 7, 3, 7
INF, INF, 3, 7, 7
1, 9999, INF, 7, 3

In adjMatrixCopy, it is a 50 x 50 matrix similar to the one above
*/
JoshA328
  • 95
  • 6
  • Just because your program crashes in one particular place doesn't mean that's where the problem is. C++ does not work this way. The problem can be anywhere in the program that executed up to that point, except that the bug did not result in an immediate crash but the program continued to run up to this point, when it finally crashed due to "heap corruption". You need to show a [mre] that anyone else can cut/paste, ***exactly as shown***, compile, run, and reproduce their crash by themselves; until then it's unlikely that anyone will know the reason for the crash. – Sam Varshavchik May 09 '21 at 22:24
  • Where is the `map` type? – Moshe Rabaev May 09 '21 at 22:25
  • Your `matrix` destructor looks odd, you're using `delete[]` and `delete` on the same type? – Moshe Rabaev May 09 '21 at 22:27
  • `for (int i = 0; i < numVertices; ++i) { NodeAM* curr = aMatrix[i];` This doesn't look right. `aMatrix` only has `n` elements, not `n*m` elements – Igor Tandetnik May 09 '21 at 22:27
  • @IgorTandetnik thank you, that was the culprit. after looking at that in my constructor I realized that I am putting more memory values in the array than it could handle, hence the program crashing in a weird place. – JoshA328 May 09 '21 at 22:30

1 Answers1

0

The constructor should be

matrix::matrix() {
    numVertices = 0;
}

matrix::matrix(int m, int n) {
    numVertices = m * n;
    aMatrix = new NodeAM * [n*m]; //n is columns
    curr = new NodeAM * [n];
    currVert = new int[n];
    for (int i = 0; i < n; ++i) {
        aMatrix[i] = nullptr;
        curr[i] = nullptr;
    }
}

At aMatrix = new NodeAM* [n*m], the array should be the size of the adjacency matrix, in the case that it has to store every value of the matrix. This is why it throws a exception, because it doesn't have enough memory to hold the values of the adjacency matrix.

JoshA328
  • 95
  • 6