1function ccolamd_test 2%CCOLAMD_TEST extensive test of ccolamd and csymamd 3% 4% Example: 5% ccolamd_test 6% 7% See also csymamd, ccolamd, ccolamd_make. 8 9% Copyright 1998-2007, Timothy A. Davis, Stefan Larimore, and Siva Rajamanickam 10% Developed in collaboration with J. Gilbert and E. Ng. 11 12help ccolamd_test 13 14global ccolamd_default_knobs csymamd_default_knobs 15ccolamd_default_knobs = [0 10 10 1 0] ; 16csymamd_default_knobs = [10 1 0] ; 17 18 fprintf ('Compiling ccolamd, csymamd, and test mexFunctions.\n') ; 19 ccolamd_make ; 20 21 d = '' ; 22 if (~isempty (strfind (computer, '64'))) 23 d = '-largeArrayDims' ; 24 end 25 cmd = sprintf ( ... 26 'mex -DDLONG -O %s -I../../SuiteSparse_config -I../Include ', d) ; 27 src = '../Source/ccolamd.c ../../SuiteSparse_config/SuiteSparse_config.c' ; 28 if (~(ispc || ismac)) 29 % for POSIX timing routine 30 src = [src ' -lrt'] ; 31 end 32 eval ([cmd 'ccolamdtestmex.c ' src]) ; 33 eval ([cmd 'csymamdtestmex.c ' src]) ; 34 fprintf ('Done compiling.\n') ; 35 36 37fprintf ('\nThe following codes will be tested:\n') ; 38which ccolamd 39which csymamd 40which ccolamdtestmex 41which csymamdtestmex 42 43fprintf ('\nStarting the tests. Please be patient.\n') ; 44 45h = waitbar (0, 'COLAMD test') ; 46 47rand ('state', 0) ; 48randn ('state', 0) ; 49 50A = sprandn (500,500,0.4) ; 51 52p = ccolamd (A, [0 10 10 1 1]) ; check_perm (p, A) ; 53p = ccolamd (A, [1 2 7 1 1]) ; check_perm (p, A) ; 54p = ccolamd (A, [1 2 10 0 1]) ; check_perm (p, A) ; 55p = ccolamd (A, [9 2 3 1 1]) ; check_perm (p, A) ; 56 57p = csymamd (A, [10 1 1]) ; check_perm (p, A) ; 58p = csymamd (A, [4 1 1]) ; check_perm (p, A) ; 59p = csymamd (A, [9 0 1]) ; check_perm (p, A) ; 60 61fprintf ('Null matrices') ; 62A = zeros (0,0) ; 63A = sparse (A) ; 64 65p = ccolamd (A) ; 66check_perm (p, A) ; 67 68p = csymamd (A) ; 69check_perm (p, A) ; 70 71A = zeros (0, 100) ; 72A = sparse (A) ; 73p = ccolamd (A) ; 74check_perm (p, A) ; 75 76A = zeros (100, 0) ; 77A = sparse (A) ; 78p = ccolamd (A) ; 79check_perm (p, A) ; 80fprintf (' OK\n') ; 81 82 83fprintf ('Matrices with a few dense row/cols\n') ; 84for trial = 1:20 85 86 waitbar (trial/20, h, 'CCOLAMD: dense rows/cols') ; 87 88 % random square unsymmetric matrix 89 A = rand_matrix (1000, 1000, 1, 10, 20) ; 90 [m n] = size (A) ; 91 92 cmember = irand (min (trial,n), n) ; 93 94 for tol = [0:.1:2 3:20 1e6] 95 B = A + A' ; 96 97 p = ccolamd (A, [ ]) ; check_perm (p, A) ; 98 p = ccolamd (A, [1 tol tol 1]) ; check_perm (p, A) ; 99 p = ccolamd (A, [0 tol tol 1]) ; check_perm (p, A) ; 100 p = ccolamd (A, [1 tol tol 0]) ; check_perm (p, A) ; 101 p = ccolamd (A, [0 tol tol 1]) ; check_perm (p, A) ; 102 p = csymamd (A, [tol 1]) ; check_perm (p, A) ; 103 p = csymamd (A, tol) ; check_perm (p, A) ; 104 p = csymamd (A, [ ]) ; check_perm (p, A) ; 105 p = csymamd (B, [tol 0]) ; check_perm (p, A) ; 106 p = ccolamd (A, [0 tol -1 1]) ; check_perm (p, A) ; 107 p = ccolamd (A, [0 -1 tol 1]) ; check_perm (p, A) ; 108 109 % check with non-null cmember 110 111 p = ccolamd (A, [ ], cmember) ; check_perm (p, A) ; 112 p = ccolamd (A, [1 tol tol 1], cmember) ; check_perm (p, A) ; 113 p = ccolamd (A, [0 tol tol 1], cmember) ; check_perm (p, A) ; 114 p = ccolamd (A, [1 tol tol 0], cmember) ; check_perm (p, A) ; 115 p = ccolamd (A, [0 tol tol 1], cmember) ; check_perm (p, A) ; 116 p = csymamd (A, [tol 1], cmember) ; check_perm (p, A) ; 117 p = csymamd (A, tol, cmember) ; check_perm (p, A) ; 118 p = csymamd (A, [ ], cmember) ; check_perm (p, A) ; 119 p = csymamd (B, [tol 0], cmember) ; check_perm (p, A) ; 120 p = ccolamd (A, [0 tol -1 1], cmember) ; check_perm (p, A) ; 121 p = ccolamd (A, [0 -1 tol 1], cmember) ; check_perm (p, A) ; 122 123 p = ccolamd (A, [ ], [ ]) ; check_perm (p, A) ; 124 p = ccolamd (A, [1 tol tol 1], [ ]) ; check_perm (p, A) ; 125 p = ccolamd (A, [0 tol tol 1], [ ]) ; check_perm (p, A) ; 126 p = ccolamd (A, [1 tol tol 0], [ ]) ; check_perm (p, A) ; 127 p = ccolamd (A, [0 tol tol 1], [ ]) ; check_perm (p, A) ; 128 p = csymamd (A, [tol 1], [ ]) ; check_perm (p, A) ; 129 p = csymamd (A, tol, [ ]) ; check_perm (p, A) ; 130 p = csymamd (A, [ ], [ ]) ; check_perm (p, A) ; 131 p = csymamd (B, [tol 0], [ ]) ; check_perm (p, A) ; 132 p = ccolamd (A, [0 tol -1 1], [ ]) ; check_perm (p, A) ; 133 p = ccolamd (A, [0 -1 tol 1], [ ]) ; check_perm (p, A) ; 134 135 end 136end 137fprintf (' OK\n') ; 138 139fprintf ('General matrices\n') ; 140for trial = 1:400 141 142 waitbar (trial/400, h, 'CCOLAMD: with dense rows/cols') ; 143 144 % matrix of random mtype 145 mtype = irand (3) ; 146 A = rand_matrix (2000, 2000, mtype, 0, 0) ; 147 p = ccolamd (A) ; 148 check_perm (p, A) ; 149 150 if (mtype == 3) 151 p = csymamd (A) ; 152 check_perm (p, A) ; 153 end 154 155end 156fprintf (' OK\n') ; 157 158 159 160fprintf ('Test error handling with invalid inputs\n') ; 161 162% Check different erroneous input. 163for trial = 1:30 164 165 waitbar (trial/30, h, 'CCOLAMD: error handling') ; 166 167 A = rand_matrix (1000, 1000, 2, 0, 0) ; 168 169 for err = 1:13 170 171 p = Tcolamd (A, [ccolamd_default_knobs 1 err], [ ]) ; 172 if (p(1) ~= -1) %#ok 173 check_perm (p, A) ; 174 end 175 176 if (err == 1) 177 % check different (valid) input args to ccolamd 178 p = Acolamd (A) ; 179 p2 = Acolamd (A, [ccolamd_default_knobs 0 0]) ; 180 if (any (p ~= p2)) 181 error ('ccolamd: mismatch 1!') ; 182 end 183 end 184 185 B = A'*A ; 186 p = Tsymamd (B, [-1 1 0 err], [ ]) ; 187 if (p(1) ~= -1) %#ok 188 check_perm (p, A) ; 189 end 190 191 if (err == 1) 192 193 % check different (valid) input args to csymamd 194 p = Asymamd (B) ; 195 check_perm (p, A) ; 196 p2 = Asymamd (B, [csymamd_default_knobs 0]) ; 197 if (any (p ~= p2)) 198 error ('symamd: mismatch 1!') ; 199 end 200 end 201 202 end 203 204end 205fprintf (' OK\n') ; 206 207fprintf ('Matrices with a few empty columns\n') ; 208 209for trial = 1:400 210 211 waitbar (trial/400, h, 'CCOLAMD: with empty rows/cols') ; 212 213 % some are square, some are rectangular 214 n = 0 ; 215 while (n < 5) 216 A = rand_matrix (1000, 1000, irand (2), 0, 0) ; 217 [m n] = size (A) ; 218 end 219 220 % Add 5 null columns at random locations. 221 null_col = randperm (n) ; 222 A (:, null_col) = 0 ; 223 224 % Order the matrix and make sure that the null columns are ordered last. 225 p = ccolamd (A, [1 1e6 1e6 0]) ; 226 check_perm (p, A) ; 227 228 % find all null columns in A 229 null_col = find (sum (spones (A), 1) == 0) ; 230 nnull = length (null_col) ; 231 if (any (null_col ~= p ((n-nnull+1):n))) 232 error ('ccolamd: Null cols are not ordered last in natural order') ; 233 end 234 235end 236fprintf (' OK\n') ; 237 238fprintf ('Matrices with a few empty rows and columns\n') ; 239 240for trial = 1:400 241 242 waitbar (trial/400, h, 'CCOLAMD: with empty rows/cols') ; 243 244 % symmetric matrices 245 n = 0 ; 246 while (n < 5) 247 A = rand_matrix (1000, 1000, 3, 0, 0) ; 248 [m n] = size (A) ; 249 end 250 251 % Add 5 null columns and rows at random locations. 252 null_col = randperm (n) ; 253 A (:, null_col) = 0 ; 254 A (null_col, :) = 0 ; 255 256 % Order the matrix and make sure that the null rows/cols are ordered last. 257 p = csymamd (A, -1) ; 258 check_perm (p, A) ; 259 260 % find all null rows/columns in A 261 Alo = tril (A, -1) ; 262 null_col = ... 263 find ((sum (spones (Alo), 1) == 0) & (sum (spones (Alo), 2) == 0)') ; 264 nnull = length (null_col) ; 265 if (any (null_col ~= p ((n-nnull+1):n))) 266 error ('csymamd: Null cols are not ordered last in natural order') ; 267 end 268 269end 270fprintf (' OK\n') ; 271 272fprintf ('Matrices with a few empty rows\n') ; 273 274% Test matrices with null rows inserted. 275 276for trial = 1:400 277 278 waitbar (trial/400, h, 'CCOLAMD: with null rows') ; 279 m = 0 ; 280 while (m < 5) 281 A = rand_matrix (1000, 1000, 2, 0, 0) ; 282 m = size (A,1) ; 283 end 284 285 % Add 5 null rows at random locations. 286 null_row = randperm (m) ; 287 null_row = sort (null_row (1:5)) ; 288 A (null_row, :) = 0 ; 289 290 p = ccolamd (A) ; 291 check_perm (p, A) ; 292 293end 294fprintf (' OK\n') ; 295 296fprintf ('\nccolamd and csymamd: all tests passed\n\n') ; 297close (h) ; 298 299%------------------------------------------------------------------------------- 300 301function p = Acolamd (S, knobs) 302% Acolamd: compare ccolamd and Tcolamd results 303 304global ccolamd_default_knobs 305 306if (nargin < 2) 307 p = ccolamd (S) ; 308 p1 = Tcolamd (S, [ccolamd_default_knobs 0 0], [ ]) ; 309else 310 p = ccolamd (S, knobs) ; 311 p1 = Tcolamd (S, knobs, [ ]) ; 312end 313 314check_perm (p, S) ; 315check_perm (p1, S) ; 316 317if (any (p1 ~= p)) 318 narg = nargin ; 319 if (nargin == 2) 320 save bad S narg knobs 321 else 322 save bad S narg 323 end 324 error ('Acolamd mismatch!') ; 325end 326 327%------------------------------------------------------------------------------- 328 329function p = Asymamd (S, knobs) 330% Asymamd: compare csymamd and Tsymamd results 331 332global csymamd_default_knobs 333 334if (nargin < 2) 335 p = csymamd (S) ; 336 p1 = Tsymamd (S, [csymamd_default_knobs 0], [ ]) ; 337else 338 p = csymamd (S, knobs) ; 339 p1 = Tsymamd (S, knobs, [ ]) ; 340end 341 342if (any (p1 ~= p)) 343 error ('Asymamd mismatch!') ; 344end 345 346 347%------------------------------------------------------------------------------- 348 349function check_perm (p, A, cmember) 350% check_perm: check for a valid permutation vector 351 352if (isempty (A) & isempty (p)) %#ok 353 % empty permutation vectors of empty matrices are OK 354 return 355end 356 357if (isempty (p)) 358 error ('Bad permutation: cannot be empty') ; 359end 360 361[m n] = size (A) ; 362[p_m p_n] = size (p) ; 363if (p_n == 1) 364 % force p to be a row vector 365 p = p' ; 366 [p_m p_n] = size (p) ; 367end 368 369if (n ~= p_n) 370 error ('Bad permutation: wrong size') ; 371end 372 373if (p_m ~= 1) ; 374 % p must be a vector 375 error ('Bad permutation: not a vector') ; 376else 377 if (any (sort (p) - (1:p_n))) 378 error ('Bad permutation') ; 379 end 380end 381 382if (nargin > 2) 383 % check cmember 384 c = cmember (p) ; 385 % c must be monotonically non-decreasing 386 c = diff (c) ; 387 if (any (c < 0)) 388 error ('permutation breaks the cmember constraints') ; 389 end 390end 391 392%------------------------------------------------------------------------------- 393 394function i = irand (n,s) 395% irand: return a random vector of size s, with values between 1 and n 396if (nargin == 1) 397 s = 1 ; 398end 399i = min (n, 1 + floor (rand (1,s) * n)) ; 400 401%------------------------------------------------------------------------------- 402 403function A = rand_matrix (n_max, m_max, mtype, d_rows, d_cols) 404% rand_matrix: return a random sparse matrix 405% 406% A = rand_matrix (n_max, m_max, mtype, d_rows, d_cols) 407% 408% A binary matrix of random size, at most n_max-by-m_max, with d_rows dense rows 409% and d_cols dense columns. 410% 411% mtype 1: square unsymmetric (m_max is ignored) 412% mtype 2: rectangular 413% mtype 3: symmetric (m_max is ignored) 414 415n = irand (n_max) ; 416if (mtype ~= 2) 417 % square 418 m = n ; 419else 420 m = irand (m_max) ; 421end 422 423A = sprand (m, n, 10 / max (m,n)) ; 424 425if (d_rows > 0) 426 % add dense rows 427 for k = 1:d_rows 428 i = irand (m) ; 429 nz = irand (n) ; 430 p = randperm (n) ; 431 p = p (1:nz) ; 432 A (i,p) = 1 ; 433 end 434end 435 436if (d_cols > 0) 437 % add dense cols 438 for k = 1:d_cols 439 j = irand (n) ; 440 nz = irand (m) ; 441 p = randperm (m) ; 442 p = p (1:nz) ; 443 A (p,j) = 1 ; 444 end 445end 446 447A = spones (A) ; 448 449% ensure that there are no empty columns 450d = find (full (sum (A,1)) == 0) ; %#ok 451A (m,d) = 1 ; %#ok 452 453% ensure that there are no empty rows 454d = find (full (sum (A,2)) == 0) ; %#ok 455A (d,n) = 1 ; %#ok 456 457if (mtype == 3) 458 % symmetric 459 A = A + A' + speye (n) ; 460end 461 462A = spones (A) ; 463 464%------------------------------------------------------------------------------- 465% Tcolamd: run ccolamd in a testing mode 466%------------------------------------------------------------------------------- 467 468function p = Tcolamd (S, knobs, cmember) 469 470% knobs (5) = 1 ; 471p = ccolamdtestmex (S, knobs, cmember) ; 472 473if (p (1) ~= -1) 474 check_perm (p, S) ; 475end 476 477 478%------------------------------------------------------------------------------- 479% Tsymamd: run csymamd in a testing mode 480%------------------------------------------------------------------------------- 481 482function p = Tsymamd (S, knobs, cmember) 483 484% knobs (2) = 1 ; 485p = csymamdtestmex (S, knobs, cmember) ; 486 487if (p (1) ~= -1) 488 check_perm (p, S) ; 489end 490 491