1function test70 (f)
2%TEST70 performance comparison of triangle counting methods
3%
4% This test saves its results in test70_results.mat, so it
5% can be restarted.  Results already obtained will be skipped.
6% This is useful since MATLAB can crash on some matrices,
7% with 'Killed', if it asks for way too much memory.
8%
9% It would be better to modify this test to check the
10% memory usage before trying the matrix multiply.
11% See test71.m, which does this:
12%
13%   % get nnz(C), flops, and memory for C=A*B:
14%   s = ssmultsym (A, B) ;
15%   % which returns a struct with these 3 statistics,
16%   % without doing any work, and requiring almost no memory
17%   % See SuiteSparse/MATLAB_tools/SSMULT
18%
19% The list of matrices can also be provided.  For example:
20% test70 ([936 2662])
21%
22% depends on functions in ../Demo/MATLAB
23
24% SuiteSparse:GraphBLAS, Timothy A. Davis, (c) 2017-2021, All Rights Reserved.
25% SPDX-License-Identifier: Apache-2.0
26
27addpath ('../Demo/MATLAB') ;
28
29[save save_chunk] = nthreads_get ;
30chunk = 4096 ;
31nthreads = feature ('numcores') ;
32nthreads_set (nthreads, chunk) ;
33
34index = ssget ;
35if (nargin == 0)
36    % get all square matrices and sort by nnz(A)
37    f = find (index.nrows == index.ncols) ;
38    [~, i] = sort (index.nnz (f)) ;
39    f = f (i) ;
40
41    % f = 936
42    % f = f (1)
43    figure (1)
44end
45
46nmat = length (f) ;
47
48% matrices too big for some methods.  0: skip that method
49if (ismac || ispc)
50    % assume this is a laptop with limited memory
51    results = 'test70_results' ;
52    skip = [
53        %id  methods 0:11
54        1294 0 1 1 1 0 1 1 1 1 1 1
55        2240 0 1 1 1 0 1 1 1 1 1 1
56        2229 1 1 1 1 0 1 1 1 1 1 1
57        1323 0 0 0 1 0 1 1 1 1 1 1
58        1324 0 0 0 1 0 1 1 1 1 1 1
59        1320 0 0 0 1 0 1 1 1 1 1 1
60        1321 0 0 0 1 0 1 1 1 1 1 1
61        1322 0 0 0 1 0 1 1 1 1 1 1
62        2234 0 1 1 1 0 1 1 1 1 1 1
63        1415 0 0 0 1 0 1 1 1 1 1 1
64        2275 0 0 0 1 0 1 1 1 1 1 1
65        2136 0 1 1 1 0 1 1 1 1 1 1
66        2241 0 0 0 1 0 1 1 1 1 1 1
67        %
68        1383 0 0 0 1 0 1 1 1 1 1 1
69            ] ;
70    % when Nedges > limit, do only MATLAB:Sandia,
71    % GraphBLAS:Sandia, and GraphBLAS:Sandia2.
72    % The others can fail badly
73    limit = 1e6 ;
74else
75    % assume this is a large server
76    results = 'test70_results_big' ;
77    skip = [
78        1383 0 0 0 1 0 1 1 1 1
79    ] ;
80    limit = 1e6 ;
81end
82
83if (nargin == 0)
84    try
85        load (results) ; % test70_results
86        fprintf ('loaded prior results: %s\n', results) ;
87    catch
88        T = nan (nmat, 9) ;
89        Nedges = nan (nmat, 1) ;
90        Nnodes = nan (nmat, 1) ;
91    end
92else
93    T = nan (nmat, 9) ;
94    Nedges = nan (nmat, 1) ;
95    Nnodes = nan (nmat, 1) ;
96end
97
98tstart = cputime ;
99
100for k = 1:nmat
101
102    if (~isnan (Nnodes (k)))
103        continue ;
104    end
105
106    id = f (k) ;
107    Prob = ssget (id, index) ;
108    A = Prob.A ;
109    name = Prob.name ;
110    clear Prob
111
112    % remove the diagonal and extract L and U
113    A = spones (A) ;
114    A = spones (A+A') ;
115    L = tril (A,-1) ;
116    U = triu (A,1) ;
117    A = L + U ;
118    n = size (A,1) ;
119    nz = nnz (L) ;
120
121    % create the edge incidence matrix
122    E = adj_to_edges (A) ;
123
124    fprintf ('\nid %4d Matrix %s\n', id, name) ;
125    fprintf ('n %d edges %d\n', n, nz) ;
126    ntri = -1 ;
127    diary off
128    diary on
129
130    Nedges (k) = nz ;
131    Nnodes (k) = n ;
132
133    % count the triangles in MATLAB and in GraphBLAS
134
135    method_list = {'minitri', 'Burkhardt', 'Cohen', 'Sandia', 'SandiaL', 'SandiaDot'} ;
136    m = 0 ;
137
138    % see what methods to skip
139    dothis = find (id == skip (:,1)) ;
140    if (~isempty (dothis))
141        dothis = skip (dothis, 2:end) ;
142    else
143        dothis = true (1,12) ;
144    end
145
146    for use_grb = 0:1
147        for kk = 1:6
148            method = method_list {kk} ;
149            m = m + 1 ;
150            if (nz > limit)
151                % do only MATLAB:Sandia, GraphBLAS:Sandia*
152                % leave other timings as NaN, not inf
153                if (~(m == 4 || m == 10 || m == 11 || m == 12))
154                    continue
155                end
156            end
157            nt = -1 ;
158            t = inf ;
159            if (dothis (m))
160                try
161                    if (use_grb)
162                        % use GraphBLAS (note that L and U are swapped since
163                        % L in row form is the same as U in column form.
164                        % The mexFunction interface to GraphBLAS passes in
165                        % the matrices in column form to tricount.
166                        [nt t] = GB_mex_tricount (kk-1, A, E, U, L) ;
167                    else
168                        % use MATLAB, unless the matrix fails
169                        [nt t] = tricount (method, A, E) ;
170                        t = t.prep_time + t.triangle_count_time ;
171                    end
172                catch
173                    % method failed (out of memory)
174                end
175            end
176            % check the result
177            if (nt ~= -1)
178                if (ntri == -1)
179                    ntri = nt ;
180                    fprintf ('# triangles: %d\n', ntri) ;
181                end
182                assert (nt == ntri) ;
183            end
184            if (use_grb)
185                fprintf ('GraphBLAS: %10s %10.4f\n', method, t) ;
186            else
187                fprintf ('MATLAB:    %10s %10.4f\n', method, t) ;
188            end
189            T (k, m) = t ;
190        end
191    end
192
193    clear A L U E
194
195    % save the results and redraw the plot, but wait at least 5 seconds
196    tnow = cputime - tstart ;
197    if (nargin == 0 && tnow > 5)
198        save (results, 'T', 'Nedges', 'Nnodes', 'f') ;
199        test70_plot (T, Nedges, Nnodes) ;
200        tstart = cputime ;
201        % also flush the diary
202    end
203
204end
205
206nthreads_set (save, save_chunk) ;
207