Reason for causing Breakpoint

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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#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
5
6
7
8
9
10
11
12
13
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!
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.
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?
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:
1
2
3
4
5
6
7
8
9
10
11
12
	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
1
2
3
4
5
6
7
8
	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.
Never mind!
I think I found the solution according to your reply.

Really thanks to you helios!
Thanks Ganado!
My friend just told me that your code is much easier to read than mine.
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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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.
yea, I just came up with the same idea after reading your reply, which I've done before in my previous assignment.

Really appreciated!

Registered users can post here. Sign in or register to post.