Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LAGraph/experimental/test/test_scc.c: tests for Strongly Connected Components
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 : // todo: write a simple scc method, as LG_check_scc, and compare its results
19 : // with LAGraph_scc
20 :
21 : #include <stdio.h>
22 : #include <acutest.h>
23 :
24 : #include <LAGraphX.h>
25 : #include <LAGraph_test.h>
26 :
27 : char msg [LAGRAPH_MSG_LEN] ;
28 : LAGraph_Graph G = NULL ;
29 : GrB_Matrix A = NULL ;
30 : #define LEN 512
31 : char filename [LEN+1] ;
32 :
33 : typedef struct
34 : {
35 : const char *name ;
36 : int cc_count;
37 : uint64_t hash;
38 : }
39 : matrix_info ;
40 :
41 : int scc_cover [7] = { 0, 0, 2, 0, 4, 2, 0 } ;
42 :
43 : const matrix_info files [ ] =
44 : {
45 : { "A2.mtx", 1, 0x2de8d717be626313},
46 : { "A.mtx", 1, 0x2de8d717be626313},
47 : { "bcsstk13.mtx", 1, 0x41d903f08b46b543},
48 : { "cover.mtx", 3, 0x30ae8cb78a807691},
49 : { "cover_structure.mtx", 3, 0x30ae8cb78a807691},
50 : { "cryg2500.mtx", 1, 0xd1cb8e3cc6be967},
51 : { "full.mtx", 1, 0x99971e4f016b4644},
52 : { "full_noheader.mtx", 1, 0x99971e4f016b4644},
53 : { "full_symmetric.mtx", 1, 0x278859fec1de1f7f},
54 : { "jagmesh7.mtx", 1, 0x66b315eea17941c8},
55 : { "karate.mtx", 1, 0x8bad7c50644c4aa9},
56 : { "ldbc-cdlp-directed-example.mtx", 2, 0x3a61ac294b7bb114},
57 : { "ldbc-cdlp-undirected-example.mtx", 1, 0x4072e255fd8e310a},
58 : { "ldbc-directed-example-bool.mtx", 7, 0xc66f5ecf1b7f6876},
59 : { "ldbc-directed-example.mtx", 7, 0xc66f5ecf1b7f6876},
60 : { "ldbc-directed-example-unweighted.mtx", 7, 0xc66f5ecf1b7f6876},
61 : { "ldbc-undirected-example-bool.mtx", 1, 0xf53db7dbbeff3283},
62 : { "ldbc-undirected-example.mtx", 1, 0xf53db7dbbeff3283},
63 : { "ldbc-undirected-example-unweighted.mtx", 1, 0xf53db7dbbeff3283},
64 : { "ldbc-wcc-example.mtx", 1, 0x36a78022528a2101},
65 : { "LFAT5.mtx", 3, 0x79d4d8de0a22a863},
66 : { "LFAT5_two.mtx", 6, 0xac369d0362d73d6},
67 : { "matrix_bool.mtx", 3, 0x30ae8cb78a807691},
68 : { "matrix_fp32.mtx", 3, 0x30ae8cb78a807691},
69 : { "matrix_fp32_structure.mtx", 3, 0x30ae8cb78a807691},
70 : { "matrix_fp64.mtx", 3, 0x30ae8cb78a807691},
71 : { "matrix_int16.mtx", 3, 0x30ae8cb78a807691},
72 : { "matrix_int32.mtx", 3, 0x30ae8cb78a807691},
73 : { "matrix_int64.mtx", 3, 0x30ae8cb78a807691},
74 : { "matrix_int8.mtx", 3, 0x30ae8cb78a807691},
75 : { "matrix_uint16.mtx", 3, 0x30ae8cb78a807691},
76 : { "matrix_uint32.mtx", 3, 0x30ae8cb78a807691},
77 : { "matrix_uint64.mtx", 3, 0x30ae8cb78a807691},
78 : { "matrix_uint8.mtx", 3, 0x30ae8cb78a807691},
79 : { "msf1.mtx", 4, 0x6445d984131a9555},
80 : { "msf2.mtx", 8, 0x72d532720c54b673},
81 : { "msf3.mtx", 5, 0xf57eb057beb5a5c7},
82 : { "olm1000.mtx", 1, 0x15cf9ea2db88ab18},
83 : { "pushpull.mtx", 1, 0x1816384cd04f7e01},
84 : { "sample2.mtx", 1, 0x4072e255fd8e310a},
85 : { "sample.mtx", 8, 0x72d532720c54b673},
86 : { "structure.mtx", 3, 0x30ae8cb78a807691},
87 : { "test_BF.mtx", 3, 0x30ae8cb78a807691},
88 : { "test_FW_1000.mtx", 1, 0x15cf9ea2db88ab18},
89 : { "test_FW_2003.mtx", 485, 0xf79ad45d3a704eec},
90 : { "test_FW_2500.mtx", 646, 0x4fa83d60352e7e19},
91 : { "tree-example.mtx", 1, 0x8857b82baeba129},
92 : { "west0067_jumbled.mtx", 1, 0xa861dc7526128ac7},
93 : { "west0067.mtx", 1, 0xa861dc7526128ac7},
94 : { "west0067_noheader.mtx", 1, 0xa861dc7526128ac7},
95 : { "zenios.mtx", 1391, 0x15b2b99a80c3480e},
96 : { "", 0, 0},
97 : } ;
98 :
99 : //------------------------------------------------------------------------------
100 : // count_connected_components: count the # of components in a component vector
101 : //------------------------------------------------------------------------------
102 :
103 102 : int count_connected_components (GrB_Vector C)
104 : {
105 102 : GrB_Index n = 0 ;
106 102 : OK (GrB_Vector_size (&n, C)) ;
107 102 : int ncomponents = 0 ;
108 39210 : for (int i = 0 ; i < n ; i++)
109 : {
110 39108 : int64_t comp = -1 ;
111 39108 : int result = GrB_Vector_extractElement (&comp, C, i) ;
112 39108 : if (result == GrB_SUCCESS && comp == i) ncomponents++ ;
113 : }
114 102 : return (ncomponents) ;
115 : }
116 :
117 : //****************************************************************************
118 1 : void test_scc (void)
119 : {
120 : #if LG_SUITESPARSE_GRAPHBLAS_V10
121 1 : LAGraph_Init (msg) ;
122 :
123 1 : for (int k = 0 ; ; k++)
124 51 : {
125 :
126 : // load the matrix as A
127 52 : const char *aname = files [k].name ;
128 52 : if (strlen (aname) == 0) break;
129 51 : printf ("\n================================== %s:\n", aname) ;
130 51 : TEST_CASE (aname) ;
131 51 : snprintf (filename, LEN, LG_DATA_DIR "%s", aname) ;
132 51 : FILE *f = fopen (filename, "r") ;
133 51 : TEST_CHECK (f != NULL) ;
134 51 : OK (LAGraph_MMRead (&A, f, msg)) ;
135 51 : fclose (f) ;
136 :
137 51 : GrB_Vector c = NULL ;
138 :
139 153 : for (int jit = 0 ; jit <= 1 ; jit++)
140 : {
141 102 : OK (GxB_Global_Option_set (GxB_JIT_C_CONTROL,
142 : jit ? GxB_JIT_ON : GxB_JIT_OFF)) ;
143 : // find the strongly connected components with LAGraph_scc
144 : // GrB_set (GrB_GLOBAL, (int32_t) (true), GxB_BURBLE) ;
145 102 : OK (LAGraph_scc (&c, A, msg)) ;
146 : // GrB_set (GrB_GLOBAL, (int32_t) (true), GxB_BURBLE) ;
147 :
148 : GrB_Index n ;
149 102 : OK (GrB_Vector_size (&n, c)) ;
150 102 : LAGraph_PrintLevel pr = (n <= 100) ? LAGraph_COMPLETE : LAGraph_SHORT ;
151 :
152 : // check result c for cover
153 102 : if (strcmp (aname, "cover.mtx") == 0)
154 : {
155 2 : GrB_Vector cgood = NULL ;
156 2 : OK (GrB_Vector_new (&cgood, GrB_UINT64, n)) ;
157 16 : for (int k = 0 ; k < n ; k++)
158 : {
159 14 : OK (GrB_Vector_setElement (cgood, scc_cover [k], k)) ;
160 : }
161 2 : OK (GrB_wait (cgood, GrB_MATERIALIZE)) ;
162 2 : printf ("\nscc (known result):\n") ;
163 2 : OK (LAGraph_Vector_Print (cgood, pr, stdout, msg)) ;
164 2 : bool ok = false ;
165 2 : OK (LAGraph_Vector_IsEqual (&ok, c, cgood, msg)) ;
166 2 : TEST_CHECK (ok) ;
167 2 : OK (GrB_free (&cgood)) ;
168 : }
169 102 : int result_cc_count = count_connected_components(c);
170 102 : TEST_CHECK(result_cc_count == files[k].cc_count);
171 102 : OK (LAGraph_Vector_Print (c, pr, stdout, msg)) ;
172 102 : uint64_t hash = 0;
173 102 : int hash_info = LAGraph_Hash_Vector(&hash, c, msg);
174 102 : OK (hash_info);
175 102 : TEST_CHECK(hash == files[k].hash);
176 102 : OK (GrB_free (&c)) ;
177 : }
178 51 : OK (GrB_free (&A)) ;
179 : }
180 :
181 1 : LAGraph_Finalize (msg) ;
182 : #endif
183 1 : }
184 :
185 : //------------------------------------------------------------------------------
186 : // test_errors
187 : //------------------------------------------------------------------------------
188 :
189 1 : void test_errors (void)
190 : {
191 : #if LG_SUITESPARSE_GRAPHBLAS_V10
192 1 : LAGraph_Init (msg) ;
193 :
194 1 : GrB_Vector c = NULL ;
195 1 : GrB_Matrix A = NULL ;
196 :
197 : // c and A are NULL
198 1 : int result = LAGraph_scc (NULL, A, msg) ;
199 1 : printf ("\nresult: %d\n", result) ;
200 1 : TEST_CHECK (result == GrB_NULL_POINTER) ;
201 :
202 : // A is rectangular
203 1 : OK (GrB_Matrix_new (&A, GrB_BOOL, 3, 4)) ;
204 1 : result = LAGraph_scc (&c, A, msg) ;
205 1 : TEST_CHECK (result == GrB_DIMENSION_MISMATCH) ;
206 :
207 1 : OK (GrB_free (&c)) ;
208 1 : OK (GrB_free (&A)) ;
209 1 : LAGraph_Finalize (msg) ;
210 : #endif
211 1 : }
212 :
213 : //****************************************************************************
214 :
215 : TEST_LIST = {
216 : {"scc", test_scc},
217 : {"scc_errors", test_errors},
218 : {NULL, NULL}
219 : };
|
