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