Line data Source code
1 : //----------------------------------------------------------------------------
2 : // LAGraph/experimental/test/test_AllKtruss.c: test cases for all-k-truss
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 : #include <stdio.h>
19 : #include <acutest.h>
20 :
21 : #include "LAGraphX.h"
22 : #include "LAGraph_test.h"
23 : #include "LG_Xtest.h"
24 :
25 : char msg [LAGRAPH_MSG_LEN] ;
26 : LAGraph_Graph G = NULL ;
27 : GrB_Matrix A = NULL ;
28 : GrB_Matrix C1 = NULL ;
29 : #define LEN 512
30 : char filename [LEN+1] ;
31 :
32 : typedef struct
33 : {
34 : uint32_t ntriangles ;
35 : const char *name ;
36 : }
37 : matrix_info ;
38 :
39 : const matrix_info files [ ] =
40 : {
41 : { 342300, "bcsstk13.mtx" },
42 : { 11, "A.mtx" },
43 : { 2016, "jagmesh7.mtx" },
44 : { 45, "karate.mtx" },
45 : { 6, "ldbc-cdlp-undirected-example.mtx" },
46 : { 4, "ldbc-undirected-example-bool.mtx" },
47 : { 4, "ldbc-undirected-example-unweighted.mtx" },
48 : { 4, "ldbc-undirected-example.mtx" },
49 : { 5, "ldbc-wcc-example.mtx" },
50 : { 0, "" },
51 : } ;
52 :
53 : //****************************************************************************
54 1 : void test_AllKTruss (void)
55 : {
56 1 : LAGraph_Init (msg) ;
57 : // OK (LG_SET_BURBLE (true)) ;
58 :
59 1 : for (int id = 0 ; ; id++)
60 9 : {
61 :
62 : // load the matrix as A
63 10 : const char *aname = files [id].name ;
64 10 : uint32_t ntriangles = files [id].ntriangles ;
65 10 : if (strlen (aname) == 0) break;
66 9 : printf ("\n================================== %s:\n", aname) ;
67 9 : TEST_CASE (aname) ;
68 9 : snprintf (filename, LEN, LG_DATA_DIR "%s", aname) ;
69 9 : FILE *f = fopen (filename, "r") ;
70 9 : TEST_CHECK (f != NULL) ;
71 9 : OK (LAGraph_MMRead (&A, f, msg)) ;
72 9 : TEST_MSG ("Loading of adjacency matrix failed") ;
73 9 : fclose (f) ;
74 :
75 : // construct an undirected graph G with adjacency matrix A
76 9 : OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_UNDIRECTED, msg)) ;
77 9 : TEST_CHECK (A == NULL) ;
78 :
79 : // check for self-edges
80 9 : OK (LAGraph_Cached_NSelfEdges (G, msg)) ;
81 9 : if (G->nself_edges != 0)
82 : {
83 : // remove self-edges
84 2 : printf ("graph has %g self edges\n", (double) G->nself_edges) ;
85 2 : OK (LAGraph_DeleteSelfEdges (G, msg)) ;
86 2 : printf ("now has %g self edges\n", (double) G->nself_edges) ;
87 2 : TEST_CHECK (G->nself_edges == 0) ;
88 : }
89 :
90 : // compute each k-truss
91 9 : bool ok = false ;
92 : GrB_Index n ;
93 : int64_t kmax ;
94 9 : OK (GrB_Matrix_nrows (&n, G->A)) ;
95 : GrB_Matrix *Cset ;
96 : int64_t *ntris, *nedges, *nsteps ;
97 9 : OK (LAGraph_Calloc ((void **) &Cset , n, sizeof (GrB_Matrix), msg)) ;
98 9 : OK (LAGraph_Malloc ((void **) &ntris , n, sizeof (int64_t), msg)) ;
99 9 : OK (LAGraph_Malloc ((void **) &nedges, n, sizeof (int64_t), msg)) ;
100 9 : OK (LAGraph_Malloc ((void **) &nsteps, n, sizeof (int64_t), msg)) ;
101 :
102 9 : OK (LAGraph_AllKTruss (Cset, &kmax, ntris, nedges, nsteps, G, msg)) ;
103 9 : printf ("all k-truss: kmax %g\n", (double) kmax) ;
104 :
105 : // compute each k-truss using LAGraph_KTruss, and compare
106 48 : for (int k = 3 ; k < n ; k++)
107 : {
108 : // printf ("\n%d-truss:\n", k) ;
109 48 : TEST_CHECK (k <= kmax) ;
110 : // compute the k-truss
111 48 : OK (LAGraph_KTruss (&C1, G, k, msg)) ;
112 :
113 : // check the result
114 : GrB_Index nvals ;
115 48 : OK (GrB_Matrix_nvals (&nvals, C1)) ;
116 48 : OK (LAGraph_Matrix_IsEqual (&ok, C1, Cset [k], msg)) ;
117 48 : TEST_CHECK (ok) ;
118 :
119 : // count the triangles in the 3-truss
120 48 : uint32_t nt = 0 ;
121 48 : OK (GrB_reduce (&nt, NULL, GrB_PLUS_MONOID_UINT32, C1, NULL)) ;
122 48 : nt = nt / 6 ;
123 48 : if (k == 3)
124 : {
125 9 : TEST_CHECK (nt == ntriangles) ;
126 : }
127 48 : TEST_CHECK (nt == ntris [k]) ;
128 48 : TEST_CHECK (nvals == 2 * nedges [k]) ;
129 48 : TEST_CHECK (nsteps [k] >= 0) ;
130 :
131 : // free C1, and break if C1 is empty
132 48 : OK (GrB_free (&C1)) ;
133 48 : if (nvals == 0)
134 : {
135 9 : TEST_CHECK (k == kmax) ;
136 9 : break ;
137 : }
138 : }
139 :
140 : // convert to directed with symmetric structure and recompute
141 9 : G->kind = LAGraph_ADJACENCY_DIRECTED ;
142 9 : G->is_symmetric_structure = LAGraph_TRUE ;
143 : int64_t k2 ;
144 : GrB_Matrix *Cset2 ;
145 : int64_t *ntris2, *nedges2, *nsteps2 ;
146 9 : OK (LAGraph_Calloc ((void **) &Cset2 , n, sizeof (GrB_Matrix), msg)) ;
147 9 : OK (LAGraph_Malloc ((void **) &ntris2 , n, sizeof (int64_t), msg)) ;
148 9 : OK (LAGraph_Malloc ((void **) &nedges2, n, sizeof (int64_t), msg)) ;
149 9 : OK (LAGraph_Malloc ((void **) &nsteps2, n, sizeof (int64_t), msg)) ;
150 :
151 9 : OK (LAGraph_AllKTruss (Cset2, &k2, ntris2, nedges2, nsteps2, G, msg)) ;
152 9 : TEST_CHECK (k2 == kmax) ;
153 84 : for (int k = 0 ; k <= kmax ; k++)
154 : {
155 75 : TEST_CHECK (ntris2 [k] == ntris [k]) ;
156 75 : TEST_CHECK (nedges2 [k] == nedges [k]) ;
157 75 : TEST_CHECK (nsteps2 [k] == nsteps [k]) ;
158 75 : if (k < 3)
159 : {
160 27 : TEST_CHECK (Cset [k] == NULL) ;
161 27 : TEST_CHECK (Cset2 [k] == NULL) ;
162 : }
163 : else
164 : {
165 48 : OK (LAGraph_Matrix_IsEqual (&ok, Cset [k], Cset2 [k], msg)) ;
166 : }
167 : // if (!ok)
168 : // {
169 : // GxB_print (Cset [k], 2) ;
170 : // GxB_print (Cset2 [k], 2) ;
171 : // }
172 75 : TEST_CHECK (ok) ;
173 75 : OK (GrB_free (&(Cset [k]))) ;
174 75 : OK (GrB_free (&(Cset2 [k]))) ;
175 : }
176 :
177 9 : LAGraph_Free ((void **) &Cset, NULL) ;
178 9 : LAGraph_Free ((void **) &ntris, NULL) ;
179 9 : LAGraph_Free ((void **) &nedges, NULL) ;
180 9 : LAGraph_Free ((void **) &nsteps, NULL) ;
181 :
182 9 : LAGraph_Free ((void **) &Cset2, NULL) ;
183 9 : LAGraph_Free ((void **) &ntris2, NULL) ;
184 9 : LAGraph_Free ((void **) &nedges2, NULL) ;
185 9 : LAGraph_Free ((void **) &nsteps2, NULL) ;
186 :
187 9 : OK (LAGraph_Delete (&G, msg)) ;
188 : }
189 :
190 1 : LAGraph_Finalize (msg) ;
191 1 : }
192 :
193 : //------------------------------------------------------------------------------
194 : // test_AllKTruss_errors
195 : //------------------------------------------------------------------------------
196 :
197 1 : void test_allktruss_errors (void)
198 : {
199 1 : LAGraph_Init (msg) ;
200 :
201 1 : snprintf (filename, LEN, LG_DATA_DIR "%s", "karate.mtx") ;
202 1 : FILE *f = fopen (filename, "r") ;
203 1 : TEST_CHECK (f != NULL) ;
204 1 : OK (LAGraph_MMRead (&A, f, msg)) ;
205 1 : TEST_MSG ("Loading of adjacency matrix failed") ;
206 1 : fclose (f) ;
207 :
208 : // construct an undirected graph G with adjacency matrix A
209 1 : OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_UNDIRECTED, msg)) ;
210 1 : TEST_CHECK (A == NULL) ;
211 :
212 1 : OK (LAGraph_Cached_NSelfEdges (G, msg)) ;
213 :
214 : GrB_Index n ;
215 : int64_t kmax ;
216 1 : OK (GrB_Matrix_nrows (&n, G->A)) ;
217 : int64_t *ntris, *nedges, *nsteps ;
218 : GrB_Matrix *Cset ;
219 1 : OK (LAGraph_Calloc ((void **) &Cset , n, sizeof (GrB_Matrix), msg)) ;
220 1 : OK (LAGraph_Malloc ((void **) &ntris , n, sizeof (int64_t), msg)) ;
221 1 : OK (LAGraph_Malloc ((void **) &nedges, n, sizeof (int64_t), msg)) ;
222 1 : OK (LAGraph_Malloc ((void **) &nsteps, n, sizeof (int64_t), msg)) ;
223 :
224 : // kmax is NULL
225 1 : int result = LAGraph_AllKTruss (Cset, NULL, ntris, nedges, nsteps, G, msg) ;
226 1 : printf ("\nresult: %d %s\n", result, msg) ;
227 1 : TEST_CHECK (result == GrB_NULL_POINTER) ;
228 :
229 : // G is invalid
230 1 : result = LAGraph_AllKTruss (Cset, &kmax, ntris, nedges, nsteps, NULL, msg) ;
231 1 : printf ("\nresult: %d %s\n", result, msg) ;
232 1 : TEST_CHECK (result == GrB_NULL_POINTER) ;
233 :
234 : // G may have self edges
235 1 : G->nself_edges = LAGRAPH_UNKNOWN ;
236 1 : result = LAGraph_AllKTruss (Cset, &kmax, ntris, nedges, nsteps, G, msg) ;
237 1 : printf ("\nresult: %d %s\n", result, msg) ;
238 1 : TEST_CHECK (result == -1004) ;
239 :
240 : // G is undirected
241 1 : G->nself_edges = 0 ;
242 1 : G->kind = LAGraph_ADJACENCY_DIRECTED ;
243 1 : G->is_symmetric_structure = LAGraph_FALSE ;
244 1 : result = LAGraph_AllKTruss (Cset, &kmax, ntris, nedges, nsteps, G, msg) ;
245 1 : printf ("\nresult: %d %s\n", result, msg) ;
246 1 : TEST_CHECK (result == -1005) ;
247 :
248 1 : LAGraph_Free ((void **) &Cset, NULL) ;
249 1 : LAGraph_Free ((void **) &ntris, NULL) ;
250 1 : LAGraph_Free ((void **) &nedges, NULL) ;
251 1 : LAGraph_Free ((void **) &nsteps, NULL) ;
252 :
253 1 : OK (LAGraph_Delete (&G, msg)) ;
254 1 : LAGraph_Finalize (msg) ;
255 1 : }
256 :
257 : //****************************************************************************
258 :
259 : TEST_LIST = {
260 : {"allktruss", test_AllKTruss},
261 : {"allktruss_errors", test_allktruss_errors},
262 : {NULL, NULL}
263 : };
|
