1 /* -*- mode: C -*- */
2 /*
3 IGraph library.
4 Copyright (C) 2009-2012 Gabor Csardi <csardi.gabor@gmail.com>
5 334 Harvard st, Cambridge MA, 02139 USA
6
7 This program is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
11
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301 USA
21
22 */
23
24 #define NCOMPLEX /* to make it compile with MSVC on Windows */
25
26 #include <cs/cs.h>
27 #include <igraph.h>
28
permute(const igraph_matrix_t * M,const igraph_vector_int_t * p,const igraph_vector_int_t * q,igraph_matrix_t * res)29 int permute(const igraph_matrix_t *M,
30 const igraph_vector_int_t *p,
31 const igraph_vector_int_t *q,
32 igraph_matrix_t *res) {
33
34 long int nrow = igraph_vector_int_size(p);
35 long int ncol = igraph_vector_int_size(q);
36 long int i, j;
37
38 igraph_matrix_resize(res, nrow, ncol);
39
40 for (i = 0; i < nrow; i++) {
41 for (j = 0; j < ncol; j++) {
42 int ii = VECTOR(*p)[i];
43 int jj = VECTOR(*q)[j];
44 MATRIX(*res, i, j) = MATRIX(*M, ii, jj);
45 }
46 }
47
48 return 0;
49 }
50
permute_rows(const igraph_matrix_t * M,const igraph_vector_int_t * p,igraph_matrix_t * res)51 int permute_rows(const igraph_matrix_t *M,
52 const igraph_vector_int_t *p,
53 igraph_matrix_t *res) {
54
55 long int nrow = igraph_vector_int_size(p);
56 long int ncol = igraph_matrix_ncol(M);
57 long int i, j;
58
59 igraph_matrix_resize(res, nrow, ncol);
60
61 for (i = 0; i < nrow; i++) {
62 for (j = 0; j < ncol; j++) {
63 int ii = VECTOR(*p)[i];
64 MATRIX(*res, i, j) = MATRIX(*M, ii, j);
65 }
66 }
67
68 return 0;
69 }
70
permute_cols(const igraph_matrix_t * M,const igraph_vector_int_t * q,igraph_matrix_t * res)71 int permute_cols(const igraph_matrix_t *M,
72 const igraph_vector_int_t *q,
73 igraph_matrix_t *res) {
74
75 long int nrow = igraph_matrix_nrow(M);
76 long int ncol = igraph_vector_int_size(q);
77 long int i, j;
78
79 igraph_matrix_resize(res, nrow, ncol);
80
81 for (i = 0; i < nrow; i++) {
82 for (j = 0; j < ncol; j++) {
83 int jj = VECTOR(*q)[j];
84 MATRIX(*res, i, j) = MATRIX(*M, i, jj);
85 }
86 }
87
88 return 0;
89 }
90
random_permutation(igraph_vector_int_t * vec)91 int random_permutation(igraph_vector_int_t *vec) {
92 /* We just do size(vec) * 2 swaps */
93 long int one, two, i, n = igraph_vector_int_size(vec);
94 int tmp;
95 for (i = 0; i < 2 * n; i++) {
96 one = RNG_INTEGER(0, n - 1);
97 two = RNG_INTEGER(0, n - 1);
98 tmp = VECTOR(*vec)[one];
99 VECTOR(*vec)[one] = VECTOR(*vec)[two];
100 VECTOR(*vec)[two] = tmp;
101 }
102 return 0;
103 }
104
check_same(const igraph_sparsemat_t * A,const igraph_matrix_t * M)105 igraph_bool_t check_same(const igraph_sparsemat_t *A,
106 const igraph_matrix_t *M) {
107
108 long int nrow = igraph_sparsemat_nrow(A);
109 long int ncol = igraph_sparsemat_ncol(A);
110 long int j, p, nzero = 0;
111
112 if (nrow != igraph_matrix_nrow(M) ||
113 ncol != igraph_matrix_ncol(M)) {
114 return 0;
115 }
116
117 for (j = 0; j < A->cs->n; j++) {
118 for (p = A->cs->p[j]; p < A->cs->p[j + 1]; p++) {
119 long int to = A->cs->i[p];
120 igraph_real_t value = A->cs->x[p];
121 if (value != MATRIX(*M, to, j)) {
122 return 0;
123 }
124 nzero += 1;
125 }
126 }
127
128 for (j = 0; j < nrow; j++) {
129 for (p = 0; p < ncol; p++) {
130 if (MATRIX(*M, j, p) != 0) {
131 nzero -= 1;
132 }
133 }
134 }
135
136 return nzero == 0;
137 }
138
main()139 int main() {
140
141 igraph_sparsemat_t A, B;
142 igraph_matrix_t M, N;
143 igraph_vector_int_t p, q;
144 long int i;
145
146 /* Permutation of a matrix */
147
148 #define NROW 10
149 #define NCOL 5
150 #define EDGES NROW*NCOL/3
151 igraph_matrix_init(&M, NROW, NCOL);
152 igraph_sparsemat_init(&A, NROW, NCOL, EDGES);
153 for (i = 0; i < EDGES; i++) {
154 long int r = RNG_INTEGER(0, NROW - 1);
155 long int c = RNG_INTEGER(0, NCOL - 1);
156 igraph_real_t value = RNG_INTEGER(1, 5);
157 MATRIX(M, r, c) = MATRIX(M, r, c) + value;
158 igraph_sparsemat_entry(&A, r, c, value);
159 }
160 igraph_sparsemat_compress(&A, &B);
161 igraph_sparsemat_destroy(&A);
162
163 igraph_vector_int_init_seq(&p, 0, NROW - 1);
164 igraph_vector_int_init_seq(&q, 0, NCOL - 1);
165
166 /* Identity */
167
168 igraph_matrix_init(&N, 0, 0);
169 permute(&M, &p, &q, &N);
170
171 igraph_sparsemat_permute(&B, &p, &q, &A);
172 igraph_sparsemat_dupl(&A);
173
174 if (! check_same(&A, &N)) {
175 return 1;
176 }
177
178 /* Random permutation */
179 random_permutation(&p);
180 random_permutation(&q);
181
182 permute(&M, &p, &q, &N);
183
184 igraph_sparsemat_destroy(&A);
185 igraph_sparsemat_permute(&B, &p, &q, &A);
186 igraph_sparsemat_dupl(&A);
187
188 if (! check_same(&A, &N)) {
189 return 2;
190 }
191
192 igraph_vector_int_destroy(&p);
193 igraph_vector_int_destroy(&q);
194 igraph_sparsemat_destroy(&A);
195 igraph_sparsemat_destroy(&B);
196 igraph_matrix_destroy(&M);
197 igraph_matrix_destroy(&N);
198
199 #undef NROW
200 #undef NCOL
201 #undef EDGES
202
203 /* Indexing */
204
205 #define NROW 10
206 #define NCOL 5
207 #define EDGES NROW*NCOL/3
208 #define I_NROW 6
209 #define I_NCOL 3
210 igraph_matrix_init(&M, NROW, NCOL);
211 igraph_sparsemat_init(&A, NROW, NCOL, EDGES);
212 for (i = 0; i < EDGES; i++) {
213 long int r = RNG_INTEGER(0, NROW - 1);
214 long int c = RNG_INTEGER(0, NCOL - 1);
215 igraph_real_t value = RNG_INTEGER(1, 5);
216 MATRIX(M, r, c) = MATRIX(M, r, c) + value;
217 igraph_sparsemat_entry(&A, r, c, value);
218 }
219 igraph_sparsemat_compress(&A, &B);
220 igraph_sparsemat_destroy(&A);
221
222 igraph_vector_int_init(&p, I_NROW);
223 igraph_vector_int_init(&q, I_NCOL);
224
225 for (i = 0; i < I_NROW; i++) {
226 VECTOR(p)[i] = RNG_INTEGER(0, I_NROW - 1);
227 }
228 for (i = 0; i < I_NCOL; i++) {
229 VECTOR(p)[i] = RNG_INTEGER(0, I_NCOL - 1);
230 }
231
232 igraph_matrix_init(&N, 0, 0);
233 permute(&M, &p, &q, &N);
234
235 igraph_sparsemat_index(&B, &p, &q, &A, 0);
236
237 if (! check_same(&A, &N)) {
238 return 3;
239 }
240
241 /* A single element */
242
243 igraph_vector_int_resize(&p, 1);
244 igraph_vector_int_resize(&q, 1);
245
246 for (i = 0; i < 100; i++) {
247 igraph_real_t value;
248 VECTOR(p)[0] = RNG_INTEGER(0, NROW - 1);
249 VECTOR(q)[0] = RNG_INTEGER(0, NCOL - 1);
250 igraph_sparsemat_index(&B, &p, &q, /*res=*/ 0, &value);
251 if (value != MATRIX(M, VECTOR(p)[0], VECTOR(q)[0])) {
252 return 4;
253 }
254 }
255
256 igraph_sparsemat_destroy(&A);
257
258 for (i = 0; i < 100; i++) {
259 igraph_real_t value;
260 VECTOR(p)[0] = RNG_INTEGER(0, NROW - 1);
261 VECTOR(q)[0] = RNG_INTEGER(0, NCOL - 1);
262 igraph_sparsemat_index(&B, &p, &q, /*res=*/ &A, &value);
263 igraph_sparsemat_destroy(&A);
264 if (value != MATRIX(M, VECTOR(p)[0], VECTOR(q)[0])) {
265 return 4;
266 }
267 }
268
269 igraph_vector_int_destroy(&p);
270 igraph_vector_int_destroy(&q);
271 igraph_sparsemat_destroy(&B);
272 igraph_matrix_destroy(&M);
273 igraph_matrix_destroy(&N);
274
275 /* Indexing only the rows or the columns */
276
277 igraph_matrix_init(&M, NROW, NCOL);
278 igraph_sparsemat_init(&A, NROW, NCOL, EDGES);
279 for (i = 0; i < EDGES; i++) {
280 long int r = RNG_INTEGER(0, NROW - 1);
281 long int c = RNG_INTEGER(0, NCOL - 1);
282 igraph_real_t value = RNG_INTEGER(1, 5);
283 MATRIX(M, r, c) = MATRIX(M, r, c) + value;
284 igraph_sparsemat_entry(&A, r, c, value);
285 }
286 igraph_sparsemat_compress(&A, &B);
287 igraph_sparsemat_destroy(&A);
288
289 igraph_vector_int_init(&p, I_NROW);
290 igraph_vector_int_init(&q, I_NCOL);
291
292 for (i = 0; i < I_NROW; i++) {
293 VECTOR(p)[i] = RNG_INTEGER(0, I_NROW - 1);
294 }
295 for (i = 0; i < I_NCOL; i++) {
296 VECTOR(p)[i] = RNG_INTEGER(0, I_NCOL - 1);
297 }
298
299 igraph_matrix_init(&N, 0, 0);
300 permute_rows(&M, &p, &N);
301
302 igraph_sparsemat_index(&B, &p, 0, &A, 0);
303
304 if (! check_same(&A, &N)) {
305 return 5;
306 }
307
308 permute_cols(&M, &q, &N);
309 igraph_sparsemat_destroy(&A);
310 igraph_sparsemat_index(&B, 0, &q, &A, 0);
311
312 if (! check_same(&A, &N)) {
313 return 6;
314 }
315
316 igraph_sparsemat_destroy(&A);
317 igraph_sparsemat_destroy(&B);
318 igraph_vector_int_destroy(&p);
319 igraph_vector_int_destroy(&q);
320 igraph_matrix_destroy(&M);
321 igraph_matrix_destroy(&N);
322
323 return 0;
324 }
325