Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LAGraph/experimental/test/LAGraph_CFL_reachability.c: test cases for Context-Free
3 : // Language Reachability Matrix-Based Algorithm
4 : //------------------------------------------------------------------------------
5 : //
6 : // LAGraph, (c) 2019-2024 by The LAGraph Contributors, All Rights Reserved.
7 : // SPDX-License-Identifier: BSD-2-Clause
8 :
9 : // Contributed by Ilhom Kombaev, Semyon Grigoriev, St. Petersburg State University.
10 :
11 : //------------------------------------------------------------------------------
12 :
13 : #include <LAGraphX.h>
14 : #include <LAGraph_test.h>
15 : #include <LG_Xtest.h>
16 : #include <LG_test.h>
17 : #include <acutest.h>
18 : #include <stdio.h>
19 :
20 : #define run_algorithm() \
21 : LAGraph_CFL_reachability(outputs, adj_matrices, grammar.terms_count, \
22 : grammar.nonterms_count, grammar.rules, grammar.rules_count, \
23 : msg)
24 :
25 : #define check_error(error) \
26 : { \
27 : retval = run_algorithm(); \
28 : TEST_CHECK(retval == error); \
29 : TEST_MSG("retval = %d (%s)", retval, msg); \
30 : }
31 :
32 : #define check_result(result) \
33 : { \
34 : char *expected = output_to_str(0); \
35 : TEST_CHECK(strcmp(result, expected) == 0); \
36 : TEST_MSG("Wrong result. Actual: %s", expected); \
37 : LAGraph_Free ((void **) &expected, msg); \
38 : }
39 :
40 : typedef struct {
41 : size_t nonterms_count;
42 : size_t terms_count;
43 : size_t rules_count;
44 : LAGraph_rule_WCNF *rules;
45 : } grammar_t;
46 :
47 : GrB_Matrix *adj_matrices = NULL;
48 : int n_adj_matrices = 0 ;
49 : GrB_Matrix *outputs = NULL;
50 : grammar_t grammar = {0, 0, 0, NULL};
51 : char msg[LAGRAPH_MSG_LEN];
52 :
53 10 : void setup() { LAGraph_Init(msg); }
54 :
55 10 : void teardown(void) { LAGraph_Finalize(msg); }
56 :
57 12 : void init_outputs()
58 : {
59 12 : LAGraph_Calloc ((void **) &outputs,
60 : grammar.nonterms_count, sizeof(GrB_Matrix), msg) ;
61 12 : }
62 :
63 8 : char *output_to_str(size_t nonterm) {
64 8 : GrB_Index nnz = 0;
65 8 : OK(GrB_Matrix_nvals(&nnz, outputs[nonterm]));
66 8 : GrB_Index *row = NULL ;
67 8 : GrB_Index *col = NULL ;
68 8 : bool *val = NULL ;
69 8 : LAGraph_Malloc ((void **) &row, nnz, sizeof (GrB_Index), msg) ;
70 8 : LAGraph_Malloc ((void **) &col, nnz, sizeof (GrB_Index), msg) ;
71 8 : LAGraph_Malloc ((void **) &val, nnz, sizeof (GrB_Index), msg) ;
72 :
73 8 : OK(GrB_Matrix_extractTuples(row, col, val, &nnz, outputs[nonterm]));
74 :
75 : // 11 - size of " (%ld, %ld)"
76 8 : char *result_str = NULL ;
77 8 : LAGraph_Malloc ((void **) &result_str, 11*nnz, sizeof (char), msg) ;
78 :
79 8 : result_str[0] = '\0';
80 52 : for (size_t i = 0; i < nnz; i++) {
81 44 : sprintf(result_str + strlen(result_str), i == 0 ?
82 : "(%" PRIu64 ", %" PRIu64 ")" : " (%" PRIu64 ", %" PRIu64 ")",
83 44 : row[i], col[i]);
84 : }
85 :
86 8 : LAGraph_Free ((void **) &row, msg);
87 8 : LAGraph_Free ((void **) &col, msg);
88 8 : LAGraph_Free ((void **) &val, msg);
89 :
90 8 : return result_str;
91 : }
92 :
93 12 : void free_workspace() {
94 :
95 12 : if (adj_matrices != NULL)
96 : {
97 33 : for (size_t i = 0; i < n_adj_matrices ; i++)
98 : {
99 22 : GrB_free(&adj_matrices[i]);
100 : }
101 : }
102 12 : LAGraph_Free ((void **) &adj_matrices, msg);
103 :
104 12 : if (outputs != NULL)
105 : {
106 70 : for (size_t i = 0; i < grammar.nonterms_count; i++)
107 : {
108 59 : GrB_free(&outputs[i]);
109 : }
110 : }
111 12 : LAGraph_Free ((void **) &outputs, msg);
112 :
113 12 : LAGraph_Free ((void **) &grammar.rules, msg);
114 12 : grammar = (grammar_t){0, 0, 0, NULL};
115 12 : }
116 :
117 : //====================
118 : // Grammars
119 : //====================
120 :
121 : // S -> aSb | ab in WCNF
122 : //
123 : // Terms: [0 a] [1 b]
124 : // Nonterms: [0 S] [1 A] [2 B] [3 C]
125 : // S -> AB [0 1 2 0]
126 : // S -> AC [0 1 3 0]
127 : // C -> SB [3 0 2 0]
128 : // A -> a [1 0 -1 0]
129 : // B -> b [2 1 -1 0]
130 9 : void init_grammar_aSb() {
131 9 : LAGraph_rule_WCNF *rules = NULL ;
132 9 : LAGraph_Calloc ((void **) &rules, 5, sizeof(LAGraph_rule_WCNF), msg);
133 :
134 9 : rules[0] = (LAGraph_rule_WCNF){0, 1, 2, 0};
135 9 : rules[1] = (LAGraph_rule_WCNF){0, 1, 3, 0};
136 9 : rules[2] = (LAGraph_rule_WCNF){3, 0, 2, 0};
137 9 : rules[3] = (LAGraph_rule_WCNF){1, 0, -1, 0};
138 9 : rules[4] = (LAGraph_rule_WCNF){2, 1, -1, 0};
139 :
140 9 : grammar = (grammar_t){
141 : .nonterms_count = 4, .terms_count = 2, .rules_count = 5, .rules = rules};
142 9 : }
143 :
144 : // S -> aS | a | eps in WCNF
145 : //
146 : // Terms: [0 a]
147 : // Nonterms: [0 S]
148 : // S -> SS [0 0 0 0]
149 : // S -> a [0 0 -1 0]
150 : // S -> eps [0 -1 -1 0]
151 2 : void init_grammar_aS() {
152 2 : LAGraph_rule_WCNF *rules = NULL ;
153 2 : LAGraph_Calloc ((void **) &rules, 3, sizeof(LAGraph_rule_WCNF), msg);
154 :
155 2 : rules[0] = (LAGraph_rule_WCNF){0, 0, 0, 0};
156 2 : rules[1] = (LAGraph_rule_WCNF){0, 0, -1, 0};
157 2 : rules[2] = (LAGraph_rule_WCNF){0, -1, -1, 0};
158 :
159 2 : grammar = (grammar_t){
160 : .nonterms_count = 1, .terms_count = 1, .rules_count = 3, .rules = rules};
161 2 : }
162 :
163 : // Complex grammar
164 : // aaaabbbb or aaabbb
165 : //
166 : // Terms: [0 a] [1 b]
167 : // Nonterms: [0 S] [n Sn]
168 : // S -> S1 S2 [0 1 2 0]
169 : // S -> S15 S16 [0 15 16 0]
170 : // S1 -> S3 S4 [1 3 4 0]
171 : // S2 -> S5 S6 [2 5 6 0]
172 : // S3 -> S7 S8 [3 7 8 0]
173 : // S4 -> S9 S10 [4 9 10 0]
174 : // S5 -> S11 S12 [5 11 12 0]
175 : // S6 -> S13 S14 [6 13 14 0]
176 : // S16 -> S17 S18 [16 17 18 0]
177 : // S17 -> S19 S20 [17 19 20 0]
178 : // S18 -> S21 S22 [18 21 22 0]
179 : // S22 -> S23 S24 [22 23 24 0]
180 : // S7 -> a [7 0 -1 0]
181 : // S8 -> a [8 0 -1 0]
182 : // S9 -> a [9 0 -1 0]
183 : // S10 -> a [10 0 -1 0]
184 : // S11 -> b [11 1 -1 0]
185 : // S12 -> b [12 1 -1 0]
186 : // S13 -> b [13 1 -1 0]
187 : // S14 -> b [14 1 -1 0]
188 : // S15 -> a [15 0 -1 0]
189 : // S19 -> a [19 0 -1 0]
190 : // S20 -> a [20 0 -1 0]
191 : // S21 -> b [21 1 -1 0]
192 : // S23 -> b [23 1 -1 0]
193 : // S24 -> b [24 1 -1 0]
194 1 : void init_grammar_complex() {
195 1 : LAGraph_rule_WCNF *rules = NULL ;
196 1 : LAGraph_Calloc ((void **) &rules, 26, sizeof(LAGraph_rule_WCNF), msg);
197 :
198 1 : rules[0] = (LAGraph_rule_WCNF){0, 1, 2, 0};
199 1 : rules[1] = (LAGraph_rule_WCNF){0, 15, 16, 0};
200 1 : rules[2] = (LAGraph_rule_WCNF){1, 3, 4, 0};
201 1 : rules[3] = (LAGraph_rule_WCNF){2, 5, 6, 0};
202 1 : rules[4] = (LAGraph_rule_WCNF){3, 7, 8, 0};
203 1 : rules[5] = (LAGraph_rule_WCNF){4, 9, 10, 0};
204 1 : rules[6] = (LAGraph_rule_WCNF){5, 11, 12, 0};
205 1 : rules[7] = (LAGraph_rule_WCNF){6, 13, 14, 0};
206 1 : rules[8] = (LAGraph_rule_WCNF){16, 17, 18, 0};
207 1 : rules[9] = (LAGraph_rule_WCNF){17, 19, 20, 0};
208 1 : rules[10] = (LAGraph_rule_WCNF){18, 21, 22, 0};
209 1 : rules[11] = (LAGraph_rule_WCNF){22, 23, 24, 0};
210 1 : rules[12] = (LAGraph_rule_WCNF){7, 0, -1, 0};
211 1 : rules[13] = (LAGraph_rule_WCNF){8, 0, -1, 0};
212 1 : rules[14] = (LAGraph_rule_WCNF){9, 0, -1, 0};
213 1 : rules[15] = (LAGraph_rule_WCNF){10, 0, -1, 0};
214 1 : rules[16] = (LAGraph_rule_WCNF){11, 1, -1, 0};
215 1 : rules[17] = (LAGraph_rule_WCNF){12, 1, -1, 0};
216 1 : rules[18] = (LAGraph_rule_WCNF){13, 1, -1, 0};
217 1 : rules[19] = (LAGraph_rule_WCNF){14, 1, -1, 0};
218 1 : rules[20] = (LAGraph_rule_WCNF){15, 0, -1, 0};
219 1 : rules[21] = (LAGraph_rule_WCNF){19, 0, -1, 0};
220 1 : rules[22] = (LAGraph_rule_WCNF){20, 0, -1, 0};
221 1 : rules[23] = (LAGraph_rule_WCNF){21, 1, -1, 0};
222 1 : rules[24] = (LAGraph_rule_WCNF){23, 1, -1, 0};
223 1 : rules[25] = (LAGraph_rule_WCNF){24, 1, -1, 0};
224 :
225 1 : grammar = (grammar_t){
226 : .nonterms_count = 25, .terms_count = 2, .rules_count = 26, .rules = rules};
227 1 : }
228 :
229 : //====================
230 : // Graphs
231 : //====================
232 :
233 : // Graph:
234 : //
235 : // 0 -a-> 1
236 : // 1 -a-> 2
237 : // 2 -a-> 0
238 : // 0 -b-> 3
239 : // 3 -b-> 0
240 5 : void init_graph_double_cycle() {
241 5 : LAGraph_Calloc ((void **) &adj_matrices, 2, sizeof (GrB_Matrix), msg) ;
242 5 : n_adj_matrices = 2 ;
243 :
244 : GrB_Matrix adj_matrix_a, adj_matrix_b;
245 5 : OK(GrB_Matrix_new(&adj_matrix_a, GrB_BOOL, 4, 4));
246 5 : OK(GrB_Matrix_new(&adj_matrix_b, GrB_BOOL, 4, 4));
247 :
248 5 : OK(GrB_Matrix_setElement(adj_matrix_a, true, 0, 1));
249 5 : OK(GrB_Matrix_setElement(adj_matrix_a, true, 1, 2));
250 5 : OK(GrB_Matrix_setElement(adj_matrix_a, true, 2, 0));
251 :
252 5 : OK(GrB_Matrix_setElement(adj_matrix_b, true, 0, 3));
253 5 : OK(GrB_Matrix_setElement(adj_matrix_b, true, 3, 0));
254 :
255 5 : adj_matrices[0] = adj_matrix_a;
256 5 : adj_matrices[1] = adj_matrix_b;
257 5 : }
258 :
259 : // Graph:
260 : //
261 : // 0 -a-> 1
262 : // 1 -a-> 2
263 : // 2 -a-> 3
264 : // 3 -a-> 4
265 : // 3 -b-> 5
266 : // 4 -b-> 3
267 : // 5 -b-> 6
268 : // 6 -b-> 7
269 1 : void init_graph_1() {
270 1 : LAGraph_Calloc ((void **) &adj_matrices, 2, sizeof (GrB_Matrix), msg) ;
271 1 : n_adj_matrices = 2 ;
272 :
273 : GrB_Matrix adj_matrix_a, adj_matrix_b;
274 1 : OK(GrB_Matrix_new(&adj_matrix_a, GrB_BOOL, 8, 8));
275 1 : OK(GrB_Matrix_new(&adj_matrix_b, GrB_BOOL, 8, 8));
276 :
277 1 : OK(GrB_Matrix_setElement(adj_matrix_a, true, 0, 1));
278 1 : OK(GrB_Matrix_setElement(adj_matrix_a, true, 1, 2));
279 1 : OK(GrB_Matrix_setElement(adj_matrix_a, true, 2, 3));
280 1 : OK(GrB_Matrix_setElement(adj_matrix_a, true, 3, 4));
281 :
282 1 : OK(GrB_Matrix_setElement(adj_matrix_b, true, 3, 5));
283 1 : OK(GrB_Matrix_setElement(adj_matrix_b, true, 4, 3));
284 1 : OK(GrB_Matrix_setElement(adj_matrix_b, true, 5, 6));
285 1 : OK(GrB_Matrix_setElement(adj_matrix_b, true, 6, 7));
286 :
287 1 : adj_matrices[0] = adj_matrix_a;
288 1 : adj_matrices[1] = adj_matrix_b;
289 1 : }
290 :
291 : // Graph:
292 : //
293 : // 0 -a-> 2
294 : // 1 -a-> 2
295 : // 3 -a-> 5
296 : // 4 -a-> 5
297 : // 2 -a-> 6
298 : // 5 -a-> 6
299 : // 2 -b-> 0
300 : // 2 -b-> 1
301 : // 5 -b-> 3
302 : // 5 -b-> 4
303 : // 6 -b-> 2
304 : // 6 -b-> 5
305 1 : void init_graph_tree() {
306 1 : LAGraph_Calloc ((void **) &adj_matrices, 2, sizeof (GrB_Matrix), msg) ;
307 1 : n_adj_matrices = 2 ;
308 :
309 : GrB_Matrix adj_matrix_a, adj_matrix_b;
310 1 : OK(GrB_Matrix_new(&adj_matrix_a, GrB_BOOL, 7, 7));
311 1 : OK(GrB_Matrix_new(&adj_matrix_b, GrB_BOOL, 7, 7));
312 :
313 1 : OK(GrB_Matrix_setElement(adj_matrix_a, true, 0, 2));
314 1 : OK(GrB_Matrix_setElement(adj_matrix_a, true, 1, 2));
315 1 : OK(GrB_Matrix_setElement(adj_matrix_a, true, 3, 5));
316 1 : OK(GrB_Matrix_setElement(adj_matrix_a, true, 4, 5));
317 1 : OK(GrB_Matrix_setElement(adj_matrix_a, true, 2, 6));
318 1 : OK(GrB_Matrix_setElement(adj_matrix_a, true, 5, 6));
319 :
320 1 : OK(GrB_Matrix_setElement(adj_matrix_b, true, 2, 0));
321 1 : OK(GrB_Matrix_setElement(adj_matrix_b, true, 2, 1));
322 1 : OK(GrB_Matrix_setElement(adj_matrix_b, true, 5, 3));
323 1 : OK(GrB_Matrix_setElement(adj_matrix_b, true, 5, 4));
324 1 : OK(GrB_Matrix_setElement(adj_matrix_b, true, 6, 2));
325 1 : OK(GrB_Matrix_setElement(adj_matrix_b, true, 6, 5));
326 :
327 1 : adj_matrices[0] = adj_matrix_a;
328 1 : adj_matrices[1] = adj_matrix_b;
329 1 : }
330 :
331 : // Graph:
332 : //
333 : // 0 -a-> 1
334 : // 1 -a-> 2
335 : // 2 -a-> 0
336 1 : void init_graph_one_cycle() {
337 1 : LAGraph_Calloc ((void **) &adj_matrices, 1, sizeof (GrB_Matrix), msg) ;
338 1 : n_adj_matrices = 1 ;
339 :
340 : GrB_Matrix adj_matrix_a;
341 1 : GrB_Matrix_new(&adj_matrix_a, GrB_BOOL, 3, 3);
342 :
343 1 : OK(GrB_Matrix_setElement(adj_matrix_a, true, 0, 1));
344 1 : OK(GrB_Matrix_setElement(adj_matrix_a, true, 1, 2));
345 1 : OK(GrB_Matrix_setElement(adj_matrix_a, true, 2, 0));
346 :
347 1 : adj_matrices[0] = adj_matrix_a;
348 1 : }
349 :
350 : // Graph:
351 :
352 : // 0 -a-> 1
353 : // 1 -a-> 2
354 : // 2 -b-> 3
355 : // 3 -b-> 4
356 1 : void init_graph_line() {
357 1 : LAGraph_Calloc ((void **) &adj_matrices, 2, sizeof (GrB_Matrix), msg) ;
358 1 : n_adj_matrices = 2 ;
359 :
360 : GrB_Matrix adj_matrix_a, adj_matrix_b;
361 1 : GrB_Matrix_new(&adj_matrix_a, GrB_BOOL, 5, 5);
362 1 : GrB_Matrix_new(&adj_matrix_b, GrB_BOOL, 5, 5);
363 :
364 1 : OK(GrB_Matrix_setElement(adj_matrix_a, true, 0, 1));
365 1 : OK(GrB_Matrix_setElement(adj_matrix_a, true, 1, 2));
366 :
367 1 : OK(GrB_Matrix_setElement(adj_matrix_b, true, 2, 3));
368 1 : OK(GrB_Matrix_setElement(adj_matrix_b, true, 3, 4));
369 :
370 1 : adj_matrices[0] = adj_matrix_a;
371 1 : adj_matrices[1] = adj_matrix_b;
372 1 : }
373 :
374 : // Graph:
375 :
376 : // 0 -a-> 0
377 : // 0 -b-> 1
378 : // 1 -c-> 2
379 1 : void init_graph_2() {
380 1 : LAGraph_Calloc ((void **) &adj_matrices, 3, sizeof (GrB_Matrix), msg) ;
381 1 : n_adj_matrices = 3 ;
382 :
383 : GrB_Matrix adj_matrix_a, adj_matrix_b, adj_matrix_c;
384 1 : GrB_Matrix_new(&adj_matrix_a, GrB_BOOL, 3, 3);
385 1 : GrB_Matrix_new(&adj_matrix_b, GrB_BOOL, 3, 3);
386 1 : GrB_Matrix_new(&adj_matrix_c, GrB_BOOL, 3, 3);
387 :
388 1 : OK(GrB_Matrix_setElement(adj_matrix_a, true, 0, 0));
389 1 : OK(GrB_Matrix_setElement(adj_matrix_b, true, 0, 1));
390 1 : OK(GrB_Matrix_setElement(adj_matrix_c, true, 1, 2));
391 :
392 1 : adj_matrices[0] = adj_matrix_a;
393 1 : adj_matrices[1] = adj_matrix_b;
394 1 : adj_matrices[2] = adj_matrix_c;
395 1 : }
396 :
397 : // Graph:
398 :
399 : // 0 -a-> 1
400 : // 1 -a-> 0
401 : // 0 -b-> 0
402 1 : void init_graph_3() {
403 1 : LAGraph_Calloc ((void **) &adj_matrices, 2, sizeof (GrB_Matrix), msg) ;
404 1 : n_adj_matrices = 2 ;
405 :
406 : GrB_Matrix adj_matrix_a, adj_matrix_b;
407 1 : GrB_Matrix_new(&adj_matrix_a, GrB_BOOL, 2, 2);
408 1 : GrB_Matrix_new(&adj_matrix_b, GrB_BOOL, 2, 2);
409 :
410 1 : OK(GrB_Matrix_setElement(adj_matrix_a, true, 0, 1));
411 1 : OK(GrB_Matrix_setElement(adj_matrix_a, true, 1, 0));
412 1 : OK(GrB_Matrix_setElement(adj_matrix_b, true, 0, 0));
413 :
414 1 : adj_matrices[0] = adj_matrix_a;
415 1 : adj_matrices[1] = adj_matrix_b;
416 1 : }
417 :
418 : // Graph:
419 :
420 : // 0 -b-> 1
421 : // 1 -b-> 0
422 1 : void init_graph_4() {
423 1 : LAGraph_Calloc ((void **) &adj_matrices, 2, sizeof (GrB_Matrix), msg) ;
424 1 : n_adj_matrices = 2 ;
425 :
426 : GrB_Matrix adj_matrix_a, adj_matrix_b;
427 1 : GrB_Matrix_new(&adj_matrix_a, GrB_BOOL, 2, 2);
428 1 : GrB_Matrix_new(&adj_matrix_b, GrB_BOOL, 2, 2);
429 :
430 1 : OK(GrB_Matrix_setElement(adj_matrix_b, true, 0, 1));
431 1 : OK(GrB_Matrix_setElement(adj_matrix_b, true, 1, 0));
432 :
433 1 : adj_matrices[0] = adj_matrix_a;
434 1 : adj_matrices[1] = adj_matrix_b;
435 1 : }
436 :
437 : //====================
438 : // Tests with valid result
439 : //====================
440 :
441 1 : void test_CFL_reachability_cycle(void) {
442 : #if LAGRAPH_SUITESPARSE
443 1 : setup();
444 : GrB_Info retval;
445 :
446 1 : init_grammar_aS();
447 1 : init_graph_one_cycle();
448 1 : init_outputs() ;
449 :
450 1 : OK(run_algorithm());
451 1 : check_result("(0, 0) (0, 1) (0, 2) (1, 0) (1, 1) (1, 2) (2, 0) (2, 1) (2, 2)");
452 :
453 1 : free_workspace();
454 1 : teardown();
455 : #endif
456 1 : }
457 :
458 1 : void test_CFL_reachability_two_cycle(void) {
459 : #if LAGRAPH_SUITESPARSE
460 1 : setup();
461 : GrB_Info retval;
462 :
463 1 : init_grammar_aSb();
464 1 : init_graph_double_cycle();
465 1 : init_outputs() ;
466 :
467 1 : OK(run_algorithm());
468 1 : check_result("(0, 0) (0, 3) (1, 0) (1, 3) (2, 0) (2, 3)");
469 :
470 1 : free_workspace();
471 1 : teardown();
472 : #endif
473 1 : }
474 :
475 1 : void test_CFL_reachability_labels_more_than_nonterms(void) {
476 : #if LAGRAPH_SUITESPARSE
477 1 : setup();
478 : GrB_Info retval;
479 :
480 1 : init_grammar_aSb();
481 1 : init_graph_2();
482 1 : init_outputs() ;
483 :
484 1 : OK(run_algorithm());
485 1 : check_result("(0, 1)");
486 :
487 1 : free_workspace();
488 1 : teardown();
489 : #endif
490 1 : }
491 :
492 1 : void test_CFL_reachability_complex_grammar(void) {
493 : #if LAGRAPH_SUITESPARSE
494 1 : setup();
495 : GrB_Info retval;
496 :
497 1 : init_grammar_complex();
498 1 : init_graph_1();
499 1 : init_outputs() ;
500 :
501 1 : OK(run_algorithm());
502 1 : check_result("(0, 7) (1, 6)");
503 :
504 1 : free_workspace();
505 1 : teardown();
506 : #endif
507 1 : }
508 :
509 1 : void test_CFL_reachability_tree(void) {
510 : #if LAGRAPH_SUITESPARSE
511 1 : setup();
512 : GrB_Info retval;
513 :
514 1 : init_grammar_aSb();
515 1 : init_graph_tree();
516 1 : init_outputs() ;
517 :
518 1 : OK(run_algorithm());
519 1 : check_result("(0, 0) (0, 1) (0, 3) (0, 4) (1, 0) (1, 1) (1, 3) (1, 4) (2, 2) (2, 5) "
520 : "(3, 0) (3, 1) (3, 3) (3, 4) (4, 0) (4, 1) (4, 3) (4, 4) (5, 2) (5, 5)");
521 :
522 1 : free_workspace();
523 1 : teardown();
524 : #endif
525 1 : }
526 :
527 1 : void test_CFL_reachability_line(void) {
528 : #if LAGRAPH_SUITESPARSE
529 1 : setup();
530 : GrB_Info retval;
531 :
532 1 : init_grammar_aSb();
533 1 : init_graph_line();
534 1 : init_outputs() ;
535 :
536 1 : OK(run_algorithm());
537 1 : check_result("(0, 4) (1, 3)");
538 :
539 1 : free_workspace();
540 1 : teardown();
541 : #endif
542 1 : }
543 :
544 1 : void test_CFL_reachability_two_nodes_cycle(void) {
545 : #if LAGRAPH_SUITESPARSE
546 1 : setup();
547 : GrB_Info retval;
548 :
549 1 : init_grammar_aSb();
550 1 : init_graph_3();
551 1 : init_outputs() ;
552 :
553 1 : OK(run_algorithm());
554 1 : check_result("(0, 0) (1, 0)");
555 :
556 1 : free_workspace();
557 1 : teardown();
558 : #endif
559 1 : }
560 :
561 1 : void test_CFL_reachability_with_empty_adj_matrix(void) {
562 : #if LAGRAPH_SUITESPARSE
563 1 : setup();
564 : GrB_Info retval;
565 :
566 1 : init_grammar_aS();
567 1 : init_graph_4();
568 1 : init_outputs() ;
569 :
570 1 : OK(run_algorithm());
571 1 : check_result("(0, 0) (1, 1)");
572 :
573 1 : free_workspace();
574 1 : teardown();
575 : #endif
576 1 : }
577 :
578 : //====================
579 : // Tests with invalid result
580 : //====================
581 :
582 1 : void test_CFL_reachability_invalid_rules(void) {
583 : #if LAGRAPH_SUITESPARSE
584 1 : setup();
585 : GrB_Info retval;
586 :
587 1 : init_grammar_aSb();
588 1 : init_graph_double_cycle();
589 1 : init_outputs() ;
590 :
591 : // Rule [Variable -> _ B]
592 1 : grammar.rules[0] =
593 : (LAGraph_rule_WCNF){.nonterm = 0, .prod_A = -1, .prod_B = 1, .index = 0};
594 1 : check_error(GrB_INVALID_VALUE);
595 :
596 : // Rule [_ -> A B]
597 1 : grammar.rules[0] =
598 : (LAGraph_rule_WCNF){.nonterm = -1, .prod_A = 1, .prod_B = 2, .index = 0};
599 1 : check_error(GrB_INVALID_VALUE);
600 :
601 : // Rule [C -> A B], where C >= nonterms_count
602 1 : grammar.rules[0] =
603 : (LAGraph_rule_WCNF){.nonterm = 10, .prod_A = 1, .prod_B = 2, .index = 0};
604 1 : check_error(GrB_INVALID_VALUE);
605 :
606 : // Rule [S -> A B], where A >= nonterms_count
607 1 : grammar.rules[0] =
608 : (LAGraph_rule_WCNF){.nonterm = 0, .prod_A = 10, .prod_B = 2, .index = 0};
609 1 : check_error(GrB_INVALID_VALUE);
610 :
611 : // Rule [C -> t], where t >= terms_count
612 1 : grammar.rules[0] =
613 : (LAGraph_rule_WCNF){.nonterm = 0, .prod_A = 10, .prod_B = -1, .index = 0};
614 1 : check_error(GrB_INVALID_VALUE);
615 :
616 1 : free_workspace();
617 1 : teardown();
618 : #endif
619 1 : }
620 :
621 1 : void test_CFL_reachability_null_pointers(void) {
622 : #if LAGRAPH_SUITESPARSE
623 :
624 1 : setup();
625 : GrB_Info retval;
626 :
627 1 : init_grammar_aSb();
628 1 : init_graph_double_cycle();
629 1 : init_outputs() ;
630 :
631 : // adj_matrices[0] = NULL;
632 : // adj_matrices[1] = NULL;
633 1 : GrB_free(&adj_matrices[0]);
634 1 : GrB_free(&adj_matrices[1]);
635 :
636 1 : check_error(GrB_NULL_POINTER);
637 :
638 : // adj_matrices = NULL;
639 1 : LAGraph_Free ((void **) &adj_matrices, msg);
640 1 : check_error(GrB_NULL_POINTER);
641 :
642 1 : free_workspace();
643 1 : init_grammar_aSb();
644 1 : init_graph_double_cycle();
645 1 : init_outputs() ;
646 :
647 : // outputs = NULL;
648 1 : LAGraph_Free ((void **) &outputs, msg);
649 1 : check_error(GrB_NULL_POINTER);
650 :
651 1 : free_workspace();
652 1 : init_grammar_aSb();
653 1 : init_graph_double_cycle();
654 1 : init_outputs() ;
655 :
656 : // grammar.rules = NULL;
657 1 : LAGraph_Free ((void **) &grammar.rules, msg);
658 1 : check_error(GrB_NULL_POINTER);
659 :
660 1 : free_workspace();
661 1 : teardown();
662 : #endif
663 1 : }
664 :
665 : TEST_LIST = {{"CFL_reachability_complex_grammar", test_CFL_reachability_complex_grammar},
666 : {"CFL_reachability_cycle", test_CFL_reachability_cycle},
667 : {"CFL_reachability_two_cycle", test_CFL_reachability_two_cycle},
668 : {"CFL_reachability_labels_more_than_nonterms",
669 : test_CFL_reachability_labels_more_than_nonterms},
670 : {"CFL_reachability_tree", test_CFL_reachability_tree},
671 : {"CFL_reachability_line", test_CFL_reachability_line},
672 : {"CFL_reachability_two_nodes_cycle", test_CFL_reachability_two_nodes_cycle},
673 : {"CFG_reach_basic_invalid_rules", test_CFL_reachability_invalid_rules},
674 : {"test_CFL_reachability_with_empty_adj_matrix", test_CFL_reachability_with_empty_adj_matrix},
675 : #if !defined ( GRAPHBLAS_HAS_CUDA )
676 : {"CFG_reachability_null_pointers", test_CFL_reachability_null_pointers},
677 : #endif
678 : {NULL, NULL}};
679 :
|
