Line data Source code
1 : //----------------------------------------------------------------------------
2 : // LAGraph/src/test/test_SwapEdges.c: test cases for LAGraph_HelloWorld
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 : //-----------------------------------------------------------------------------
15 :
16 :
17 :
18 : #include <stdio.h>
19 : #include <acutest.h>
20 : #include <LAGraphX.h>
21 : #include <LG_internal.h>
22 : #include <LAGraph_test.h>
23 : #include <LG_Xtest.h>
24 : #include <LG_test.h>
25 :
26 : char msg [LAGRAPH_MSG_LEN] ;
27 : LAGraph_Graph G = NULL, G_new = NULL;
28 : GrB_Matrix A = NULL, C = NULL, C_new = NULL;
29 : #define LEN 512
30 : char filename [LEN+1] ;
31 :
32 : const char* tests [ ] =
33 : {
34 : "random_unweighted_general1.mtx",
35 : "random_unweighted_general2.mtx",
36 : "random_weighted_general1.mtx",
37 : "random_weighted_general2.mtx",
38 : "bcsstk13.mtx",
39 : "test_FW_2500.mtx",
40 : ""
41 : } ;
42 : const char* testsb [ ] =
43 : {
44 : "random_unweighted_general1.mtx",
45 : "random_unweighted_general2.mtx",
46 : "random_weighted_general1.mtx",
47 : "random_weighted_general2.mtx",
48 : "bucky.mtx",
49 : ""
50 : } ;
51 1 : void test_SwapEdges (void)
52 : {
53 : #if LG_SUITESPARSE_GRAPHBLAS_V10
54 : //--------------------------------------------------------------------------
55 : // start LAGraph
56 : //--------------------------------------------------------------------------
57 1 : OK (LAGraph_Init (msg)) ;
58 :
59 1 : for (int k = 0 ; ; k++)
60 6 : {
61 : //The following code taken from MIS tester
62 : // load the matrix as A
63 7 : const char *aname = tests [k];
64 7 : if (strlen (aname) == 0) break;
65 6 : TEST_CASE (aname) ;
66 6 : snprintf (filename, LEN, LG_DATA_DIR "%s", aname) ;
67 6 : FILE *f = fopen (filename, "r") ;
68 6 : TEST_CHECK (f != NULL) ;
69 6 : OK (LAGraph_MMRead (&A, f, msg)) ;
70 6 : OK (fclose (f)) ;
71 6 : TEST_MSG ("Loading of valued matrix failed") ;
72 6 : printf ("\nMatrix: %s\n", aname) ;
73 :
74 : // C = structure of A
75 6 : OK (LAGraph_Matrix_Structure (&C, A, msg)) ;
76 6 : OK (GrB_free (&A)) ;
77 :
78 : // construct a directed graph G with adjacency matrix C
79 6 : OK (LAGraph_New (&G, &C, LAGraph_ADJACENCY_DIRECTED, msg)) ;
80 6 : TEST_CHECK (C == NULL) ;
81 :
82 : // check if the pattern is symmetric
83 6 : OK (LAGraph_Cached_IsSymmetricStructure (G, msg)) ;
84 :
85 6 : if (G->is_symmetric_structure == LAGraph_FALSE)
86 : {
87 : // make the adjacency matrix symmetric
88 1 : OK (LAGraph_Cached_AT (G, msg)) ;
89 1 : OK (GrB_eWiseAdd (G->A, NULL, NULL, GrB_LOR, G->A, G->AT, NULL)) ;
90 1 : G->is_symmetric_structure = LAGraph_TRUE ;
91 : }
92 6 : G->kind = LAGraph_ADJACENCY_UNDIRECTED ;
93 :
94 : // check for self-edges
95 6 : OK (LAGraph_Cached_NSelfEdges (G, msg)) ;
96 6 : if (G->nself_edges != 0)
97 : {
98 : // remove self-edges
99 2 : printf ("graph has %g self edges\n", (double) G->nself_edges) ;
100 2 : OK (LAGraph_DeleteSelfEdges (G, msg)) ;
101 2 : printf ("now has %g self edges\n", (double) G->nself_edges) ;
102 2 : TEST_CHECK (G->nself_edges == 0) ;
103 : }
104 :
105 : // compute the row degree
106 6 : GrB_Index n = 0;
107 6 : OK (LAGraph_Cached_OutDegree (G, msg)) ;
108 6 : OK (GrB_Matrix_nrows(&n, G->A));
109 18 : for (int jit = 0 ; jit <= 1 ; jit++)
110 : {
111 12 : OK (GxB_Global_Option_set (GxB_JIT_C_CONTROL,
112 : jit ? GxB_JIT_ON : GxB_JIT_OFF)) ;
113 12 : double pQ = 0.0;
114 : //------------------------------------------------------------------
115 : // test the algorithm
116 : //------------------------------------------------------------------
117 : // GrB_set (GrB_GLOBAL, (int32_t) (true), GxB_BURBLE) ;
118 12 : OK(LAGraph_SwapEdges( &G_new, &pQ, G, 100.0, msg));
119 : // GrB_set (GrB_GLOBAL, (int32_t) (false), GxB_BURBLE) ;
120 12 : printf ("Test ends. Swaps per Edge: %g \n", pQ) ;
121 12 : printf ("%s\n", msg) ;
122 :
123 : //------------------------------------------------------------------
124 : // check results
125 : //------------------------------------------------------------------
126 : // Check sufficient swaps were performed.
127 12 : TEST_CHECK (pQ >= 100.0) ;
128 : //Make sure we got a symetric back out:
129 12 : OK (LAGraph_CheckGraph (G_new, msg)) ;
130 :
131 12 : OK (LAGraph_Cached_NSelfEdges (G_new, msg)) ;
132 12 : TEST_CHECK (G_new->nself_edges == 0);
133 :
134 : //Make sure no self edges created.
135 12 : OK (LAGraph_Cached_NSelfEdges (G_new, msg)) ;
136 12 : TEST_CHECK (G_new->nself_edges == 0);
137 :
138 : // Check nvals stay the same.
139 : GrB_Index edge_count, new_edge_count;
140 12 : OK (GrB_Matrix_nvals(&edge_count, G->A)) ;
141 12 : OK (GrB_Matrix_nvals(&new_edge_count, G_new->A)) ;
142 12 : TEST_CHECK(edge_count == new_edge_count);
143 : //next: check degrees stay the same.
144 12 : OK (LAGraph_Cached_OutDegree (G_new, msg)) ;
145 :
146 12 : bool ok = false;
147 12 : OK (LAGraph_Vector_IsEqual (
148 : &ok, G->out_degree, G_new->out_degree, msg)) ;
149 12 : TEST_CHECK (ok) ;
150 12 : OK (LAGraph_Delete (&G_new, msg)) ;
151 : }
152 6 : OK (LAGraph_Delete (&G, msg)) ;
153 : }
154 :
155 : //--------------------------------------------------------------------------
156 : // free everything and finalize LAGraph
157 : //--------------------------------------------------------------------------
158 1 : LAGraph_Finalize (msg) ;
159 : #endif
160 1 : }
161 :
162 1 : void test_SwapFull(void)
163 : {
164 : #if LG_SUITESPARSE_GRAPHBLAS_V10
165 : //--------------------------------------------------------------------------
166 : // start LAGraph
167 : //--------------------------------------------------------------------------
168 1 : OK (LAGraph_Init (msg)) ;
169 : //The following code taken from MIS tester
170 : // load the matrix as A
171 1 : const char *aname = "full.mtx";
172 1 : TEST_CASE (aname) ;
173 1 : snprintf (filename, LEN, LG_DATA_DIR "%s", aname) ;
174 1 : FILE *f = fopen (filename, "r") ;
175 1 : TEST_CHECK (f != NULL) ;
176 1 : OK (LAGraph_MMRead (&A, f, msg)) ;
177 1 : OK (fclose (f)) ;
178 1 : TEST_MSG ("Loading of valued matrix failed") ;
179 1 : printf ("\nMatrix: %s\n", aname) ;
180 :
181 : // C = structure of A
182 1 : OK (LAGraph_Matrix_Structure (&C, A, msg)) ;
183 1 : OK (GrB_free (&A)) ;
184 :
185 : // construct a directed graph G with adjacency matrix C
186 1 : OK (LAGraph_New (&G, &C, LAGraph_ADJACENCY_DIRECTED, msg)) ;
187 1 : TEST_CHECK (C == NULL) ;
188 :
189 : // check if the pattern is symmetric
190 1 : OK (LAGraph_Cached_IsSymmetricStructure (G, msg)) ;
191 1 : G->kind = LAGraph_ADJACENCY_UNDIRECTED ;
192 :
193 : // check for self-edges
194 1 : OK (LAGraph_Cached_NSelfEdges (G, msg)) ;
195 1 : if (G->nself_edges != 0)
196 : {
197 : // remove self-edges
198 1 : printf ("graph has %g self edges\n", (double) G->nself_edges) ;
199 1 : OK (LAGraph_DeleteSelfEdges (G, msg)) ;
200 1 : printf ("now has %g self edges\n", (double) G->nself_edges) ;
201 1 : TEST_CHECK (G->nself_edges == 0) ;
202 : }
203 :
204 : // compute the row degree
205 1 : GrB_Index n = 0;
206 1 : OK (LAGraph_Cached_OutDegree (G, msg)) ;
207 1 : OK (GrB_Matrix_nrows(&n, G->A));
208 : //------------------------------------------------------------------
209 : // test the algorithm
210 : //------------------------------------------------------------------
211 1 : double pQ = 0;
212 1 : TEST_CHECK(
213 : LAGraph_SwapEdges( &G_new, &pQ, G, 100.0, msg)
214 : == LAGRAPH_INSUFFICIENT_SWAPS) ;
215 1 : TEST_CHECK(pQ == 0.0);
216 1 : printf ("Test ends. \n") ;
217 1 : printf ("%s\n", msg) ;
218 : //------------------------------------------------------------------
219 : // check results (No swaps should have occured)
220 : //------------------------------------------------------------------
221 :
222 1 : bool ok = false;
223 1 : OK (LAGraph_Matrix_IsEqual (&ok, G_new->A, G->A, msg)) ;
224 1 : TEST_CHECK (ok) ;
225 1 : OK (LAGraph_Delete (&G_new, msg)) ;
226 1 : OK (LAGraph_Delete (&G, msg)) ;
227 :
228 : //--------------------------------------------------------------------------
229 : // free everything and finalize LAGraph
230 : //--------------------------------------------------------------------------
231 1 : LAGraph_Finalize (msg) ;
232 : #endif
233 1 : }
234 1 : void test_SwapEdges_brutal (void)
235 : {
236 : #if LG_SUITESPARSE_GRAPHBLAS_V10
237 : //--------------------------------------------------------------------------
238 : // start LAGraph
239 : //--------------------------------------------------------------------------
240 1 : OK (LG_brutal_setup (msg)) ;
241 :
242 1 : for (int k = 0 ; ; k++)
243 5 : {
244 : //The following code taken from MIS tester
245 : // load the matrix as A
246 6 : const char *aname = testsb [k];
247 6 : if (strlen (aname) == 0) break;
248 5 : TEST_CASE (aname) ;
249 5 : snprintf (filename, LEN, LG_DATA_DIR "%s", aname) ;
250 5 : FILE *f = fopen (filename, "r") ;
251 5 : TEST_CHECK (f != NULL) ;
252 5 : OK (LAGraph_MMRead (&A, f, msg)) ;
253 5 : OK (fclose (f)) ;
254 5 : TEST_MSG ("Loading of valued matrix failed") ;
255 5 : printf ("\nMatrix: %s\n", aname) ;
256 :
257 : // C = structure of A
258 5 : OK (LAGraph_Matrix_Structure (&C, A, msg)) ;
259 5 : OK (GrB_free (&A)) ;
260 :
261 : // construct a directed graph G with adjacency matrix C
262 5 : OK (LAGraph_New (&G, &C, LAGraph_ADJACENCY_DIRECTED, msg)) ;
263 5 : TEST_CHECK (C == NULL) ;
264 :
265 5 : OK (LAGraph_Cached_IsSymmetricStructure (G, msg)) ;
266 5 : OK (LAGraph_Cached_NSelfEdges (G, msg)) ;
267 :
268 : // all matricies I test on here are undirected with no self edges.
269 : // If this changes, change to #if 1.
270 : #if 0
271 : // check if the pattern is symmetric
272 : if (G->is_symmetric_structure == LAGraph_FALSE)
273 : {
274 : // make the adjacency matrix symmetric
275 : OK (LAGraph_Cached_AT (G, msg)) ;
276 : OK (GrB_eWiseAdd (G->A, NULL, NULL, GrB_LOR, G->A, G->AT, NULL)) ;
277 : G->is_symmetric_structure = LAGraph_TRUE ;
278 : }
279 : G->kind = LAGraph_ADJACENCY_UNDIRECTED ;
280 :
281 : // check for self-edges
282 : if (G->nself_edges != 0)
283 : {
284 : // remove self-edges
285 : printf ("graph has %g self edges\n", (double) G->nself_edges) ;
286 : OK (LAGraph_DeleteSelfEdges (G, msg)) ;
287 : printf ("now has %g self edges\n", (double) G->nself_edges) ;
288 : TEST_CHECK (G->nself_edges == 0) ;
289 : }
290 : #else
291 5 : TEST_CHECK (G->is_symmetric_structure) ;
292 5 : TEST_CHECK (G->nself_edges == 0) ;
293 5 : G->kind = LAGraph_ADJACENCY_UNDIRECTED ;
294 : #endif
295 :
296 : // compute the row degree
297 5 : OK (LAGraph_Cached_OutDegree (G, msg)) ;
298 5 : LG_BRUTAL_BURBLE (LAGraph_CheckGraph (G, msg)) ;
299 : //------------------------------------------------------------------
300 : // test the algorithm
301 : //------------------------------------------------------------------
302 5 : double pQ = 0.0;
303 5232 : LG_BRUTAL_BURBLE (LAGraph_SwapEdges( &G_new, &pQ, G, 1.0, msg)) ;
304 5 : printf ("Test ends. Swaps per Edge: %g \n", pQ) ;
305 5 : printf ("%s\n", msg) ;
306 :
307 : //------------------------------------------------------------------
308 : // check results
309 : //------------------------------------------------------------------
310 : // Check sufficient swaps were performed.
311 5 : TEST_CHECK (pQ >= 1.0) ;
312 : //Make sure we got a symetric back out:
313 5 : LG_BRUTAL_BURBLE (LAGraph_CheckGraph (G_new, msg)) ;
314 :
315 5 : OK (LAGraph_Cached_NSelfEdges (G_new, msg)) ;
316 5 : TEST_CHECK (G_new->nself_edges == 0);
317 :
318 : // Check nvals stay the same.
319 : GrB_Index edge_count, new_edge_count;
320 5 : OK (GrB_Matrix_nvals(&edge_count, G->A)) ;
321 5 : OK (GrB_Matrix_nvals(&new_edge_count, G_new->A)) ;
322 5 : TEST_CHECK(edge_count == new_edge_count);
323 : //next: check degrees stay the same.
324 5 : OK (LAGraph_Cached_OutDegree (G_new, msg)) ;
325 :
326 5 : bool ok = false;
327 5 : OK (LAGraph_Vector_IsEqual (
328 : &ok, G->out_degree, G_new->out_degree, msg)) ;
329 5 : TEST_CHECK (ok) ;
330 5 : OK (LAGraph_Delete (&G_new, msg)) ;
331 5 : OK (LAGraph_Delete (&G, msg)) ;
332 : }
333 : //--------------------------------------------------------------------------
334 : // free everything and finalize LAGraph
335 : //--------------------------------------------------------------------------
336 1 : OK (LG_brutal_teardown (msg)) ;
337 : #endif
338 1 : }
339 : //----------------------------------------------------------------------------
340 : // the make program is created by acutest, and it runs a list of tests:
341 : //----------------------------------------------------------------------------
342 :
343 : TEST_LIST =
344 : {
345 : {"SwapEdges", test_SwapEdges},
346 : {"SwapFull", test_SwapFull},
347 : #if LG_BRUTAL_TESTS
348 : {"SwapFull", test_SwapEdges_brutal},
349 : #endif
350 : {NULL, NULL}
351 : } ;
|
