Reason for causing Breakpoint

[fraC19]

Hey guys, I'm currently working with my friend on an assignment which we need to find the shortest path to each point by using prim's algorithm. And here is our work:

#include <iostream>
#include <fstream>
#include <stdio.h>
#include <limits.h>
#include <string>
#include <sstream>

using namespace std;

#define MAX_V 500

class adjMatrix {
public:
	int total_vertex = 0;
	int clusters;
	int adjmatrix[MAX_V][MAX_V];
	int* parent = new int[total_vertex];
	int* key = new int[total_vertex];
	bool* mstSet = new bool[total_vertex];
	void build_adjmatrix(ifstream &fin);
	void primMST();
	int minKey();
	void printMST();
};


int main()
{
	ifstream fin;
	adjMatrix adj;

	adj.build_adjmatrix(fin);
	adj.primMST();

	system("pause");
	return 0;
}

void adjMatrix::build_adjmatrix(ifstream &fin) {
	bool firstTrue = false;
	bool secondTrue = false;
	int max_vertex;
	int vi = 0;
	int vj = 0;
	int count = 0;
	string str;
	fin.open("1.txt");

	while (getline(fin, str)) {
		if (str != "" && !(firstTrue)) {
			stringstream stream(str);
			while (1) {
				int n;
				stream >> n;
				if (!stream) {
					break;
				}
				max_vertex = n;
				if (max_vertex > total_vertex) {
					total_vertex = max_vertex;
					max_vertex = 0;
				}
			}
		}
		else if (str == "" && !(secondTrue)) {
			getline(fin, str);
			firstTrue = true;
		}
		else if (str == "" && (secondTrue)) {
			firstTrue = false;
			getline(fin, str);
			stringstream stream(str);
			while (1) {
				int n;
				stream >> n;
				if (!stream) {
					break;
				}
				clusters = n;
			}
		}
		if (firstTrue) {
			secondTrue = true;
			vj = 0;
			stringstream stream(str);
			while (1) {
				int n;
				stream >> n;
				if (!stream) {
					break;
				}
				if (n == -999) {
					n = 0;
				}
				adjmatrix[vi][vj] = n;
				vj++;
			}
			vi++;
		}
	}
	total_vertex++;
	cout << "total vertex = " << total_vertex << "  clusters =" << clusters << endl;
	for (vi = 0; vi < total_vertex; vi++) {
		for (vj = 0; vj < total_vertex; vj++) {
			cout << adjmatrix[vi][vj] << " ";
		}
		cout << "\n";
	}
}

void adjMatrix::primMST()
{
	for (int i = 0; i < total_vertex; i++) {
		key[i] = INT_MAX;
		mstSet[i] = false;
	}

	key[0] = 0;
	parent[0] = -1;

	for (int count = 0; count < total_vertex - 1; count++) {
		int u = minKey();

		mstSet[u] = true;

		for (int v = 0; v < total_vertex; v++) {
			if (adjmatrix[u][v] && mstSet[v] == false && adjmatrix[u][v] < key[v]) {
				parent[v] = u;
				key[v] = adjmatrix[u][v];
			}
		}
	}
	printMST();
}

int adjMatrix::minKey()
{
	int min = INT_MAX;
	int min_index;

	for (int v = 0; v < total_vertex; v++) {
		if (mstSet[v] == false && key[v] < min) {
			min = key[v];
			min_index = v;
		}
	}
	return min_index;
}

void adjMatrix::printMST()
{
	printf("Edge   Weight\n");
	for (int i = 1; i < total_vertex; i++) {
		printf("%d - %d    %d \n", parent[i], i, adjmatrix[i][parent[i]]);
	}
}

For my part, I wrote code to handle the input file which looks like this:

1 2 3 4
0 2 3
0 1 3
0 1 2
0

0 3 4 5 2
3 0 2 4 -999
4 2 0 1 -999
5 4 1 0 -999
2 -999 -999 -999 0

2

And the rest are my friend's work. The output for our code seems to look corrected, but after we press any key to exist the execution, it pop up a message says there is a breakpoint for our code.
Can someone help us with this problem? Really appreciated!

[helios]

On lines 17 and 19 you create two arrays of size zero. All usages of these arrays cause undefined behavior.

If you need a growable sequence you should use std::vector instead.

[fraC19]

Thanks for the reply.
The problem is that our professor dose not allow us to use vector or anything provided by STL to this assignment. So is there any other solution for that?

[Ganado]

Darn, I was looking through the code and didn't spot the obvious :P

So since helios probably found the problem, just want to add that if you're in debug mode in visual studio, a break point can mean that runtime routines found heap corruption.
Since you're working with dynamic arrays (int* var = new int[...]), my initial guess was that you're going out of bounds in your array iterations. (which is in fact the problem)

If I compile with errors, note that you never use the variable "count" on line 45. Not sure if this is intentional.

Here's some other notes:

	while (1) {
		int n;
		stream >> n;
		if (!stream) {
			break;
		}
		max_vertex = n;
		if (max_vertex > total_vertex) {
			total_vertex = max_vertex;
			max_vertex = 0;
		}
	}

can be slightly shorted as

	int n;
	while (stream >> n) {
		max_vertex = n;
		if (max_vertex > total_vertex) {
			total_vertex = max_vertex;
			max_vertex = 0;
		}
	}

as well as in other similar places.

[fraC19]

Never mind!
I think I found the solution according to your reply.

Really thanks to you helios!

[fraC19]

Thanks Ganado!
My friend just told me that your code is much easier to read than mine.

[helios]

I recommend that you create a class that behaves like an automatically resized array, which is how you assumed new T[total_vertex] would behave when you wrote your code. I'll just give you the class declaration:

template <typename T>
class DynamicArray{
    T *data = nullptr;
    size_t size = 0;
public:
    DynamicArray() = default;

    //Sets element i of the array to value val. If the internal array is too small it grows it
    //and fills any intermediate elements with zeroes.
    //For example:
    //DynamicArray<int> a;
    //(a = [])
    //a.set(0,1);
    //(a = [1])
    //a.set(3, 2);
    //(a = [1, 0, 0, 2])
    void set(size_t i, const T &val);

    //Returns element i of the array. I recommend checking that the index is valid and
    //throwing an exception if it's not.
    const T &get(size_t i);
};

Remember that to "grow" an array you need to allocate a larger array and copy the contents of the old one to it, then release the old array.

[fraC19]

yea, I just came up with the same idea after reading your reply, which I've done before in my previous assignment.

Really appreciated!