Newer
Older
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 "ZeroVolumeSearch.h"
#include "testHelper_DisconnectedMatrix.h"
void test_detectConnectedComponents(int symmetric, int dummies, int colWeights);
int main(int argc, char **argv) {
printf("Test DetectConnectedComponents: ");
SetRandomSeed(111);
/*struct timeval tv;
gettimeofday(&tv,NULL);
unsigned long time_in_micros = 1000000 * tv.tv_sec + tv.tv_usec;
SetRandomSeed(time_in_micros);*/
test_detectConnectedComponents(FALSE, FALSE, FALSE);
test_detectConnectedComponents(TRUE, FALSE, FALSE);
test_detectConnectedComponents(FALSE, TRUE, FALSE);
test_detectConnectedComponents(TRUE, TRUE, FALSE);
test_detectConnectedComponents(FALSE, FALSE, TRUE);
test_detectConnectedComponents(TRUE, FALSE, TRUE);
test_detectConnectedComponents(FALSE, TRUE, TRUE);
test_detectConnectedComponents(TRUE, TRUE, TRUE);
printf("OK\n");
exit(0);
} /* end main */
/**
* Test DetectConnectedComponents()
*
* Input:
* symmetric : Whether the matrix should be symmetric
* dummies : Whether the matrix should contain dummy diagonal nonzeros
* colWeights : Whether the matrix should be weighted with column weights
*/
void test_detectConnectedComponents(int symmetric, int dummies, int colWeights) {
struct sparsematrix A;
struct opts Options;
SetDefaultOptions(&Options);
Options.SymmetricMatrix_UseSingleEntry = symmetric ? SingleEntYes : SingleEntNo;
/* In this function, we distinguish between the components we generate (calling them submatrices) and
* the components we detect (calling them just components), to make clean what we are dealing with.
*/
long i, I, cmpnnt, submat;
long numSubmatrices, *submatrix_m, *submatrix_n, *submatrix_weights, **i_to_I, **j_to_J;
ConstructDisconnectedMatrix(&A, symmetric, dummies, colWeights, 2, 5, &numSubmatrices, &submatrix_m, &submatrix_n, &submatrix_weights, &i_to_I, &j_to_J);
long maxWeight = 0;
for(submat=0; submat<numSubmatrices; ++submat) {
if(submatrix_weights[submat] > maxWeight) {
maxWeight = submatrix_weights[submat];
}
}
long numComponentsFound = 0;
long *componentWeightsFound = NULL;
long *rowAssignmentsFound = NULL;
/* Search for connected components (this should fail) */
if(DetectConnectedComponents(&A, maxWeight-1, &numComponentsFound, &componentWeightsFound, &rowAssignmentsFound, &Options)) {
printf("Error\n");
exit(1);
}
/* Search for connected components (this should succeed) */
if(!DetectConnectedComponents(&A, maxWeight, &numComponentsFound, &componentWeightsFound, &rowAssignmentsFound, &Options)) {
printf("Error\n");
exit(1);
}
/* Check number of components */
if(numComponentsFound != numSubmatrices) {
printf("Error\n");
exit(1);
}
/*for(cmpnnt=0; cmpnnt<numComponentsFound; ++cmpnnt) {
fprintf(stderr, "%ld ", submatrix_weights[cmpnnt]);
}fprintf(stderr, "\n");
for(cmpnnt=0; cmpnnt<numComponentsFound; ++cmpnnt) {
fprintf(stderr, "%ld ", componentWeightsFound[cmpnnt]);
}fprintf(stderr, "\n");*/
/* Check amount of nonzeros in each component */
long *component2submatrix = (long *)calloc(numSubmatrices, sizeof(long));
if (component2submatrix == NULL) {
printf("Error\n");
exit(1);
}
for(submat=0; submat<numSubmatrices; ++submat) {
int found = 0;
for(cmpnnt=0; cmpnnt<numComponentsFound; ++cmpnnt) {
if(component2submatrix[cmpnnt] == 0 && componentWeightsFound[cmpnnt] == submatrix_weights[submat]) {
component2submatrix[cmpnnt] = submat;
found = 1;
break;
}
}
if(!found) {
printf("Error\n");
exit(1);
}
}
/* Check all row assigments (check rowAssignmentsFound against i_to_I) */
long *component_m_found = (long*)calloc(numSubmatrices, sizeof(long));
if (component_m_found == NULL) {
printf("Error\n");
exit(1);
}
long submat_nnz;
for(I=0; I<A.m; ++I) {
submat = component2submatrix[rowAssignmentsFound[I]];
submat_nnz = submatrix_weights[submat];
/* Search whether the current row is actually part of the submatrix */
int found = 0;
for(i=0; i<submat_nnz; ++i) {
if(i_to_I[submat][i] == I) {
found = 1;
break;
}
}
if(!found) {
printf("Error\n");
exit(1);
}
++component_m_found[submat];
}
/* Check the obtained row counts */
for(submat=0; submat<numSubmatrices; ++submat) {
if(component_m_found[submat] != submatrix_m[submat]) {
printf("Error\n");
exit(1);
}
}
free(component2submatrix);
free(component_m_found);
free(componentWeightsFound);
free(rowAssignmentsFound);
DestructDisconnectedMatrix(&A, symmetric, dummies, colWeights, &submatrix_m, &submatrix_n, &submatrix_weights, &i_to_I, &j_to_J);
} /* end test_detectConnectedComponents */