Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LAGraph/src/test/test_Cached_Degree.c: test LAGraph_Cached_*Degree
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 "LAGraph_test.h"
19 :
20 : //------------------------------------------------------------------------------
21 : // global variables
22 : //------------------------------------------------------------------------------
23 :
24 : LAGraph_Graph G = NULL ;
25 : char msg [LAGRAPH_MSG_LEN] ;
26 : GrB_Matrix A = NULL ;
27 : #define LEN 512
28 : char filename [LEN+1] ;
29 :
30 : //------------------------------------------------------------------------------
31 : // setup: start a test
32 : //------------------------------------------------------------------------------
33 :
34 1 : void setup (void)
35 : {
36 1 : OK (LAGraph_Init (msg)) ;
37 1 : }
38 :
39 : //------------------------------------------------------------------------------
40 : // teardown: finalize a test
41 : //------------------------------------------------------------------------------
42 :
43 1 : void teardown (void)
44 : {
45 1 : OK (LAGraph_Finalize (msg)) ;
46 1 : }
47 :
48 : //------------------------------------------------------------------------------
49 : // check_degree: check a row or column degree vector
50 : //------------------------------------------------------------------------------
51 :
52 516 : void check_degree
53 : (
54 : GrB_Vector Degree,
55 : GrB_Index n,
56 : const int *degree
57 : )
58 : {
59 : GrB_Index n2 ;
60 516 : OK (GrB_Vector_size (&n2, Degree)) ;
61 516 : TEST_CHECK (n == n2) ;
62 6048 : for (int k = 0 ; k < n ; k++)
63 : {
64 : int64_t degk ;
65 5532 : GrB_Info info = GrB_Vector_extractElement (°k, Degree, k) ;
66 5532 : TEST_CHECK (info == GrB_NO_VALUE || info == GrB_SUCCESS) ;
67 5532 : if (info == GrB_NO_VALUE)
68 : {
69 156 : TEST_CHECK (degree [k] == 0) ;
70 : }
71 : else
72 : {
73 5376 : TEST_CHECK (degree [k] == degk) ;
74 : }
75 : }
76 516 : }
77 :
78 : //------------------------------------------------------------------------------
79 : // test_Cached_Degree: test LAGraph_Cached_*Degree
80 : //------------------------------------------------------------------------------
81 :
82 : typedef struct
83 : {
84 : const char *name ;
85 : const int out_deg [67] ;
86 : const int in_deg [67] ;
87 : }
88 : matrix_info ;
89 :
90 : const matrix_info files [ ] =
91 : {
92 : { "A.mtx",
93 : { 3, 5, 5, 5, 3, 4, 5, },
94 : { 3, 5, 5, 5, 3, 4, 5, }, },
95 : { "LFAT5.mtx",
96 : { 3, 2, 2, 4, 4, 3, 3, 5, 5, 2, 2, 4, 4, 3, },
97 : { 3, 2, 2, 4, 4, 3, 3, 5, 5, 2, 2, 4, 4, 3, }, },
98 : { "cover.mtx",
99 : { 2, 2, 1, 2, 1, 1, 3, },
100 : { 1, 1, 3, 2, 2, 2, 1, }, },
101 : { "cover_structure.mtx",
102 : { 2, 2, 1, 2, 1, 1, 3, },
103 : { 1, 1, 3, 2, 2, 2, 1, }, },
104 : { "full.mtx",
105 : { 3, 3, 3, },
106 : { 3, 3, 3, }, },
107 : { "full_symmetric.mtx",
108 : { 4, 4, 4, 4, },
109 : { 4, 4, 4, 4, }, },
110 : { "karate.mtx",
111 : { 16, 9, 10, 6, 3, 4, 4, 4, 5, 2, 3, 1, 2, 5, 2, 2, 2, 2, 2, 3,
112 : 2, 2, 2, 5, 3, 3, 2, 4, 3, 4, 4, 6, 12, 17, },
113 : { 16, 9, 10, 6, 3, 4, 4, 4, 5, 2, 3, 1, 2, 5, 2, 2, 2, 2, 2, 3,
114 : 2, 2, 2, 5, 3, 3, 2, 4, 3, 4, 4, 6, 12, 17, }, },
115 : { "ldbc-cdlp-directed-example.mtx",
116 : { 3, 2, 2, 2, 3, 2, 3, 1, },
117 : { 2, 2, 2, 1, 3, 4, 3, 1, }, },
118 : { "ldbc-cdlp-undirected-example.mtx",
119 : { 3, 2, 2, 3, 4, 3, 3, 4, },
120 : { 3, 2, 2, 3, 4, 3, 3, 4, }, },
121 : { "ldbc-directed-example-bool.mtx",
122 : { 2, 3, 4, 0, 3, 2, 1, 1, 1, 0, },
123 : { 2, 0, 3, 5, 3, 0, 0, 2, 0, 2, }, },
124 : { "ldbc-directed-example-unweighted.mtx",
125 : { 2, 3, 4, 0, 3, 2, 1, 1, 1, 0, },
126 : { 2, 0, 3, 5, 3, 0, 0, 2, 0, 2, }, },
127 : { "ldbc-directed-example.mtx",
128 : { 2, 3, 4, 0, 3, 2, 1, 1, 1, 0, },
129 : { 2, 0, 3, 5, 3, 0, 0, 2, 0, 2, }, },
130 : { "ldbc-undirected-example-bool.mtx",
131 : { 2, 4, 2, 3, 5, 2, 3, 2, 1, },
132 : { 2, 4, 2, 3, 5, 2, 3, 2, 1, }, },
133 : { "ldbc-undirected-example-unweighted.mtx",
134 : { 2, 4, 2, 3, 5, 2, 3, 2, 1, },
135 : { 2, 4, 2, 3, 5, 2, 3, 2, 1, }, },
136 : { "ldbc-undirected-example.mtx",
137 : { 2, 4, 2, 3, 5, 2, 3, 2, 1, },
138 : { 2, 4, 2, 3, 5, 2, 3, 2, 1, }, },
139 : { "ldbc-wcc-example.mtx",
140 : { 3, 3, 5, 5, 5, 2, 1, 3, 1, 2, },
141 : { 3, 3, 5, 5, 5, 2, 1, 3, 1, 2, }, },
142 : { "matrix_bool.mtx",
143 : { 2, 2, 1, 2, 1, 1, 3, },
144 : { 1, 1, 3, 2, 2, 2, 1, }, },
145 : { "matrix_fp32.mtx",
146 : { 2, 2, 1, 2, 1, 1, 3, },
147 : { 1, 1, 3, 2, 2, 2, 1, }, },
148 : { "matrix_fp32_structure.mtx",
149 : { 2, 2, 1, 2, 1, 1, 3, },
150 : { 1, 1, 3, 2, 2, 2, 1, }, },
151 : { "matrix_fp64.mtx",
152 : { 2, 2, 1, 2, 1, 1, 3, },
153 : { 1, 1, 3, 2, 2, 2, 1, }, },
154 : { "matrix_int16.mtx",
155 : { 2, 2, 1, 2, 1, 1, 3, },
156 : { 1, 1, 3, 2, 2, 2, 1, }, },
157 : { "matrix_int32.mtx",
158 : { 2, 2, 1, 2, 1, 1, 3, },
159 : { 1, 1, 3, 2, 2, 2, 1, }, },
160 : { "matrix_int64.mtx",
161 : { 2, 2, 1, 2, 1, 1, 3, },
162 : { 1, 1, 3, 2, 2, 2, 1, }, },
163 : { "matrix_int8.mtx",
164 : { 2, 2, 1, 2, 1, 1, 3, },
165 : { 1, 1, 3, 2, 2, 2, 1, }, },
166 : { "matrix_uint16.mtx",
167 : { 2, 2, 1, 2, 1, 1, 3, },
168 : { 1, 1, 3, 2, 2, 2, 1, }, },
169 : { "matrix_uint32.mtx",
170 : { 2, 2, 1, 2, 1, 1, 3, },
171 : { 1, 1, 3, 2, 2, 2, 1, }, },
172 : { "matrix_uint64.mtx",
173 : { 2, 2, 1, 2, 1, 1, 3, },
174 : { 1, 1, 3, 2, 2, 2, 1, }, },
175 : { "matrix_uint8.mtx",
176 : { 2, 2, 1, 2, 1, 1, 3, },
177 : { 1, 1, 3, 2, 2, 2, 1, }, },
178 : { "msf1.mtx",
179 : { 2, 2, 1, 1, 1, 1, },
180 : { 1, 1, 2, 2, 0, 2, }, },
181 : { "msf2.mtx",
182 : { 2, 3, 3, 2, 1, 1, 0, 0, },
183 : { 0, 1, 1, 1, 2, 2, 2, 3, }, },
184 : { "msf3.mtx",
185 : { 2, 2, 2, 1, 0, },
186 : { 0, 1, 1, 2, 3, }, },
187 : { "structure.mtx",
188 : { 2, 2, 1, 2, 1, 1, 3, },
189 : { 1, 1, 3, 2, 2, 2, 1, }, },
190 : { "sample.mtx",
191 : { 3, 2, 1, 2, 2, 1, 1, 0, },
192 : { 0, 1, 3, 1, 3, 1, 1, 2, }, },
193 : { "sample2.mtx",
194 : { 2, 3, 4, 3, 5, 5, 3, 3, },
195 : { 2, 3, 4, 3, 5, 5, 3, 3, }, },
196 : { "skew_fp32.mtx",
197 : { 3, 3, 3, 4, 3, 4, },
198 : { 3, 3, 3, 4, 3, 4, }, },
199 : { "skew_fp64.mtx",
200 : { 3, 3, 3, 4, 3, 4, },
201 : { 3, 3, 3, 4, 3, 4, }, },
202 : { "skew_int16.mtx",
203 : { 3, 3, 3, 4, 3, 4, },
204 : { 3, 3, 3, 4, 3, 4, }, },
205 : { "skew_int32.mtx",
206 : { 3, 3, 3, 4, 3, 4, },
207 : { 3, 3, 3, 4, 3, 4, }, },
208 : { "skew_int64.mtx",
209 : { 3, 3, 3, 4, 3, 4, },
210 : { 3, 3, 3, 4, 3, 4, }, },
211 : { "skew_int8.mtx",
212 : { 3, 3, 3, 4, 3, 4, },
213 : { 3, 3, 3, 4, 3, 4, }, },
214 : { "tree-example.mtx",
215 : { 1, 1, 2, 3, 2, 1, },
216 : { 1, 1, 2, 3, 2, 1, }, },
217 : { "west0067.mtx",
218 : { 3, 3, 3, 3, 5, 5, 5, 5, 5, 6, 3, 3, 3, 3, 4, 5, 5, 5, 5, 5,
219 : 3, 3, 3, 3, 6, 6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 3, 3, 3, 3, 5,
220 : 5, 5, 5, 5, 6, 3, 3, 3, 3, 4, 4, 4, 4, 4, 6, 1, 5, 5, 5, 5,
221 : 5, 5, 5, 5, 5, 5, 5, },
222 : { 10, 4, 4, 4, 4, 3, 5, 3, 3, 3, 3, 2, 5, 5, 5, 5, 4, 5, 2, 10,
223 : 3, 3, 3, 3, 3, 4, 4, 4, 4, 3, 10, 3, 3, 3, 3, 3, 10, 5, 5, 5,
224 : 5, 4, 5, 4, 4, 4, 4, 3, 10, 3, 3, 3, 3, 3, 10, 5, 5, 5, 5, 4,
225 : 5, 4, 4, 4, 4, 3, 5, }, },
226 : { "west0067_jumbled.mtx",
227 : { 3, 3, 3, 3, 5, 5, 5, 5, 5, 6, 3, 3, 3, 3, 4, 5, 5, 5, 5, 5,
228 : 3, 3, 3, 3, 6, 6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 3, 3, 3, 3, 5,
229 : 5, 5, 5, 5, 6, 3, 3, 3, 3, 4, 4, 4, 4, 4, 6, 1, 5, 5, 5, 5,
230 : 5, 5, 5, 5, 5, 5, 5, },
231 : { 10, 4, 4, 4, 4, 3, 5, 3, 3, 3, 3, 2, 5, 5, 5, 5, 4, 5, 2, 10,
232 : 3, 3, 3, 3, 3, 4, 4, 4, 4, 3, 10, 3, 3, 3, 3, 3, 10, 5, 5, 5,
233 : 5, 4, 5, 4, 4, 4, 4, 3, 10, 3, 3, 3, 3, 3, 10, 5, 5, 5, 5, 4,
234 : 5, 4, 4, 4, 4, 3, 5, }, },
235 : { "", { 0 }, { 0 }}
236 : } ;
237 :
238 : //-----------------------------------------------------------------------------
239 : // test_Cached_Degree
240 : //-----------------------------------------------------------------------------
241 :
242 1 : void test_Cached_Degree (void)
243 : {
244 1 : setup ( ) ;
245 :
246 1 : for (int k = 0 ; ; k++)
247 43 : {
248 :
249 : // load the matrix as A
250 44 : const char *aname = files [k].name ;
251 44 : if (strlen (aname) == 0) break;
252 43 : const int *out_deg = files [k].out_deg ;
253 43 : const int *in_deg = files [k].in_deg ;
254 43 : TEST_CASE (aname) ;
255 43 : snprintf (filename, LEN, LG_DATA_DIR "%s", aname) ;
256 43 : FILE *f = fopen (filename, "r") ;
257 43 : TEST_CHECK (f != NULL) ;
258 43 : OK (LAGraph_MMRead (&A, f, msg)) ;
259 43 : OK (fclose (f)) ;
260 43 : TEST_MSG ("Loading of adjacency matrix failed") ;
261 :
262 : // construct the graph G with adjacency matrix A
263 43 : OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_DIRECTED, msg)) ;
264 43 : TEST_CHECK (A == NULL) ;
265 :
266 172 : for (int trial = 0 ; trial <= 2 ; trial++)
267 : {
268 : // create the G->out_degree cached property and check it
269 129 : OK (LAGraph_Cached_OutDegree (G, msg)) ;
270 : GrB_Index n ;
271 129 : OK (GrB_Matrix_nrows (&n, G->A)) ;
272 129 : check_degree (G->out_degree, n, out_deg) ;
273 :
274 129 : if (trial == 2)
275 : {
276 : // use G->AT to compute G->in_degree
277 43 : OK (LAGraph_DeleteCached (G, msg)) ;
278 43 : OK (LAGraph_Cached_AT (G, msg)) ;
279 : }
280 :
281 : // create the G->in_degree cached property and check it
282 129 : OK (LAGraph_Cached_InDegree (G, msg)) ;
283 129 : OK (GrB_Matrix_ncols (&n, G->A)) ;
284 129 : check_degree (G->in_degree, n, in_deg) ;
285 : }
286 :
287 43 : OK (LAGraph_Delete (&G, msg)) ;
288 : }
289 :
290 : // check error handling
291 1 : int status = LAGraph_Cached_OutDegree (NULL, msg) ;
292 1 : printf ("\nstatus: %d, msg: %s\n", status, msg) ;
293 1 : TEST_CHECK (status == GrB_NULL_POINTER) ;
294 1 : status = LAGraph_Cached_InDegree (NULL, msg) ;
295 1 : printf ("status: %d, msg: %s\n", status, msg) ;
296 1 : TEST_CHECK (status == GrB_NULL_POINTER) ;
297 :
298 1 : teardown ( ) ;
299 1 : }
300 :
301 : //-----------------------------------------------------------------------------
302 : // test_Cached_Degree_brutal
303 : //-----------------------------------------------------------------------------
304 :
305 : #if LAGRAPH_SUITESPARSE
306 1 : void test_Cached_Degree_brutal (void)
307 : {
308 1 : OK (LG_brutal_setup (msg)) ;
309 :
310 1 : for (int k = 0 ; ; k++)
311 43 : {
312 :
313 : // load the matrix as A
314 44 : const char *aname = files [k].name ;
315 44 : if (strlen (aname) == 0) break;
316 43 : const int *out_deg = files [k].out_deg ;
317 43 : const int *in_deg = files [k].in_deg ;
318 43 : TEST_CASE (aname) ;
319 43 : snprintf (filename, LEN, LG_DATA_DIR "%s", aname) ;
320 43 : FILE *f = fopen (filename, "r") ;
321 43 : TEST_CHECK (f != NULL) ;
322 43 : OK (LAGraph_MMRead (&A, f, msg)) ;
323 43 : OK (fclose (f)) ;
324 43 : TEST_MSG ("Loading of adjacency matrix failed") ;
325 :
326 : // construct the graph G with adjacency matrix A
327 43 : OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_DIRECTED, msg)) ;
328 43 : TEST_CHECK (A == NULL) ;
329 :
330 172 : for (int trial = 0 ; trial <= 2 ; trial++)
331 : {
332 : // create the G->out_degree cached property and check it
333 425 : LG_BRUTAL (LAGraph_Cached_OutDegree (G, msg)) ;
334 : GrB_Index n ;
335 129 : OK (GrB_Matrix_nrows (&n, G->A)) ;
336 129 : check_degree (G->out_degree, n, out_deg) ;
337 :
338 129 : if (trial == 2)
339 : {
340 : // use G->AT to compute G->in_degree
341 43 : OK (LAGraph_DeleteCached (G, msg)) ;
342 43 : OK (LAGraph_Cached_AT (G, msg)) ;
343 : }
344 :
345 : // create the G->in_degree cached property and check it
346 732 : LG_BRUTAL (LAGraph_Cached_InDegree (G, msg)) ;
347 129 : OK (GrB_Matrix_ncols (&n, G->A)) ;
348 129 : check_degree (G->in_degree, n, in_deg) ;
349 : }
350 :
351 43 : OK (LAGraph_Delete (&G, msg)) ;
352 : }
353 :
354 1 : OK (LG_brutal_teardown (msg)) ;
355 1 : }
356 : #endif
357 :
358 : //-----------------------------------------------------------------------------
359 : // TEST_LIST: the list of tasks for this entire test
360 : //-----------------------------------------------------------------------------
361 :
362 : TEST_LIST =
363 : {
364 : { "test_Degree", test_Cached_Degree },
365 : #if LAGRAPH_SUITESPARSE
366 : { "test_Degree_brutal", test_Cached_Degree_brutal },
367 : #endif
368 : { NULL, NULL }
369 : } ;
|
