Line data Source code
1 : #include <stdio.h>
2 : #include <acutest.h>
3 : #include <LG_Xtest.h>
4 : #include <LG_test.h>
5 : #include <LAGraphX.h>
6 : #include <LAGraph_test.h>
7 :
8 : #define LEN 512
9 : #define MAX_LABELS 3
10 : #define MAX_RESULTS 2000000
11 :
12 : char msg [LAGRAPH_MSG_LEN] ;
13 : LAGraph_Graph G[MAX_LABELS] ;
14 : LAGraph_Graph R[MAX_LABELS] ;
15 : GrB_Matrix A ;
16 :
17 : char testcase_name [LEN+1] ;
18 : char filename [LEN+1] ;
19 :
20 : typedef struct
21 : {
22 : const char* name ;
23 : const char* graphs[MAX_LABELS] ;
24 : const char* fas[MAX_LABELS] ;
25 : const char* fa_meta ;
26 : const char* sources ;
27 : const GrB_Index expected[MAX_RESULTS] ;
28 : const size_t expected_count ;
29 : }
30 : matrix_info ;
31 :
32 : const matrix_info files [ ] =
33 : {
34 : {"simple 1 or more",
35 : {"rpq_data/a.mtx", "rpq_data/b.mtx", NULL},
36 : {"rpq_data/1_a.mtx", NULL }, // Regex: a+
37 : "rpq_data/1_meta.txt",
38 : "rpq_data/1_sources.txt",
39 : {2, 4, 6, 7}, 4},
40 : {"simple kleene star",
41 : {"rpq_data/a.mtx", "rpq_data/b.mtx", NULL},
42 : {"rpq_data/2_a.mtx", "rpq_data/2_b.mtx", NULL}, // Regex: (a b)*
43 : "rpq_data/2_meta.txt",
44 : "rpq_data/2_sources.txt",
45 : {2, 6, 8}, 3},
46 : {"kleene star of the conjunction",
47 : {"rpq_data/a.mtx", "rpq_data/b.mtx", NULL},
48 : {"rpq_data/3_a.mtx", "rpq_data/3_b.mtx", NULL}, // Regex: (a | b)*
49 : "rpq_data/3_meta.txt",
50 : "rpq_data/3_sources.txt",
51 : {3, 6}, 2},
52 : {"simple repeat from n to m times",
53 : {"rpq_data/a.mtx", "rpq_data/b.mtx", NULL},
54 : {"", "rpq_data/4_b.mtx", NULL}, // Regex: b b b (b b)?
55 : "rpq_data/4_meta.txt",
56 : "rpq_data/4_sources.txt",
57 : {3, 4, 6}, 3},
58 : {NULL, NULL, NULL, NULL},
59 : } ;
60 :
61 : //****************************************************************************
62 1 : void test_RegularPathQueryBasic (void)
63 : {
64 1 : LAGraph_Init (msg) ;
65 :
66 5 : for (int k = 0 ; ; k++)
67 : {
68 5 : if (files[k].sources == NULL) break ;
69 :
70 4 : snprintf (testcase_name, LEN, "basic regular path query %s", files[k].name) ;
71 4 : TEST_CASE (testcase_name) ;
72 :
73 12 : for (int check_symmetry = 0 ; check_symmetry <= 1 ; check_symmetry++)
74 : {
75 : // Load graph from MTX files representing its adjacency matrix
76 : // decomposition
77 8 : for (int i = 0 ; ; i++)
78 16 : {
79 24 : const char *name = files[k].graphs[i] ;
80 :
81 24 : if (name == NULL) break ;
82 16 : if (strlen(name) == 0) continue ;
83 :
84 16 : snprintf (filename, LEN, LG_DATA_DIR "%s", name) ;
85 16 : FILE *f = fopen (filename, "r") ;
86 16 : TEST_CHECK (f != NULL) ;
87 16 : OK (LAGraph_MMRead (&A, f, msg)) ;
88 16 : OK (fclose (f));
89 :
90 16 : OK (LAGraph_New (&(G[i]), &A, LAGraph_ADJACENCY_DIRECTED, msg)) ;
91 :
92 16 : TEST_CHECK (A == NULL) ;
93 : }
94 :
95 : // Load NFA from MTX files representing its adjacency matrix
96 : // decomposition
97 8 : for (int i = 0 ; ; i++)
98 14 : {
99 22 : const char *name = files[k].fas[i] ;
100 :
101 22 : if (name == NULL) break ;
102 14 : if (strlen(name) == 0) continue ;
103 :
104 12 : snprintf (filename, LEN, LG_DATA_DIR "%s", name) ;
105 12 : FILE *f = fopen (filename, "r") ;
106 12 : TEST_CHECK (f != NULL) ;
107 12 : OK (LAGraph_MMRead (&A, f, msg)) ;
108 12 : OK (fclose (f)) ;
109 :
110 12 : OK (LAGraph_New (&(R[i]), &A, LAGraph_ADJACENCY_DIRECTED, msg)) ;
111 :
112 12 : if (check_symmetry)
113 : {
114 : // Check if the pattern is symmetric - if it isn't make it.
115 : // Note this also computes R[i]->AT
116 6 : OK (LAGraph_Cached_IsSymmetricStructure (R[i], msg)) ;
117 : }
118 :
119 12 : TEST_CHECK (A == NULL) ;
120 : }
121 :
122 : // Note the matrix rows/cols are enumerated from 0 to n-1.
123 : // Meanwhile, in MTX format they are enumerated from 1 to n. Thus,
124 : // when loading/comparing the results these values should be
125 : // decremented/incremented correspondingly.
126 :
127 : // Load graph source nodes from the sources file
128 : GrB_Index s ;
129 : GrB_Index S[16] ;
130 8 : size_t ns = 0 ;
131 :
132 8 : const char *name = files[k].sources ;
133 8 : snprintf (filename, LEN, LG_DATA_DIR "%s", name) ;
134 8 : FILE *f = fopen (filename, "r") ;
135 8 : TEST_CHECK (f != NULL) ;
136 :
137 20 : while (fscanf(f, "%" PRIu64, &s) != EOF)
138 : {
139 12 : S[ns++] = s - 1 ;
140 : }
141 :
142 8 : OK (fclose(f)) ;
143 :
144 : // Load NFA starting states from the meta file
145 : GrB_Index qs ;
146 : GrB_Index QS[16] ;
147 8 : size_t nqs = 0 ;
148 :
149 8 : name = files[k].fa_meta ;
150 8 : snprintf (filename, LEN, LG_DATA_DIR "%s", name) ;
151 8 : f = fopen (filename, "r") ;
152 8 : TEST_CHECK (f != NULL) ;
153 :
154 8 : uint64_t nqs64 = 0 ;
155 8 : TEST_CHECK (fscanf(f, "%" PRIu64, &nqs64) != EOF) ;
156 8 : nqs = (size_t) nqs64 ;
157 :
158 18 : for (uint64_t i = 0; i < nqs; i++) {
159 10 : TEST_CHECK (fscanf(f, "%" PRIu64, &qs) != EOF) ;
160 10 : QS[i] = qs - 1 ;
161 : }
162 :
163 : // Load NFA final states from the same file
164 : uint64_t qf ;
165 : uint64_t QF[16] ;
166 8 : size_t nqf = 0 ;
167 8 : uint64_t nqf64 = 0 ;
168 :
169 8 : TEST_CHECK (fscanf(f, "%" PRIu64, &nqf64) != EOF) ;
170 8 : nqf = (size_t) nqf64 ;
171 :
172 16 : for (uint64_t i = 0; i < nqf; i++) {
173 8 : TEST_CHECK (fscanf(f, "%" PRIu64, &qf) != EOF) ;
174 8 : QF[i] = qf - 1 ;
175 : }
176 :
177 8 : OK (fclose(f)) ;
178 :
179 : // Evaluate the algorithm
180 8 : GrB_Vector r = NULL ;
181 :
182 8 : OK (LAGraph_RegularPathQuery (&r, R, MAX_LABELS, QS, nqs,
183 : QF, nqf, G, S, ns, msg)) ;
184 :
185 : // Extract results from the output vector
186 : GrB_Index *reachable ;
187 : bool *values ;
188 :
189 : GrB_Index nvals ;
190 8 : GrB_Vector_nvals (&nvals, r) ;
191 :
192 8 : OK (LAGraph_Malloc ((void **) &reachable, MAX_RESULTS, sizeof (GrB_Index), msg)) ;
193 8 : OK (LAGraph_Malloc ((void **) &values, MAX_RESULTS, sizeof (GrB_Index), msg)) ;
194 :
195 8 : GrB_Vector_extractTuples (reachable, values, &nvals, r) ;
196 :
197 : // Compare the results with expected values
198 8 : TEST_CHECK (nvals == files[k].expected_count) ;
199 32 : for (uint64_t i = 0 ; i < nvals ; i++)
200 24 : TEST_CHECK (reachable[i] + 1 == files[k].expected[i]) ;
201 :
202 : // Cleanup
203 8 : OK (LAGraph_Free ((void **) &values, NULL)) ;
204 8 : OK (LAGraph_Free ((void **) &reachable, NULL)) ;
205 :
206 8 : OK (GrB_free (&r)) ;
207 :
208 32 : for (uint64_t i = 0 ; i < MAX_LABELS ; i++)
209 : {
210 24 : if (G[i] == NULL) continue ;
211 16 : OK (LAGraph_Delete (&(G[i]), msg)) ;
212 : }
213 :
214 32 : for (uint64_t i = 0 ; i < MAX_LABELS ; i++ )
215 : {
216 24 : if (R[i] == NULL) continue ;
217 12 : OK (LAGraph_Delete (&(R[i]), msg)) ;
218 : }
219 : }
220 : }
221 :
222 1 : LAGraph_Finalize (msg) ;
223 1 : }
224 :
225 :
226 : TEST_LIST = {
227 : {"RegularPathQueryBasic", test_RegularPathQueryBasic},
228 : {NULL, NULL}
229 : };
|
