Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LG_check_tri: compute the number of triangles in a graph (simple method)
3 : //------------------------------------------------------------------------------
4 :
5 : // LAGraph, (c) 2019-2022 by The LAGraph Contributors, All Rights Reserved.
6 : // SPDX-License-Identifier: BSD-2-Clause
7 : //
8 : // For additional details (including references to third party source code and
9 : // other files) see the LICENSE file or contact permission@sei.cmu.edu. See
10 : // Contributors.txt for a full list of contributors. Created, in part, with
11 : // funding and support from the U.S. Government (see Acknowledgments.txt file).
12 : // DM22-0790
13 :
14 : // Contributed by Timothy A. Davis, Texas A&M University
15 :
16 : //------------------------------------------------------------------------------
17 :
18 : // A very slow, bare-bones triangle count using a parallel dot-product method.
19 : // Computes the sum(sum((A'*A).*A)), in MATLAB notation, where A is symmetric
20 : // and treated as binary (only the structure is used). Diagonal entries are
21 : // ignored. In GraphBLAS notation, C{A} = A'*A followed by reduce(C) to scalar.
22 : // This method is for testing only, to check the result of other, faster
23 : // methods. Do not benchmark this method; it is slow and simple by design.
24 :
25 : #define LG_FREE_ALL \
26 : { \
27 : LAGraph_Free ((void **) &Ap, NULL) ; \
28 : LAGraph_Free ((void **) &Aj, NULL) ; \
29 : LAGraph_Free ((void **) &Ax, NULL) ; \
30 : }
31 :
32 : #include "LG_internal.h"
33 : #include "LG_test.h"
34 :
35 : //------------------------------------------------------------------------------
36 : // LG_check_tri
37 : //------------------------------------------------------------------------------
38 :
39 : // Since this method does not modify G->A, it can be tested with LG_BRUTAL.
40 : // See test_TriangleCount for a brutal memory test of this method.
41 :
42 143 : int LG_check_tri // -1 if out of memory, 0 if successful
43 : (
44 : // output
45 : uint64_t *ntri, // # of triangles in A
46 : // input
47 : LAGraph_Graph G, // the structure of G->A must be symmetric
48 : char *msg
49 : )
50 : {
51 :
52 : //--------------------------------------------------------------------------
53 : // check inputs
54 : //--------------------------------------------------------------------------
55 :
56 143 : LG_CLEAR_MSG ;
57 :
58 143 : GrB_Index *Ap = NULL, *Aj = NULL, *Ai = NULL ;
59 143 : void *Ax = NULL ;
60 : GrB_Index Ap_size, Aj_size, Ax_size, n, ncols, Ap_len, Aj_len, Ax_len ;
61 143 : LG_ASSERT (ntri != NULL, GrB_NULL_POINTER) ;
62 143 : LG_TRY (LAGraph_CheckGraph (G, msg)) ;
63 143 : LG_ASSERT (G->nself_edges == 0, LAGRAPH_NO_SELF_EDGES_ALLOWED) ;
64 143 : LG_ASSERT_MSG ((G->kind == LAGraph_ADJACENCY_UNDIRECTED ||
65 : (G->kind == LAGraph_ADJACENCY_DIRECTED &&
66 : G->is_symmetric_structure == LAGraph_TRUE)),
67 : LAGRAPH_SYMMETRIC_STRUCTURE_REQUIRED,
68 : "G->A must be known to be symmetric") ;
69 143 : GRB_TRY (GrB_Matrix_nrows (&n, G->A)) ;
70 143 : GRB_TRY (GrB_Matrix_ncols (&ncols, G->A)) ;
71 :
72 : //--------------------------------------------------------------------------
73 : // export the matrix in CSR form
74 : //--------------------------------------------------------------------------
75 :
76 : size_t typesize ;
77 143 : LG_TRY (LG_check_export (G, &Ap, &Aj, &Ax, &Ap_len, &Aj_len, &Ax_len,
78 : &typesize, msg)) ;
79 :
80 : //--------------------------------------------------------------------------
81 : // compute the # of triangles (each triangle counted 6 times)
82 : //--------------------------------------------------------------------------
83 :
84 37 : int64_t ntriangles = 0 ;
85 37 : Ai = Aj ; // pretend A is symmetric and in CSC format instead
86 :
87 : // masked dot-product method
88 : int64_t j;
89 : #if !defined ( COVERAGE )
90 : #pragma omp parallel for reduction(+:ntriangles) schedule(dynamic,1024)
91 : #endif
92 12987 : for (j = 0 ; j < n ; j++)
93 : {
94 : // for each entry in the lower triangular part of A
95 367098 : for (int64_t p = Ap [j] ; p < Ap [j+1] ; p++)
96 : {
97 354148 : const int64_t i = Ai [p] ;
98 354148 : if (i > j)
99 : {
100 : // ntriangles += A(:,i)' * A(:,j)
101 177074 : int64_t p1 = Ap [i] ;
102 177074 : int64_t p1_end = Ap [i+1] ;
103 177074 : int64_t p2 = Ap [j] ;
104 177074 : int64_t p2_end = Ap [j+1] ;
105 11681606 : while (p1 < p1_end && p2 < p2_end)
106 : {
107 11504532 : int64_t i1 = Ai [p1] ;
108 11504532 : int64_t i2 = Ai [p2] ;
109 11504532 : if (i1 < i2)
110 : {
111 : // A(i1,i) appears before A(i2,j)
112 3055392 : p1++ ;
113 : }
114 8449140 : else if (i2 < i1)
115 : {
116 : // A(i2,j) appears before A(i1,i)
117 4316361 : p2++ ;
118 : }
119 : else // i1 == i2 == k
120 : {
121 : // A(k,i) and A(k,j) are the next entries to merge
122 4132779 : ntriangles++ ;
123 4132779 : p1++ ;
124 4132779 : p2++ ;
125 : }
126 : }
127 : }
128 : }
129 : }
130 37 : ntriangles = ntriangles / 3 ;
131 :
132 : //--------------------------------------------------------------------------
133 : // free workspace and return result
134 : //--------------------------------------------------------------------------
135 :
136 37 : LG_FREE_ALL ;
137 37 : (*ntri) = ntriangles ;
138 37 : return (GrB_SUCCESS) ;
139 : }
|
