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