1 /* ========================================================================== */
2 /* === Tcov/cctest ========================================================== */
3 /* ========================================================================== */
4
5 /* -----------------------------------------------------------------------------
6 * CHOLMOD/Tcov Module. Copyright (C) 2005-2006, Timothy A. Davis
7 * http://www.suitesparse.com
8 * -------------------------------------------------------------------------- */
9
10 /* Test for ccolamd v1.0. Not used if NCAMD defined at compile time. */
11
12 #include "cm.h"
13
14 #ifndef NCAMD
15 #include "ccolamd.h"
16
17 /* ========================================================================== */
18 /* === check_constraints ==================================================== */
19 /* ========================================================================== */
20
21 /* Check to see if P obeys the constraints */
check_constraints(Int * P,Int * Cmember,Int n)22 Int check_constraints (Int *P, Int *Cmember, Int n)
23 {
24 Int c, clast, k, i ;
25 if ((P == NULL) || !CHOLMOD(print_perm) (P, n, n, "ccolamd perm", cm))
26 {
27 printf ("cctest: Perm is bad\n") ;
28 return (FALSE) ;
29 }
30 clast = EMPTY ;
31 for (k = 0 ; k < n ; k++)
32 {
33 i = P [k] ;
34 c = Cmember [i] ;
35 if (c < clast)
36 {
37 printf ("cctest: constraints are incorrect\n") ;
38 return (FALSE) ;
39 }
40 clast = c ;
41 }
42 return (TRUE) ;
43 }
44
45
46 /* ========================================================================== */
47 /* === cctest =============================================================== */
48 /* ========================================================================== */
49
cctest(cholmod_sparse * A)50 void cctest (cholmod_sparse *A)
51 {
52
53 double knobs [CCOLAMD_KNOBS], knobs2 [CCOLAMD_KNOBS] ;
54 Int *P, *Cmember, *Cp, *Ci, *Front_npivcol, *Front_nrows, *Front_ncols,
55 *Front_parent, *Front_cols, *InFront, *Si, *Sp ;
56 cholmod_sparse *C, *A2, *B, *S ;
57 Int nrow, ncol, alen, ok, stats [CCOLAMD_STATS], csets, i, nfr, c, p ;
58 size_t s ;
59
60 /* ---------------------------------------------------------------------- */
61 /* get inputs */
62 /* ---------------------------------------------------------------------- */
63
64 my_srand (42) ; /* RAND reset */
65
66 printf ("\nCCOLAMD test\n") ;
67
68 if (A == NULL)
69 {
70 return ;
71 }
72
73 if (A->stype)
74 {
75 A2 = CHOLMOD(copy) (A, 0, 0, cm) ;
76 B = A2 ;
77 }
78 else
79 {
80 A2 = NULL ;
81 B = A ;
82 }
83 S = CHOLMOD(copy_sparse) (A, cm) ;
84
85 nrow = B->nrow ;
86 ncol = B->ncol ;
87 Si = S->i ;
88 Sp = S->p ;
89
90 /* ---------------------------------------------------------------------- */
91 /* allocate workspace and Cmember for ccolamd */
92 /* ---------------------------------------------------------------------- */
93
94 P = CHOLMOD(malloc) (nrow+1, sizeof (Int), cm) ;
95 Cmember = CHOLMOD(malloc) (nrow, sizeof (Int), cm) ;
96 Front_npivcol = CHOLMOD(malloc) (nrow+1, sizeof (Int), cm) ;
97 Front_nrows = CHOLMOD(malloc) (nrow+1, sizeof (Int), cm) ;
98 Front_ncols = CHOLMOD(malloc) (nrow+1, sizeof (Int), cm) ;
99 Front_parent = CHOLMOD(malloc) (nrow+1, sizeof (Int), cm) ;
100 Front_cols = CHOLMOD(malloc) (nrow+1, sizeof (Int), cm) ;
101 InFront = CHOLMOD(malloc) (ncol, sizeof (Int), cm) ;
102
103 csets = MIN (6, nrow) ;
104 for (i = 0 ; i < nrow ; i++)
105 {
106 Cmember [i] = nrand (csets) ;
107 }
108
109 CCOLAMD_set_defaults (knobs) ;
110 CCOLAMD_set_defaults (knobs2) ;
111 CCOLAMD_set_defaults (NULL) ;
112 CCOLAMD_report (NULL) ;
113 CSYMAMD_report (NULL) ;
114
115 alen = CCOLAMD_recommended (B->nzmax, ncol, nrow) ;
116 C = CHOLMOD(allocate_sparse) (ncol, nrow, alen, TRUE, TRUE, 0,
117 CHOLMOD_PATTERN, cm) ;
118 Cp = C->p ;
119 Ci = C->i ;
120
121 /* ---------------------------------------------------------------------- */
122 /* order with ccolamd */
123 /* ---------------------------------------------------------------------- */
124
125 ok = CHOLMOD(transpose_unsym) (B, 0, NULL, NULL, 0, C, cm) ; OK (ok) ;
126 CHOLMOD(print_sparse) (C, "C for ccolamd", cm) ;
127 ok = CCOLAMD_MAIN (ncol, nrow, alen, Ci, Cp, NULL, stats, Cmember) ;
128 CCOLAMD_report (stats) ;
129 OK (ok) ;
130 ok = stats [CCOLAMD_STATUS] ;
131 ok = (ok == CCOLAMD_OK || ok == CCOLAMD_OK_BUT_JUMBLED) ;
132 OK (ok) ;
133
134 /* permutation returned in C->p, if the ordering succeeded */
135 /* make sure P obeys the constraints */
136 OK (check_constraints (Cp, Cmember, nrow)) ;
137
138 /* ---------------------------------------------------------------------- */
139 /* order with ccolamd2 */
140 /* ---------------------------------------------------------------------- */
141
142 ok = CHOLMOD(transpose_unsym) (B, 0, NULL, NULL, 0, C, cm) ; OK (ok) ;
143 ok = CCOLAMD_2 (ncol, nrow, alen, Ci, Cp, NULL, stats,
144 Front_npivcol, Front_nrows, Front_ncols, Front_parent,
145 Front_cols, &nfr, InFront, Cmember) ;
146 CCOLAMD_report (stats) ;
147 OK (check_constraints (Cp, Cmember, nrow)) ;
148
149 /* ---------------------------------------------------------------------- */
150 /* with a small dense-row threshold */
151 /* ---------------------------------------------------------------------- */
152
153 knobs2 [CCOLAMD_DENSE_ROW] = 0 ;
154 ok = CHOLMOD(transpose_unsym) (B, 0, NULL, NULL, 0, C, cm) ; OK (ok) ;
155 ok = CCOLAMD_MAIN (ncol, nrow, alen, Ci, Cp, knobs2, stats, Cmember) ;
156 CCOLAMD_report (stats) ;
157
158 knobs2 [CCOLAMD_DENSE_ROW] = 0.625 ;
159 knobs2 [CCOLAMD_DENSE_COL] = 0 ;
160 ok = CHOLMOD(transpose_unsym) (B, 0, NULL, NULL, 0, C, cm) ; OK (ok) ;
161 ok = CCOLAMD_MAIN (ncol, nrow, alen, Ci, Cp, knobs2, stats, Cmember) ;
162 CCOLAMD_report (stats) ;
163
164 knobs2 [CCOLAMD_DENSE_ROW] = 0.625 ;
165 knobs2 [CCOLAMD_DENSE_COL] = -1 ;
166 ok = CHOLMOD(transpose_unsym) (B, 0, NULL, NULL, 0, C, cm) ; OK (ok) ;
167 ok = CCOLAMD_MAIN (ncol, nrow, alen, Ci, Cp, knobs2, stats, Cmember) ;
168 CCOLAMD_report (stats) ;
169
170 knobs2 [CCOLAMD_DENSE_COL] = 0 ;
171
172 /* ---------------------------------------------------------------------- */
173 /* duplicate entries */
174 /* ---------------------------------------------------------------------- */
175
176 if (ncol > 2 && nrow > 2)
177 {
178 ok = CHOLMOD(transpose_unsym) (B, 0, NULL, NULL, 0, C, cm) ;
179 OK (ok) ;
180 if (Cp [1] - Cp [0] > 2)
181 {
182 Ci [0] = Ci [1] ;
183 }
184 ok = CCOLAMD_MAIN (ncol, nrow, alen, Ci, Cp, knobs2, stats, Cmember) ;
185 CCOLAMD_report (stats) ;
186 OK (CHOLMOD(print_perm) (Cp, nrow, nrow, "ccolamd perm", cm)) ;
187 }
188
189 /* ---------------------------------------------------------------------- */
190 /* csymamd */
191 /* ---------------------------------------------------------------------- */
192
193 if (nrow == ncol)
194 {
195 Int n = nrow ;
196
197 ok = CSYMAMD_MAIN (n, Si, Sp, P, NULL, stats,
198 SuiteSparse_config.calloc_func,
199 SuiteSparse_config.free_func,
200 Cmember, A->stype) ;
201 OK (ok) ;
202 OK (check_constraints (P, Cmember, n)) ;
203 CSYMAMD_report (stats) ;
204
205 /* ------------------------------------------------------------------ */
206 /* csymamd errors */
207 /* ------------------------------------------------------------------ */
208
209 ok = CSYMAMD_MAIN (n, Si, Sp, P, NULL, NULL,
210 SuiteSparse_config.calloc_func,
211 SuiteSparse_config.free_func,
212 Cmember, A->stype) ; NOT (ok);
213
214 ok = CSYMAMD_MAIN (n, NULL, Sp, P, NULL, stats,
215 SuiteSparse_config.calloc_func,
216 SuiteSparse_config.free_func,
217 Cmember, A->stype) ; NOT (ok);
218 CSYMAMD_report (stats) ;
219
220 ok = CSYMAMD_MAIN (n, Si, NULL, P, NULL, stats,
221 SuiteSparse_config.calloc_func,
222 SuiteSparse_config.free_func,
223 Cmember, A->stype) ; NOT (ok);
224 CSYMAMD_report (stats) ;
225
226 ok = CSYMAMD_MAIN (-1, Si, Sp, P, NULL, stats,
227 SuiteSparse_config.calloc_func,
228 SuiteSparse_config.free_func,
229 Cmember, A->stype) ; NOT (ok);
230 CSYMAMD_report (stats) ;
231
232 p = Sp [n] ;
233 Sp [n] = -1 ;
234 ok = CSYMAMD_MAIN (n, Si, Sp, P, NULL, stats,
235 SuiteSparse_config.calloc_func,
236 SuiteSparse_config.free_func,
237 Cmember, A->stype) ; NOT (ok);
238 CSYMAMD_report (stats) ;
239 Sp [n] = p ;
240
241 Sp [0] = -1 ;
242 ok = CSYMAMD_MAIN (n, Si, Sp, P, NULL, stats,
243 SuiteSparse_config.calloc_func,
244 SuiteSparse_config.free_func,
245 Cmember, A->stype) ; NOT (ok);
246 CSYMAMD_report (stats) ;
247 Sp [0] = 0 ;
248
249 if (n > 2 && Sp [n] > 3)
250 {
251 p = Sp [1] ;
252 Sp [1] = -1 ;
253 ok = CSYMAMD_MAIN (n, Si, Sp, P, NULL, stats,
254 SuiteSparse_config.calloc_func,
255 SuiteSparse_config.free_func,
256 Cmember, A->stype) ; NOT (ok);
257 CSYMAMD_report (stats) ;
258 Sp [1] = p ;
259
260 i = Si [0] ;
261 Si [0] = -1 ;
262 ok = CSYMAMD_MAIN (n, Si, Sp, P, NULL, stats,
263 SuiteSparse_config.calloc_func,
264 SuiteSparse_config.free_func,
265 Cmember, A->stype) ; NOT (ok);
266 CSYMAMD_report (stats) ;
267 Si [0] = i ;
268
269 /* ok, but jumbled */
270 i = Si [0] ;
271 Si [0] = Si [1] ;
272 Si [1] = i ;
273 ok = CSYMAMD_MAIN (n, Si, Sp, P, NULL, stats,
274 SuiteSparse_config.calloc_func,
275 SuiteSparse_config.free_func,
276 Cmember, A->stype) ; OK (ok);
277 CSYMAMD_report (stats) ;
278 i = Si [0] ;
279 Si [0] = Si [1] ;
280 Si [1] = i ;
281
282 test_memory_handler ( ) ;
283 ok = CSYMAMD_MAIN (n, Si, Sp, P, NULL, stats,
284 SuiteSparse_config.calloc_func,
285 SuiteSparse_config.free_func,
286 Cmember, A->stype) ; NOT(ok);
287 CSYMAMD_report (stats) ;
288 normal_memory_handler ( ) ;
289 }
290 }
291
292 /* ---------------------------------------------------------------------- */
293 /* error tests */
294 /* ---------------------------------------------------------------------- */
295
296 ok = CHOLMOD(transpose_unsym) (B, 0, NULL, NULL, 0, C, cm) ; OK (ok) ;
297 ok = CCOLAMD_MAIN (ncol, nrow, 0, Ci, Cp, knobs, stats, Cmember) ; NOT (ok) ;
298 CCOLAMD_report (stats) ;
299
300 ok = CCOLAMD_MAIN (ncol, nrow, alen, NULL, Cp, knobs, stats, Cmember); NOT (ok) ;
301 CCOLAMD_report (stats) ;
302
303 ok = CCOLAMD_MAIN (ncol, nrow, alen, Ci, NULL, knobs, stats, Cmember); NOT (ok) ;
304 CCOLAMD_report (stats) ;
305
306 ok = CCOLAMD_MAIN (ncol, nrow, alen, Ci, Cp, knobs, NULL, Cmember) ; NOT (ok) ;
307 CCOLAMD_report (stats) ;
308
309 ok = CCOLAMD_MAIN (-1, nrow, alen, Ci, Cp, knobs, stats, Cmember) ; NOT (ok) ;
310 CCOLAMD_report (stats) ;
311
312 ok = CCOLAMD_MAIN (ncol, -1, alen, Ci, Cp, knobs, stats, Cmember) ; NOT (ok) ;
313 CCOLAMD_report (stats) ;
314
315 ok = CHOLMOD(transpose_unsym) (B, 0, NULL, NULL, 0, C, cm) ; OK (ok) ;
316 Cp [nrow] = -1 ;
317 ok = CCOLAMD_MAIN (ncol, nrow, alen, Ci, Cp, knobs, stats, Cmember) ; NOT (ok) ;
318 CCOLAMD_report (stats) ;
319
320 Cp [0] = 1 ;
321 ok = CCOLAMD_MAIN (ncol, nrow, alen, Ci, Cp, knobs, stats, Cmember) ; NOT (ok) ;
322 CCOLAMD_report (stats) ;
323
324 ok = CHOLMOD(transpose_unsym) (B, 0, NULL, NULL, 0, C, cm) ; OK (ok) ;
325
326 if (nrow > 0 && alen > 0 && Cp [1] > 0)
327 {
328 c = Cmember [0] ;
329 Cmember [0] = -1 ;
330 ok = CCOLAMD_MAIN (ncol, nrow, alen, Ci, Cp, knobs, stats, Cmember) ;NOT(ok);
331 CCOLAMD_report (stats) ;
332 Cmember [0] = c ;
333
334 p = Cp [1] ;
335 Cp [1] = -1 ;
336 ok = CCOLAMD_MAIN (ncol, nrow, alen, Ci, Cp, knobs, stats, Cmember) ;NOT(ok);
337 CCOLAMD_report (stats) ;
338 Cp [1] = p ;
339
340 i = Ci [0] ;
341 Ci [0] = -1 ;
342 ok = CCOLAMD_MAIN (ncol, nrow, alen, Ci, Cp, knobs, stats, Cmember) ;NOT(ok);
343 CCOLAMD_report (stats) ;
344 Ci [0] = i ;
345 }
346
347 s = CCOLAMD_recommended (-1, 0, 0) ;
348 OK (s == 0) ;
349
350 /* ---------------------------------------------------------------------- */
351 /* free workspace */
352 /* ---------------------------------------------------------------------- */
353
354 CHOLMOD(free) (nrow+1, sizeof (Int), Front_npivcol, cm) ;
355 CHOLMOD(free) (nrow+1, sizeof (Int), Front_nrows, cm) ;
356 CHOLMOD(free) (nrow+1, sizeof (Int), Front_ncols, cm) ;
357 CHOLMOD(free) (nrow+1, sizeof (Int), Front_parent, cm) ;
358 CHOLMOD(free) (nrow+1, sizeof (Int), Front_cols, cm) ;
359 CHOLMOD(free) (nrow+1, sizeof (Int), P, cm) ;
360 CHOLMOD(free) (nrow, sizeof (Int), Cmember, cm) ;
361 CHOLMOD(free) (ncol, sizeof (Int), InFront, cm) ;
362
363 CHOLMOD(free_sparse) (&S, cm) ;
364 CHOLMOD(free_sparse) (&A2, cm) ;
365 CHOLMOD(free_sparse) (&C, cm) ;
366 cm->print = 1 ;
367 }
368
369 #else
370
cctest(cholmod_sparse * A)371 void cctest (cholmod_sparse *A)
372 {
373 if (A == NULL)
374 {
375 return ;
376 }
377
378 cm->print = 1 ;
379 }
380 #endif
381