Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LG_check_ktruss: construct the ktruss of 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 ktruss method. This method is for testing only, to
19 : // check the result of other, faster methods. Do not benchmark this method; it
20 : // is slow and simple by design. G->A must be symmetric, with no entries on
21 : // its diagonal.
22 :
23 : #define LG_FREE_WORK \
24 : { \
25 : LAGraph_Free ((void **) &Cp, NULL) ; \
26 : LAGraph_Free ((void **) &Cj, NULL) ; \
27 : LAGraph_Free ((void **) &Cx, NULL) ; \
28 : LAGraph_Free ((void **) &Ax, NULL) ; \
29 : }
30 :
31 : #define LG_FREE_ALL \
32 : { \
33 : LG_FREE_WORK ; \
34 : GrB_free (&C) ; \
35 : }
36 :
37 : #include "LG_internal.h"
38 : #include "LG_test.h"
39 :
40 30 : int LG_check_ktruss
41 : (
42 : // output
43 : GrB_Matrix *C_handle, // the ktruss of G->A, of type GrB_UINT32
44 : // input
45 : LAGraph_Graph G, // the structure of G->A must be symmetric
46 : uint32_t k,
47 : char *msg
48 : )
49 : {
50 :
51 : //--------------------------------------------------------------------------
52 : // check inputs
53 : //--------------------------------------------------------------------------
54 :
55 30 : LG_CLEAR_MSG ;
56 :
57 30 : GrB_Matrix C = NULL ;
58 30 : GrB_Index *Cp = NULL, *Cj = NULL ;
59 30 : uint32_t *Cx = NULL ;
60 30 : void *Ax = NULL ;
61 : GrB_Index n, ncols, Cp_len, Cj_len, Cx_len, nvals1, nvals2 ;
62 30 : LG_ASSERT (C_handle != NULL, GrB_NULL_POINTER) ;
63 30 : LG_TRY (LAGraph_CheckGraph (G, msg)) ;
64 30 : LG_ASSERT_MSG (G->nself_edges == 0, -104, "G->nself_edges must be zero") ;
65 30 : if (G->kind == LAGraph_ADJACENCY_UNDIRECTED ||
66 9 : (G->kind == LAGraph_ADJACENCY_DIRECTED &&
67 9 : G->is_symmetric_structure == LAGraph_TRUE))
68 : {
69 : // the structure of A is known to be symmetric
70 : ;
71 : }
72 : else
73 : {
74 : // A is not known to be symmetric
75 1 : LG_ASSERT_MSG (false, -1005, "G->A must be symmetric") ;
76 : }
77 29 : GRB_TRY (GrB_Matrix_nrows (&n, G->A)) ;
78 29 : GRB_TRY (GrB_Matrix_ncols (&ncols, G->A)) ;
79 29 : LG_ASSERT_MSG (n == ncols, -1001, "A must be square") ;
80 :
81 : //--------------------------------------------------------------------------
82 : // export G->A in CSR form and discard its values
83 : //--------------------------------------------------------------------------
84 :
85 : size_t typesize ;
86 29 : LG_TRY (LG_check_export (G, &Cp, &Cj, &Ax, &Cp_len, &Cj_len, &Cx_len,
87 : &typesize, msg)) ;
88 29 : LAGraph_Free ((void **) &Ax, NULL) ;
89 :
90 : //--------------------------------------------------------------------------
91 : // allocate Cx
92 : //--------------------------------------------------------------------------
93 :
94 29 : LG_TRY (LAGraph_Malloc ((void **) &Cx, Cx_len, sizeof (uint32_t), msg)) ;
95 :
96 : //--------------------------------------------------------------------------
97 : // construct the k-truss of G->A
98 : //--------------------------------------------------------------------------
99 :
100 : while (true)
101 47 : {
102 :
103 : //----------------------------------------------------------------------
104 : // compute the # of triangles incident on each edge of C
105 : //----------------------------------------------------------------------
106 :
107 : // masked dot-product method: C{C}=C*C' using the PLUS_ONE semiring
108 : int64_t i;
109 : #if !defined ( COVERAGE )
110 : #pragma omp parallel for schedule(dynamic,1024)
111 : #endif
112 19130 : for (i = 0 ; i < n ; i++)
113 : {
114 : // for each entry in C(i,:)
115 63472 : for (int64_t p = Cp [i] ; p < Cp [i+1] ; p++)
116 : {
117 44418 : const int64_t j = Cj [p] ;
118 44418 : uint32_t cij = 0 ;
119 : // cij += C(i,:) * C(j,:)'
120 44418 : int64_t p1 = Cp [i] ;
121 44418 : int64_t p1_end = Cp [i+1] ;
122 44418 : int64_t p2 = Cp [j] ;
123 44418 : int64_t p2_end = Cp [j+1] ;
124 391970 : while (p1 < p1_end && p2 < p2_end)
125 : {
126 347552 : int64_t j1 = Cj [p1] ;
127 347552 : int64_t j2 = Cj [p2] ;
128 347552 : if (j1 < j2)
129 : {
130 : // C(i,j1) appears before C(j,j2)
131 133513 : p1++ ;
132 : }
133 214039 : else if (j2 < j1)
134 : {
135 : // C(j,j2) appears before C(i,j1)
136 133513 : p2++ ;
137 : }
138 : else // j1 == j2
139 : {
140 : // C(i,j1) and C(j,j1) are the next entries to merge
141 80526 : cij++ ;
142 80526 : p1++ ;
143 80526 : p2++ ;
144 : }
145 : }
146 44418 : Cx [p] = cij ;
147 : }
148 : }
149 :
150 : //----------------------------------------------------------------------
151 : // import C in CSR form
152 : //----------------------------------------------------------------------
153 :
154 76 : GRB_TRY (GrB_Matrix_import_UINT32 (&C, GrB_UINT32, n, n,
155 : Cp, Cj, Cx, Cp_len, Cj_len, Cx_len, GrB_CSR_FORMAT)) ;
156 76 : GRB_TRY (GrB_Matrix_nvals (&nvals1, C)) ;
157 :
158 : //----------------------------------------------------------------------
159 : // keep entries >= k-2 and check for convergence
160 : //----------------------------------------------------------------------
161 :
162 76 : GRB_TRY (GrB_select (C, NULL, NULL, GrB_VALUEGE_UINT32, C, k-2, NULL)) ;
163 76 : GRB_TRY (GrB_Matrix_nvals (&nvals2, C)) ;
164 76 : if (nvals1 == nvals2)
165 : {
166 : // C is now the k-truss of G->A
167 29 : LG_FREE_WORK ;
168 29 : (*C_handle) = C ;
169 29 : return (GrB_SUCCESS) ;
170 : }
171 :
172 : //----------------------------------------------------------------------
173 : // export C in CSR form for the next iteration and free it
174 : //----------------------------------------------------------------------
175 :
176 47 : GRB_TRY (GrB_Matrix_export_UINT32 (Cp, Cj, Cx,
177 : &Cp_len, &Cj_len, &Cx_len, GrB_CSR_FORMAT, C)) ;
178 47 : GRB_TRY (GrB_free (&C)) ;
179 : }
180 : }
|
