1function s = tricount (A, arg2, arg3)
2%GRB.TRICOUNT count triangles in a matrix.
3% s = GrB.tricount (A) is the number of triangles in the matrix A.
4% spones (A) must be symmetric; results are undefined if spones (A) is
5% unsymmetric.  Diagonal entries are ignored.
6%
7% To check the input matrix A, use GrB.tricount (A, 'check').  This check
8% takes additional time so by default the input is not checked.
9%
10% If d is a vector of length n with d(i) equal to the degree of node i,
11% then s = tricount (A, d) can be used.  Otherwise, tricount must compute
12% the degrees first.
13%
14% See also GrB.ktruss, GrB.entries.
15
16% SuiteSparse:GraphBLAS, Timothy A. Davis, (c) 2017-2021, All Rights Reserved.
17% SPDX-License-Identifier: GPL-3.0-or-later
18
19% NOTE: this is a high-level algorithm that uses GrB objects.
20
21[m, n] = size (A) ;
22if (m ~= n)
23    error ('A must be square') ;
24end
25
26d = [ ] ;
27check = false ;
28
29if (nargin == 2)
30    if (ischar (arg2))
31        % s = tricount (A, 'check')
32        check = isequal (arg2, 'check') ;
33    else
34        % s = tricount (A, d)
35        d = arg2 ;
36    end
37elseif (nargin == 3)
38    if (ischar (arg2))
39        % s = tricount (A, 'check', d)
40        check = isequal (arg2, 'check') ;
41        d = arg3 ;
42    else
43        % s = tricount (A, d, 'check')
44        d = arg2 ;
45        check = isequal (arg3, 'check') ;
46    end
47end
48
49if (check && ~issymmetric (spones (A)))
50    error ('pattern of A must be symmetric') ;
51end
52
53if (isequal (class (d), 'GrB'))
54    d = double (d) ;
55end
56
57% determine if A should be sorted first
58if (n > 1000 && GrB.entries (A) >= 10*n)
59    if (isempty (d))
60        % compute the degree of each node, if not provided on input
61        if (GrB.isbyrow (A))
62            d = double (GrB.entries (A, 'row', 'degree')) ;
63        else
64            d = double (GrB.entries (A, 'col', 'degree')) ;
65        end
66    end
67    % sample the degree
68    sample = d (randperm (n, 1000)) ;
69    dmean = full (mean (sample)) ;
70    dmed  = full (median (sample)) ;
71    if (dmean > 4 * dmed)
72        % sort if the average degree is very high compared to the median
73        [~, p] = sort (d, 'descend') ;
74        % A = A (p,p) ;
75        A = GrB.extract (A, { p }, { p }) ;
76        clear p
77    end
78end
79
80% C, L, and U will have the same format as A
81C = GrB (n, n, 'int64', GrB.format (A)) ;
82L = tril (A, -1) ;
83U = triu (A, 1) ;
84
85% Inside GraphBLAS, the methods below are identical.  For example, L stored by
86% row is the same data structure as U stored by column.  Both use the
87% SandiaDot2 method as defined in LAGraph (case 6), which is typically the
88% fastest of the methods in LAGraph_tricount.
89
90desc.mask = 'structural' ;
91
92if (GrB.isbyrow (A))
93    % C<U> = U*L': SandiaDot2 method
94    desc.in1 = 'transpose' ;
95    C = GrB.mxm (C, U, '+.pair.int64', U, L, desc) ;
96else
97    % C<U> = L'*U: SandiaDot2 method
98    desc.in0 = 'transpose' ;
99    C = GrB.mxm (C, U, '+.pair.int64', L, U, desc) ;
100end
101
102s = full (double (GrB.reduce ('+.int64', C))) ;
103
104