1function test12 (nmat)
2%TEST12 test etree2 and compare with etree
3% Example:
4%   test12(nmat)
5% See also cholmod_test
6
7% Copyright 2007, Timothy A. Davis, http://www.suitesparse.com
8
9fprintf ('=================================================================\n');
10fprintf ('test12: test etree2 and compare with etree\n') ;
11
12index = ssget ;
13
14% only test matrices with nrows = 109000 or less.  large ones nearly always
15% cause a MATLAB segfault.
16% f = find (index.nrows < 109000) ;
17f = 1:length (index.nrows) ;
18
19% sort by row dimension
20[ignore i] = sort (index.nrows (f)) ;
21f = f (i) ;
22
23if (nargin > 0)
24    nmat = max (0,nmat) ;
25    nmat = min (nmat, length (f)) ;
26    f = f (1:nmat) ;
27end
28
29% MATLAB 7.0 (R14, sp2, linux) etree gives a segfault for these matrices:
30s_skip =   [ 803 374 1287 1311 1308 957 958 1257 955 761 1282 1230 1256 ...
31	    924 1302 537 820 821 822 1258 ...
32	    844 845 1238 804 939 1270 1305 1208 1209 290 879 928 1307 1244 ...
33	    1275 1276 1296 885 1269 959 542 1290 ] ;
34
35sym_skip =  s_skip  ;
36
37p_sym_skip =   1296  ;
38p_symt_skip =  1296  ;
39
40symt_skip= [ s_skip 592 593 809 ] ;
41
42rowcol_skip = [ 646 ...
43	     1224 803 588 589 374 1287 562 563 801 1311 1246 951 1308 950 ...
44	     957 958 800 1257 564 565 955 761 1282 590 591 1230 1256 952 566 ...
45	     567 924 1302 1293 1294 537 820 821 822 1306 849 1258 592 593 ...
46	     1225 844 845 1226 1238 1227 804 939 1270 752 753 1305 809 1228 ...
47	     1208 1209 1291 1292 1300 856 1229 290 879 928 1307 857 1244  ...
48	     1275 1276 1296 885 858 859 1269 1263 959 542 1290 ] ;
49
50col_skip = [ rowcol_skip 647 612 610 648 799 651 652 750 751 640 ] ;
51
52row_skip= [ rowcol_skip 903 373 ] ;
53
54% f = f (find (f == 1290) : end) ;
55
56fprintf ('Matrices to test: %d\n', length (f)) ;
57
58
59for i = f
60
61    % try
62
63	Problem = ssget (i) ;
64	A = spones (Problem.A) ;
65	[m n] = size (A) ;
66	fprintf ('\n%4d: %-20s nrow: %6d ncol: %6d nnz: %10d\n', ...
67	    i, Problem.name, m, n, nnz(A)) ;
68
69	% if (max (m,n) < 500)
70	%    A = full (A) ;
71	% end
72
73	% warmup, for accurate timing
74	etree (sparse (1)) ;
75	etree2 (sparse (1)) ;
76	amd2 (sparse (1)) ;
77
78	% test column etree
79	skip = any (i == col_skip) | m > 109000 ;			    %#ok
80	if (~skip)
81	    tic ;
82	    [parent post] = etree (A, 'col') ;
83	    t1 = toc ;
84	else
85	    t1 = Inf ;
86	end
87
88	tic ;
89	[my_parent my_post] = etree2 (A, 'col') ;
90	t2 = toc ;
91
92	if (~skip)
93	    if (any (parent ~= my_parent))
94		error ('parent invalid!') ;
95	    end
96	end
97	fprintf ('etree(A,''col''): %8.4f  %8.4f              speedup %8.2f  ',...
98		t1, t2, t1/t2);
99	if (~skip)
100	    if (any (post ~= my_post))
101		fprintf ('postorder differs') ;
102	    end
103	end
104	fprintf ('\n') ;
105
106	% test row etree
107	skip = any (i == row_skip) | m > 109000 ;			    %#ok
108	if (~skip)
109	    tic ;
110	    [parent post] = etree (A', 'col') ;
111	    t1 = toc ;
112	else
113	    t1 = Inf ;
114	end
115
116	tic ;
117	[my_parent my_post] = etree2 (A, 'row') ;
118	t2 = toc ;
119
120	if (~skip)
121	    if (any (parent ~= my_parent))
122		error ('parent invalid!') ;
123	    end
124	end
125	fprintf ('etree(A,''row''): %8.4f  %8.4f              speedup %8.2f  ',...
126		t1, t2, t1/t2);
127	if (~skip)
128	    if (any (post ~= my_post))
129		fprintf ('postorder differs') ;
130	    end
131	end
132	fprintf ('\n') ;
133
134
135
136	if (m == n)
137
138	    for trial = 1:2
139
140		if (trial == 1)
141		    skip1 = any (i == sym_skip) | m > 109000 ;		    %#ok
142		    skip2 = any (i == symt_skip) | m > 109000 ;		    %#ok
143		else
144		    skip1 = any (i == p_sym_skip) | m > 109000 ;	    %#ok
145		    skip2 = any (i == p_symt_skip) | m > 109000 ;	    %#ok
146		    fprintf ('after amd:\n') ;
147		    p = amd2 (A) ;  % use AMD from SuiteSparse
148		    A = A (p,p) ;
149		end
150
151		% test symmetric etree, using triu(A)
152		if (~skip1)
153		    tic ;
154		    [parent post] = etree (A) ;
155		    t1 = toc ;
156		else
157		    t1 = Inf ;
158		end
159
160		tic ;
161		[my_parent my_post] = etree2 (A) ;
162		t2 = toc ;
163
164		if (~skip1)
165		    if (any (parent ~= my_parent))
166			error ('parent invalid!') ;
167		    end
168		end
169		fprintf ('etree(A):       %8.4f  %8.4f              speedup %8.2f  ',...
170			t1, t2, t1/t2);
171		if (~skip1)
172		    if (any (post ~= my_post))
173			fprintf ('postorder differs') ;
174		    end
175		end
176		fprintf ('\n') ;
177
178		% test symmetric etree, using tril(A)
179		if (~skip2)
180		    tic ;
181		    [parent post] = etree (A') ;
182		    t1 = toc ;
183		else
184		    t1 = Inf ;
185		end
186
187		tic ;
188		[my_parent my_post] = etree2 (A, 'lo') ;
189		t2 = toc ;
190
191		if (~skip2)
192		    if (any (parent ~= my_parent))
193			error ('parent invalid!') ;
194		    end
195		end
196		fprintf('etree(A''):      %8.4f  %8.4f              speedup %8.2f  ',...
197			t1, t2, t1/t2);
198		if (~skip2)
199		    if (any (post ~= my_post))
200			fprintf ('postorder differs') ;
201		    end
202		end
203		fprintf ('\n') ;
204
205	    end
206
207	end
208
209    % catch
210	% fprintf ('%d: failed\n', i) ;
211    % end
212end
213
214fprintf ('test12 passed\n') ;
215