Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LAGraph/src/test/test_SortByDegree test LAGr_SortByDegree
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, H = NULL ;
25 : char msg [LAGRAPH_MSG_LEN] ;
26 : GrB_Matrix A = NULL, B = NULL ;
27 : GrB_Vector d = NULL ;
28 : #define LEN 512
29 : char filename [LEN+1] ;
30 : int64_t *P = NULL ;
31 : bool *W = NULL ;
32 : GrB_Index n, nrows, ncols ;
33 : bool is_symmetric ;
34 : int kind ;
35 :
36 : //------------------------------------------------------------------------------
37 : // setup: start a test
38 : //------------------------------------------------------------------------------
39 :
40 2 : void setup (void)
41 : {
42 2 : OK (LAGraph_Init (msg)) ;
43 2 : }
44 :
45 : //------------------------------------------------------------------------------
46 : // teardown: finalize a test
47 : //------------------------------------------------------------------------------
48 :
49 2 : void teardown (void)
50 : {
51 2 : OK (LAGraph_Finalize (msg)) ;
52 2 : }
53 :
54 : //------------------------------------------------------------------------------
55 : // test_SortByDegree test LAGr_SortByDegree
56 : //------------------------------------------------------------------------------
57 :
58 : const char *files [ ] =
59 : {
60 : "A.mtx",
61 : "LFAT5.mtx",
62 : "cover.mtx",
63 : "full.mtx",
64 : "full_symmetric.mtx",
65 : "karate.mtx",
66 : "ldbc-cdlp-directed-example.mtx",
67 : "ldbc-cdlp-undirected-example.mtx",
68 : "ldbc-directed-example-bool.mtx",
69 : "ldbc-directed-example-unweighted.mtx",
70 : "ldbc-directed-example.mtx",
71 : "ldbc-undirected-example-bool.mtx",
72 : "ldbc-undirected-example-unweighted.mtx",
73 : "ldbc-undirected-example.mtx",
74 : "ldbc-wcc-example.mtx",
75 : "matrix_int16.mtx",
76 : "msf1.mtx",
77 : "msf2.mtx",
78 : "msf3.mtx",
79 : "structure.mtx",
80 : "sample.mtx",
81 : "sample2.mtx",
82 : "skew_fp32.mtx",
83 : "tree-example.mtx",
84 : "west0067.mtx",
85 : "",
86 : } ;
87 :
88 1 : void test_SortByDegree (void)
89 : {
90 1 : setup ( ) ;
91 :
92 1 : for (int kk = 0 ; ; kk++)
93 25 : {
94 :
95 : // get the name of the test matrix
96 26 : const char *aname = files [kk] ;
97 26 : if (strlen (aname) == 0) break;
98 25 : TEST_CASE (aname) ;
99 25 : printf ("\n############################################# %s\n", aname) ;
100 25 : snprintf (filename, LEN, LG_DATA_DIR "%s", aname) ;
101 :
102 47 : for (int outer = 0 ; outer <= 1 ; outer++)
103 : {
104 :
105 : // load the matrix as A
106 36 : FILE *f = fopen (filename, "r") ;
107 36 : TEST_CHECK (f != NULL) ;
108 36 : OK (LAGraph_MMRead (&A, f, msg)) ;
109 36 : OK (fclose (f)) ;
110 36 : TEST_MSG ("Loading of adjacency matrix failed") ;
111 :
112 : // ensure the matrix is square
113 36 : OK (GrB_Matrix_nrows (&nrows, A)) ;
114 36 : OK (GrB_Matrix_ncols (&ncols, A)) ;
115 36 : TEST_CHECK (nrows == ncols) ;
116 36 : n = nrows ;
117 :
118 : // decide if the graph G is directed or undirected
119 36 : if (outer == 0)
120 : {
121 25 : kind = LAGraph_ADJACENCY_DIRECTED ;
122 25 : printf ("\n#### case: directed graph\n\n") ;
123 : }
124 : else
125 : {
126 11 : kind = LAGraph_ADJACENCY_UNDIRECTED ;
127 11 : printf ("\n#### case: undirected graph\n\n") ;
128 : }
129 :
130 : // construct a graph G with adjacency matrix A
131 36 : TEST_CHECK (A != NULL) ;
132 36 : OK (LAGraph_New (&G, &A, kind, msg)) ;
133 36 : TEST_CHECK (A == NULL) ;
134 36 : TEST_CHECK (G != NULL) ;
135 :
136 : // create the cached properties
137 72 : int ok_result = (kind == LAGraph_ADJACENCY_UNDIRECTED) ?
138 36 : LAGRAPH_CACHE_NOT_NEEDED : GrB_SUCCESS ;
139 36 : int result = LAGraph_Cached_AT (G, msg) ;
140 36 : TEST_CHECK (result == ok_result) ;
141 36 : OK (LAGraph_Cached_OutDegree (G, msg)) ;
142 36 : result = LAGraph_Cached_InDegree (G, msg) ;
143 36 : TEST_CHECK (result == ok_result) ;
144 36 : OK (LAGraph_Cached_IsSymmetricStructure (G, msg)) ;
145 36 : OK (LAGraph_Graph_Print (G, LAGraph_SHORT, stdout, msg)) ;
146 :
147 : // sort 4 different ways
148 180 : for (int trial = 0 ; trial <= 3 ; trial++)
149 : {
150 144 : bool byout = (trial == 0 || trial == 1) ;
151 144 : bool ascending = (trial == 0 || trial == 2) ;
152 :
153 : // sort the graph by degree
154 144 : TEST_CHECK (P == NULL) ;
155 144 : OK (LAGr_SortByDegree (&P, G, byout, ascending, msg)) ;
156 144 : TEST_CHECK (P != NULL) ;
157 :
158 : // ensure P is a permutation of 0..n-1
159 144 : OK (LAGraph_Calloc ((void **) &W, n, sizeof (bool), msg)) ;
160 1736 : for (int k = 0 ; k < n ; k++)
161 : {
162 1592 : int64_t j = P [k] ;
163 1592 : TEST_CHECK (j >= 0 && j < n) ;
164 1592 : TEST_CHECK (W [j] == false) ;
165 1592 : W [j] = true ;
166 : }
167 :
168 : // check the result by constructing a new graph with adjacency
169 : // matrix B = A (P,P)
170 144 : OK (GrB_Matrix_new (&B, GrB_BOOL, n, n)) ;
171 144 : OK (GrB_extract (B, NULL, NULL, G->A,
172 : (GrB_Index *) P, n, (GrB_Index *) P, n, NULL)) ;
173 144 : OK (LAGraph_New (&H, &B, kind, msg)) ;
174 144 : TEST_CHECK (B == NULL) ;
175 144 : TEST_CHECK (H != NULL) ;
176 :
177 : // get the cached properties of H
178 144 : OK (LAGraph_Cached_OutDegree (H, msg)) ;
179 144 : result = LAGraph_Cached_InDegree (H, msg) ;
180 144 : TEST_CHECK (result == ok_result) ;
181 144 : OK (LAGraph_Cached_IsSymmetricStructure (H, msg)) ;
182 144 : TEST_CHECK (G->is_symmetric_structure ==
183 : H->is_symmetric_structure) ;
184 144 : printf ("\nTrial %d, graph H, sorted (%s) by (%s) degrees:\n",
185 : trial, ascending ? "ascending" : "descending",
186 : byout ? "row" : "column") ;
187 144 : OK (LAGraph_Graph_Print (H, LAGraph_SHORT, stdout, msg)) ;
188 :
189 72 : d = (byout || G->is_symmetric_structure == LAGraph_TRUE) ?
190 216 : H->out_degree : H->in_degree ;
191 :
192 : // ensure d is sorted in ascending or descending order
193 144 : int64_t last_deg = (ascending) ? (-1) : (n+1) ;
194 1736 : for (int k = 0 ; k < n ; k++)
195 : {
196 1592 : int64_t deg = 0 ;
197 1592 : GrB_Info info = GrB_Vector_extractElement (°, d, k) ;
198 1592 : TEST_CHECK (info == GrB_NO_VALUE || info == GrB_SUCCESS) ;
199 1592 : if (info == GrB_NO_VALUE) deg = 0 ;
200 1592 : if (ascending)
201 : {
202 796 : TEST_CHECK (last_deg <= deg) ;
203 : }
204 : else
205 : {
206 796 : TEST_CHECK (last_deg >= deg) ;
207 : }
208 1592 : last_deg = deg ;
209 : }
210 :
211 : // free workspace and the graph H
212 144 : OK (LAGraph_Free ((void **) &W, NULL)) ;
213 144 : OK (LAGraph_Free ((void **) &P, NULL)) ;
214 144 : OK (LAGraph_Delete (&H, msg)) ;
215 : }
216 :
217 : // check if the adjacency matrix is symmetric
218 36 : if (outer == 0)
219 : {
220 : // if G->A is symmetric, then continue the outer iteration to
221 : // create an undirected graph. Otherwise just do the directed
222 : // graph
223 25 : OK (LAGraph_Matrix_IsEqual (&is_symmetric, G->A, G->AT, msg)) ;
224 25 : if (!is_symmetric)
225 : {
226 14 : printf ("matrix is unsymmetric; skip undirected case\n") ;
227 14 : OK (LAGraph_Delete (&G, msg)) ;
228 14 : break ;
229 : }
230 : }
231 22 : OK (LAGraph_Delete (&G, msg)) ;
232 : }
233 : }
234 :
235 1 : teardown ( ) ;
236 1 : }
237 :
238 :
239 : //------------------------------------------------------------------------------
240 : // test_SortByDegree_brutal
241 : //------------------------------------------------------------------------------
242 :
243 : #if LAGRAPH_SUITESPARSE
244 1 : void test_SortByDegree_brutal (void)
245 : {
246 1 : OK (LG_brutal_setup (msg)) ;
247 1 : printf ("\n") ;
248 :
249 1 : for (int kk = 0 ; ; kk++)
250 25 : {
251 :
252 : // get the name of the test matrix
253 26 : const char *aname = files [kk] ;
254 26 : if (strlen (aname) == 0) break;
255 25 : TEST_CASE (aname) ;
256 25 : printf ("%s\n", aname) ;
257 25 : snprintf (filename, LEN, LG_DATA_DIR "%s", aname) ;
258 :
259 47 : for (int outer = 0 ; outer <= 1 ; outer++)
260 : {
261 :
262 : // load the matrix as A
263 36 : FILE *f = fopen (filename, "r") ;
264 36 : TEST_CHECK (f != NULL) ;
265 36 : OK (LAGraph_MMRead (&A, f, msg)) ;
266 36 : OK (fclose (f)) ;
267 36 : TEST_MSG ("Loading of adjacency matrix failed") ;
268 :
269 : // ensure the matrix is square
270 36 : OK (GrB_Matrix_nrows (&nrows, A)) ;
271 36 : OK (GrB_Matrix_ncols (&ncols, A)) ;
272 36 : TEST_CHECK (nrows == ncols) ;
273 36 : n = nrows ;
274 :
275 : // decide if the graph G is directed or undirected
276 36 : if (outer == 0)
277 : {
278 25 : kind = LAGraph_ADJACENCY_DIRECTED ;
279 : }
280 : else
281 : {
282 11 : kind = LAGraph_ADJACENCY_UNDIRECTED ;
283 : }
284 :
285 : // construct a graph G with adjacency matrix A
286 36 : TEST_CHECK (A != NULL) ;
287 36 : OK (LAGraph_New (&G, &A, kind, msg)) ;
288 36 : TEST_CHECK (A == NULL) ;
289 36 : TEST_CHECK (G != NULL) ;
290 :
291 : // create the cached properties
292 72 : int ok_result = (kind == LAGraph_ADJACENCY_UNDIRECTED) ?
293 36 : LAGRAPH_CACHE_NOT_NEEDED : GrB_SUCCESS ;
294 36 : int result = LAGraph_Cached_AT (G, msg) ;
295 36 : TEST_CHECK (result == ok_result) ;
296 36 : OK (LAGraph_Cached_OutDegree (G, msg)) ;
297 36 : result = LAGraph_Cached_InDegree (G, msg) ;
298 36 : TEST_CHECK (result == ok_result) ;
299 36 : OK (LAGraph_Cached_IsSymmetricStructure (G, msg)) ;
300 : // OK (LAGraph_Graph_Print (G, LAGraph_SHORT, stdout, msg)) ;
301 :
302 : // sort 4 different ways
303 180 : for (int trial = 0 ; trial <= 3 ; trial++)
304 : {
305 144 : bool byout = (trial == 0 || trial == 1) ;
306 144 : bool ascending = (trial == 0 || trial == 2) ;
307 :
308 : // sort the graph by degree
309 144 : TEST_CHECK (P == NULL) ;
310 144 : OK (LAGr_SortByDegree (&P, G, byout, ascending, msg)) ;
311 144 : TEST_CHECK (P != NULL) ;
312 :
313 : // ensure P is a permutation of 0..n-1
314 144 : OK (LAGraph_Calloc ((void **) &W, n, sizeof (bool), msg)) ;
315 1736 : for (int k = 0 ; k < n ; k++)
316 : {
317 1592 : int64_t j = P [k] ;
318 1592 : TEST_CHECK (j >= 0 && j < n) ;
319 1592 : TEST_CHECK (W [j] == false) ;
320 1592 : W [j] = true ;
321 : }
322 :
323 : // check the result by constructing a new graph with adjacency
324 : // matrix B = A (P,P)
325 144 : OK (GrB_Matrix_new (&B, GrB_BOOL, n, n)) ;
326 144 : OK (GrB_extract (B, NULL, NULL, G->A,
327 : (GrB_Index *) P, n, (GrB_Index *) P, n, NULL)) ;
328 144 : OK (LAGraph_New (&H, &B, kind, msg)) ;
329 144 : TEST_CHECK (B == NULL) ;
330 144 : TEST_CHECK (H != NULL) ;
331 :
332 : // get the cached properties of H
333 144 : OK (LAGraph_Cached_OutDegree (H, msg)) ;
334 144 : result = LAGraph_Cached_InDegree (H, msg) ;
335 144 : TEST_CHECK (result == ok_result) ;
336 144 : OK (LAGraph_Cached_IsSymmetricStructure (H, msg)) ;
337 144 : TEST_CHECK (G->is_symmetric_structure ==
338 : H->is_symmetric_structure) ;
339 :
340 72 : d = (byout || G->is_symmetric_structure == LAGraph_TRUE) ?
341 216 : H->out_degree : H->in_degree ;
342 :
343 : // ensure d is sorted in ascending or descending order
344 144 : int64_t last_deg = (ascending) ? (-1) : (n+1) ;
345 1736 : for (int k = 0 ; k < n ; k++)
346 : {
347 1592 : int64_t deg = 0 ;
348 1592 : GrB_Info info = GrB_Vector_extractElement (°, d, k) ;
349 1592 : TEST_CHECK (info == GrB_NO_VALUE || info == GrB_SUCCESS) ;
350 1592 : if (info == GrB_NO_VALUE) deg = 0 ;
351 1592 : if (ascending)
352 : {
353 796 : TEST_CHECK (last_deg <= deg) ;
354 : }
355 : else
356 : {
357 796 : TEST_CHECK (last_deg >= deg) ;
358 : }
359 1592 : last_deg = deg ;
360 : }
361 :
362 : // free workspace and the graph H
363 144 : OK (LAGraph_Free ((void **) &W, NULL)) ;
364 144 : OK (LAGraph_Free ((void **) &P, NULL)) ;
365 144 : OK (LAGraph_Delete (&H, msg)) ;
366 : }
367 :
368 : // check if the adjacency matrix is symmetric
369 36 : if (outer == 0)
370 : {
371 : // if G->A is symmetric, then continue the outer iteration to
372 : // create an undirected graph. Otherwise just do the directed
373 : // graph
374 25 : OK (LAGraph_Matrix_IsEqual (&is_symmetric, G->A, G->AT, msg)) ;
375 25 : if (!is_symmetric)
376 : {
377 14 : OK (LAGraph_Delete (&G, msg)) ;
378 14 : break ;
379 : }
380 : }
381 :
382 22 : OK (LAGraph_Delete (&G, msg)) ;
383 : }
384 : }
385 :
386 1 : OK (LG_brutal_teardown (msg)) ;
387 1 : }
388 : #endif
389 :
390 : //-----------------------------------------------------------------------------
391 : // test_SortByDegree_failures: test error handling of LAGr_SortByDegree
392 : //-----------------------------------------------------------------------------
393 :
394 1 : void test_SortByDegree_failures (void)
395 : {
396 1 : setup ( ) ;
397 :
398 1 : int result = LAGr_SortByDegree (NULL, NULL, true, true, msg) ;
399 1 : printf ("\nresult %d: msg: %s\n", result, msg) ;
400 1 : TEST_CHECK (result == GrB_NULL_POINTER) ;
401 :
402 1 : result = LAGr_SortByDegree (&P, NULL, true, true, msg) ;
403 1 : TEST_CHECK (result == GrB_NULL_POINTER) ;
404 1 : printf ("msg: %s\n", msg) ;
405 :
406 : // create the karate graph
407 1 : FILE *f = fopen (LG_DATA_DIR "karate.mtx", "r") ;
408 1 : TEST_CHECK (f != NULL) ;
409 1 : OK (LAGraph_MMRead (&A, f, msg)) ;
410 1 : OK (fclose (f)) ;
411 1 : TEST_MSG ("Loading of adjacency matrix failed") ;
412 1 : OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_UNDIRECTED, msg)) ;
413 :
414 : // cached degree property must first be computed
415 1 : result = LAGr_SortByDegree (&P, G, true, true, msg) ;
416 1 : printf ("\nresult %d: msg: %s\n", result, msg) ;
417 1 : TEST_CHECK (result == LAGRAPH_NOT_CACHED) ;
418 :
419 1 : teardown ( ) ;
420 1 : }
421 :
422 : //-----------------------------------------------------------------------------
423 : // TEST_LIST: the list of tasks for this entire test
424 : //-----------------------------------------------------------------------------
425 :
426 : TEST_LIST =
427 : {
428 : { "SortByDegree", test_SortByDegree },
429 : { "SortByDegree_failures", test_SortByDegree_failures },
430 : #if LAGRAPH_SUITESPARSE
431 : { "SortByDegree_brutal", test_SortByDegree_brutal },
432 : #endif
433 : { NULL, NULL }
434 : } ;
|
