← Back to branch summary

~ubuntu-branches/ubuntu/natty/suitesparse/natty

« back to all changes in this revision

Viewing changes to CCOLAMD/MATLAB/ccolamd_test.m

  • Committer: Bazaar Package Importer
  • Author(s): Christophe Prud'homme
  • Date: 2007-05-29 09:36:29 UTC
  • mfrom: (1.1.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20070529093629-zowquo0b7slkk6nc
Tags: 3.0.0-2
http://bugs.debian.org/426349
http://bugs.debian.org/426354
* suitesparse builds properly twice in a row
* Bug fix: "suitesparse - FTBFS: Broken build depens: libgfortran1-dev",
  thanks to Bastian Blank (Closes: #426349).
* Bug fix: "suitesparse_3.0.0-1: FTBFS: build-depends on
  libgfortran1-dev", thanks to Steve Langasek (Closes: #426354).

Show diffs side-by-side

added added

removed removed

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