Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LAGraph/experimental/test/test_MaximalIndependentSet
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 : #include <LAGraphX.h>
21 : #include <LAGraph_test.h>
22 : #include <LG_Xtest.h>
23 :
24 : //------------------------------------------------------------------------------
25 : // test cases
26 : //------------------------------------------------------------------------------
27 :
28 : const char *files [ ] =
29 : {
30 : "A.mtx",
31 : "jagmesh7.mtx",
32 : "bcsstk13.mtx",
33 : "karate.mtx",
34 : "ldbc-cdlp-undirected-example.mtx",
35 : "ldbc-cdlp-directed-example.mtx",
36 : "ldbc-undirected-example-bool.mtx",
37 : "ldbc-undirected-example-unweighted.mtx",
38 : "ldbc-undirected-example.mtx",
39 : "ldbc-wcc-example.mtx",
40 : "LFAT5.mtx",
41 : "LFAT5_two.mtx",
42 : "cryg2500.mtx",
43 : "msf2.mtx",
44 : "olm1000.mtx",
45 : "west0067.mtx",
46 : ""
47 : } ;
48 :
49 : #define LEN 512
50 : char filename [LEN+1] ;
51 :
52 : char msg [LAGRAPH_MSG_LEN] ;
53 : GrB_Vector mis = NULL, ignore = NULL ;
54 : GrB_Matrix A = NULL, C = NULL, empty_row = NULL, empty_col = NULL ;
55 : LAGraph_Graph G = NULL ;
56 :
57 : //------------------------------------------------------------------------------
58 : // setup: start a test
59 : //------------------------------------------------------------------------------
60 :
61 1 : void setup (void)
62 : {
63 1 : OK (LAGraph_Init (msg)) ;
64 : // OK (LG_SET_BURBLE (true)) ;
65 1 : }
66 :
67 : //------------------------------------------------------------------------------
68 : // teardown: finalize a test
69 : //------------------------------------------------------------------------------
70 :
71 1 : void teardown (void)
72 : {
73 1 : OK (LAGraph_Finalize (msg)) ;
74 1 : }
75 :
76 : //------------------------------------------------------------------------------
77 : // test_MaximalIndependentSet: test MIS
78 : //------------------------------------------------------------------------------
79 :
80 1 : void test_MIS (void)
81 : {
82 : GrB_Info info ;
83 1 : setup ( ) ;
84 :
85 1 : for (int k = 0 ; ; k++)
86 16 : {
87 :
88 : // load the matrix as A
89 17 : const char *aname = files [k] ;
90 17 : if (strlen (aname) == 0) break;
91 16 : TEST_CASE (aname) ;
92 16 : snprintf (filename, LEN, LG_DATA_DIR "%s", aname) ;
93 16 : FILE *f = fopen (filename, "r") ;
94 16 : TEST_CHECK (f != NULL) ;
95 16 : OK (LAGraph_MMRead (&A, f, msg)) ;
96 16 : OK (fclose (f)) ;
97 16 : TEST_MSG ("Loading of valued matrix failed") ;
98 16 : printf ("\nMatrix: %s\n", aname) ;
99 :
100 : // C = structure of A
101 16 : OK (LAGraph_Matrix_Structure (&C, A, msg)) ;
102 16 : OK (GrB_free (&A)) ;
103 :
104 : // construct a directed graph G with adjacency matrix C
105 16 : OK (LAGraph_New (&G, &C, LAGraph_ADJACENCY_DIRECTED, msg)) ;
106 16 : TEST_CHECK (C == NULL) ;
107 :
108 : // error handling test
109 16 : int result = LAGraph_MaximalIndependentSet (&mis, G, 0, NULL, msg) ;
110 16 : TEST_CHECK (result == -105) ;
111 16 : TEST_CHECK (mis == NULL) ;
112 :
113 : // check if the pattern is symmetric
114 16 : OK (LAGraph_Cached_IsSymmetricStructure (G, msg)) ;
115 :
116 16 : if (G->is_symmetric_structure == LAGraph_FALSE)
117 : {
118 : // make the adjacency matrix symmetric
119 5 : OK (LAGraph_Cached_AT (G, msg)) ;
120 5 : OK (GrB_eWiseAdd (G->A, NULL, NULL, GrB_LOR, G->A, G->AT, NULL)) ;
121 5 : G->is_symmetric_structure = LAGraph_TRUE ;
122 : }
123 16 : G->kind = LAGraph_ADJACENCY_UNDIRECTED ;
124 :
125 : // check for self-edges
126 16 : OK (LAGraph_Cached_NSelfEdges (G, msg)) ;
127 16 : if (G->nself_edges != 0)
128 : {
129 : // remove self-edges
130 7 : printf ("graph has %g self edges\n", (double) G->nself_edges) ;
131 7 : OK (LAGraph_DeleteSelfEdges (G, msg)) ;
132 7 : printf ("now has %g self edges\n", (double) G->nself_edges) ;
133 7 : TEST_CHECK (G->nself_edges == 0) ;
134 : }
135 :
136 : // compute the row degree
137 16 : OK (LAGraph_Cached_OutDegree (G, msg)) ;
138 :
139 : GrB_Index n ;
140 16 : GrB_Matrix_nrows (&n, G->A) ;
141 :
142 : // create ignore
143 16 : OK (GrB_Vector_new (&ignore, GrB_BOOL, n)) ;
144 880 : for (int i = 0 ; i < n ; i += 8)
145 : {
146 864 : OK (GrB_Vector_setElement (ignore, (bool) true, i)) ;
147 : }
148 :
149 96 : for (int64_t seed = 0 ; seed <= 4*n ; seed += n)
150 : {
151 : // compute the MIS with no ignored nodes
152 80 : OK (LAGraph_MaximalIndependentSet (&mis, G, seed, NULL, msg)) ;
153 : // check the result
154 80 : OK (LG_check_mis (G->A, mis, NULL, msg)) ;
155 80 : OK (GrB_free (&mis)) ;
156 :
157 : // compute the MIS with ignored nodes
158 80 : OK (LAGraph_MaximalIndependentSet (&mis, G, seed, ignore, msg)) ;
159 : // check the result
160 80 : OK (LG_check_mis (G->A, mis, ignore, msg)) ;
161 :
162 80 : OK (GrB_free (&mis)) ;
163 : }
164 :
165 : // create some singletons
166 16 : GrB_Index nsingletons = 0 ;
167 : GrB_Index I [1] ;
168 16 : OK (GrB_Matrix_new (&empty_col, GrB_BOOL, n, 1)) ;
169 16 : OK (GrB_Matrix_new (&empty_row, GrB_BOOL, 1, n)) ;
170 705 : for (int64_t i = 0 ; i < n ; i += 10)
171 : {
172 : // make node i a singleton
173 689 : I [0] = i ;
174 689 : OK (GrB_assign (G->A, NULL, NULL, empty_col, GrB_ALL, n, I, 1,
175 : NULL)) ;
176 689 : OK (GrB_assign (G->A, NULL, NULL, empty_row, I, 1, GrB_ALL, n,
177 : NULL)) ;
178 689 : nsingletons++ ;
179 : }
180 16 : printf ("creating at least %g singletons\n", (double) nsingletons) ;
181 :
182 16 : OK (LAGraph_DeleteCached (G, msg)) ;
183 16 : G->kind = LAGraph_ADJACENCY_UNDIRECTED ;
184 16 : G->is_symmetric_structure = LAGraph_TRUE ;
185 16 : G->nself_edges = 0 ;
186 :
187 : // recompute the out degree
188 16 : OK (LAGraph_Cached_OutDegree (G, msg)) ;
189 :
190 : GrB_Index nonsingletons, nsingletons_actual ;
191 16 : OK (GrB_Vector_nvals (&nonsingletons, G->out_degree)) ;
192 16 : nsingletons_actual = n - nonsingletons ;
193 16 : printf ("actual # of singletons: %g\n", (double) nsingletons_actual) ;
194 16 : TEST_CHECK (nsingletons <= nsingletons_actual) ;
195 :
196 96 : for (int64_t seed = 0 ; seed <= 4*n ; seed += n)
197 : {
198 : // compute the MIS with no ignored nodes
199 80 : OK (LAGraph_MaximalIndependentSet (&mis, G, seed, NULL, msg)) ;
200 : // check the result
201 80 : OK (LG_check_mis (G->A, mis, NULL, msg)) ;
202 80 : OK (GrB_free (&mis)) ;
203 :
204 : // compute the MIS with ignored nodes
205 80 : OK (LAGraph_MaximalIndependentSet (&mis, G, seed, ignore, msg)) ;
206 : // check the result
207 80 : OK (LG_check_mis (G->A, mis, ignore, msg)) ;
208 :
209 80 : OK (GrB_free (&mis)) ;
210 : }
211 :
212 : // convert to directed with symmetric structure and recompute the MIS
213 16 : G->kind = LAGraph_ADJACENCY_DIRECTED ;
214 16 : OK (LAGraph_MaximalIndependentSet (&mis, G, 0, NULL, msg)) ;
215 : // check the result
216 16 : OK (LG_check_mis (G->A, mis, NULL, msg)) ;
217 16 : OK (GrB_free (&mis)) ;
218 :
219 : // hack the random number generator to induce an error condition
220 : #if defined ( COVERAGE )
221 16 : printf ("Hack the random number generator to induce a stall:\n") ;
222 16 : random_hack = true ;
223 16 : result = LAGraph_MaximalIndependentSet (&mis, G, 0, NULL, msg) ;
224 16 : random_hack = false ;
225 16 : printf ("hack msg: %d %s\n", result, msg) ;
226 16 : TEST_CHECK (result == LAGRAPH_CONVERGENCE_FAILURE || result == 0) ;
227 16 : if (result == 0)
228 : {
229 3 : OK (LG_check_mis (G->A, mis, NULL, msg)) ;
230 : }
231 : #endif
232 :
233 16 : OK (GrB_free (&mis)) ;
234 16 : OK (GrB_free (&ignore)) ;
235 16 : OK (GrB_free (&empty_col)) ;
236 16 : OK (GrB_free (&empty_row)) ;
237 16 : OK (LAGraph_Delete (&G, msg)) ;
238 : }
239 1 : teardown ( ) ;
240 1 : }
241 :
242 : //-----------------------------------------------------------------------------
243 : // TEST_LIST: the list of tasks for this entire test
244 : //-----------------------------------------------------------------------------
245 :
246 : TEST_LIST =
247 : {
248 : { "MIS", test_MIS },
249 : { NULL, NULL }
250 : } ;
|
