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