Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LAGraph/experimental/test/test_MaximalMatching
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 Vidith Madhu, Texas A&M University
15 :
16 : //------------------------------------------------------------------------------
17 :
18 : /*
19 : NOTE: Unlike the other tests, this does not use .mtx files, but rather generates the test
20 : matrices using specified configurations and seeds with LAGraph_Random_Matrix
21 :
22 : */
23 :
24 : #include <stdio.h>
25 : #include <acutest.h>
26 : #include <LAGraphX.h>
27 : #include <LAGraph_test.h>
28 : #include <LG_Xtest.h>
29 :
30 : GrB_Vector matching = NULL , weight = NULL, node_degree = NULL, hop_nodes = NULL, hop_edges = NULL ;
31 : GrB_Matrix A = NULL, E = NULL, E_t = NULL ;
32 : LAGraph_Graph G = NULL ;
33 :
34 : typedef struct
35 : {
36 : double matching_val ; // for unweighted matchings, the size of the matching. For weighted, sum of edge weights
37 : int matching_type ; // 0: unweighted, 1: heavy, 2: light
38 : int is_exact ; // whether or not matching_val is exactly computed for this test
39 : const char *name ; // matrix file name
40 : }
41 : matrix_info ;
42 :
43 : const matrix_info tests [ ] =
44 : {
45 : // unweighted bipartite
46 : { 150, 0, 1, "random_unweighted_bipartite1.mtx" }, // 42
47 : { 150, 0, 1, "random_unweighted_bipartite2.mtx" }, // 69
48 : { 143, 0, 0, "random_unweighted_bipartite1.mtx" }, // repeat
49 : { 147, 0, 0, "random_unweighted_bipartite2.mtx" }, // repeat
50 :
51 : // unweighted general
52 : // { 25, 0, 1, 50, -1, 5.0 / 50, 31, "unweighted_general_1" } , // 31
53 : { 25, 0, 1, "random_unweighted_general1.mtx"},
54 : // { 100, 0, 1, 200, -1, 10.0 / 200, 101, "unweighted_general_2" }, // 101
55 : { 100, 0, 1, "random_unweighted_general2.mtx"},
56 : { 24, 0, 0, "random_unweighted_general1.mtx"},
57 : { 95, 0, 0, "random_unweighted_general2.mtx"},
58 :
59 : // weighted bipartite
60 : // answer, matching_type, is_exact, l_node, r_node, density, seed, name
61 : // { 3777422047635, 1, 0, 1000, 1000, 20.0 / 1000, 83, "weighted_bipartite_1" },
62 : { 775940425564, 1, 0, "random_weighted_bipartite1.mtx"}, // seed: 83, nodes: 500, spf: 8
63 : // { 9851292258178, 1, 0, 2500, 2500, 30.0 / 2500, 78, "weighted_bipartite_2" }
64 : { 417490248760, 1, 0, "random_weighted_bipartite2.mtx"}, // seed: 151, nodes: 300, spf: 5
65 : { 181453589490, 2, 0, "random_weighted_bipartite1.mtx" }, // repeat
66 : { 133704435764, 2, 0, "random_weighted_bipartite2.mtx" }, // repeat
67 : // weighted general
68 : { 783685067769, 1, 0, "random_weighted_general1.mtx" }, // seed: 137, nodes: 500, spf: 8
69 : { 420609293186, 1, 0, "random_weighted_general2.mtx" }, // seed: 62, nodes: 300, spf: 5
70 : { 165090013148, 2, 0, "random_weighted_general1.mtx" }, // repeat
71 : { 128746478507, 2, 0, "random_weighted_general2.mtx" }, // repeat
72 :
73 : { 0, 0, 0, "" }
74 : } ;
75 :
76 : double thresholds [ ] = {
77 : 0.85, // unweighted matching, exact
78 : 0.90, // unweighted matching, naive
79 : 0.80, // weighted matching, naive, light
80 : 0.90, // weighted matching, naive, heavy
81 : } ;
82 :
83 : #define SEEDS_PER_TEST 10
84 : #define LEN 512
85 :
86 : char filename [LEN+1] ;
87 : char msg [LAGRAPH_MSG_LEN] ;
88 :
89 1 : void test_MaximalMatching (void)
90 : {
91 : #if LAGRAPH_SUITESPARSE
92 1 : OK (LAGraph_Init (msg)) ;
93 : // OK (LG_SET_BURBLE (true)) ;
94 :
95 1 : for (int k = 0 ; ; k++)
96 16 : {
97 17 : const char *aname = tests [k].name ;
98 17 : if (strlen (aname) == 0) break ;
99 16 : printf ("\n======================= %s:\n", aname) ;
100 16 : TEST_CASE (aname) ;
101 :
102 : // old code using files
103 : //--------------
104 16 : snprintf (filename, LEN, LG_DATA_DIR "%s", aname) ;
105 16 : FILE *f = fopen (filename, "r") ;
106 16 : TEST_CHECK (f != NULL) ;
107 16 : TEST_MSG ("Filename %s is invalid", filename) ;
108 16 : OK (LAGraph_MMRead (&A, f, msg)) ;
109 16 : fclose (f) ;
110 : //--------------
111 :
112 16 : TEST_CHECK (A != NULL) ;
113 16 : TEST_MSG ("Building of adjacency matrix failed") ;
114 16 : GxB_print (A, 1) ;
115 :
116 16 : OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_DIRECTED, msg)) ;
117 :
118 16 : OK (LAGraph_Cached_NSelfEdges (G, msg)) ;
119 16 : OK (LAGraph_Cached_AT (G, msg)) ;
120 :
121 : // if (G->nself_edges != 0)
122 : {
123 : // remove self-edges
124 16 : printf ("graph has %g self edges\n", (double) G->nself_edges) ;
125 16 : OK (LAGraph_DeleteSelfEdges (G, msg)) ;
126 16 : printf ("now has %g self edges\n", (double) G->nself_edges) ;
127 16 : TEST_CHECK (G->nself_edges == 0) ;
128 : }
129 :
130 : // check if G is undirected
131 : // by definition, G->A must equal G->AT iff G is undirected
132 16 : bool ok = 0;
133 16 : OK (LAGraph_Matrix_IsEqual (&ok, G->A, G->AT, msg)) ;
134 16 : TEST_CHECK (ok) ;
135 16 : TEST_MSG ("Input graph is not undirected") ;
136 16 : G->kind = LAGraph_ADJACENCY_UNDIRECTED ;
137 :
138 16 : OK (LAGraph_Incidence_Matrix (&E, G, msg)) ;
139 : GrB_Index num_nodes ;
140 : GrB_Index num_edges ;
141 16 : OK (GrB_Matrix_nrows (&num_nodes, E)) ;
142 16 : OK (GrB_Matrix_ncols (&num_edges, E)) ;
143 16 : OK (GrB_Matrix_new (&E_t, GrB_FP64, num_edges, num_nodes)) ;
144 16 : OK (GrB_transpose (E_t, NULL, NULL, E, NULL)) ;
145 : // set to row major incase Incidence_Matrix gave col_major
146 16 : OK (GrB_set(E, GrB_ROWMAJOR, GrB_STORAGE_ORIENTATION_HINT)) ;
147 :
148 : // get weight vector
149 16 : OK (GrB_Vector_new (&weight, GrB_FP64, num_edges)) ;
150 16 : OK (GrB_reduce (weight, NULL, NULL, GrB_MAX_MONOID_FP64, E_t, NULL)) ;
151 :
152 : // used to check correctness of matching
153 16 : OK (GrB_Vector_new (&node_degree, GrB_UINT64, num_nodes)) ;
154 :
155 16 : OK (GrB_Vector_new (&hop_edges, GrB_BOOL, num_edges)) ;
156 16 : OK (GrB_Vector_new (&hop_nodes, GrB_BOOL, num_nodes)) ;
157 :
158 16 : double avg_acc = 0 ;
159 : size_t which_threshold ;
160 16 : uint64_t seed = 0 ;
161 : // run max matching
162 176 : for (int i = 0; i < SEEDS_PER_TEST; i++){
163 : // try random seeds
164 160 : OK (LAGraph_MaximalMatching (&matching, E, E_t, tests [k].matching_type, seed, msg)) ;
165 : // check correctness
166 160 : OK (GrB_mxv (node_degree, NULL, NULL, LAGraph_plus_one_uint64, E, matching, NULL)) ;
167 : GrB_Index max_degree ;
168 160 : OK (GrB_reduce (&max_degree, NULL, GrB_MAX_MONOID_UINT64, node_degree, NULL)) ;
169 160 : TEST_CHECK (max_degree <= 1) ;
170 160 : TEST_MSG ("Matching is invalid") ;
171 : // check maximality
172 : // not maximal <-> there is an edge where neither node is matched
173 : // we can do a 1-hop from the matched edges and see if every edge in the graph is covered
174 160 : OK (GrB_mxv (hop_nodes, NULL, NULL, LAGraph_any_one_bool, E, matching, NULL)) ;
175 160 : OK (GrB_mxv (hop_edges, NULL, NULL, LAGraph_any_one_bool, E_t, hop_nodes, NULL)) ;
176 : GrB_Index hop_edges_nvals ;
177 160 : OK (GrB_Vector_nvals (&hop_edges_nvals, hop_edges)) ;
178 160 : TEST_CHECK (hop_edges_nvals == num_edges) ;
179 160 : TEST_MSG ("Matching is not maximal") ;
180 : // check that the value of the matching is close enough
181 160 : double expected = tests [k].matching_val ;
182 160 : double matching_value = 0 ;
183 :
184 160 : if (tests [k].matching_type == 0) {
185 : // unweighted
186 : // we only care about the number of chosen edges
187 : uint64_t matching_val_int ;
188 80 : OK (GrB_Vector_nvals (&matching_val_int, matching)) ;
189 80 : matching_value = matching_val_int ;
190 80 : if (tests [k].is_exact) {
191 40 : which_threshold = 0 ;
192 : } else {
193 40 : which_threshold = 1 ;
194 : }
195 : } else {
196 : // weighted
197 : // sum the weights of the chosen edges.
198 : // eliminate entries in the weight that are not in the matching, then sum the remaining entries
199 80 : GrB_Vector use_weights = NULL ;
200 :
201 80 : OK (GrB_Vector_new (&use_weights, GrB_FP64, num_edges)) ;
202 80 : OK (GrB_eWiseMult (use_weights, NULL, NULL, GrB_TIMES_FP64, weight, matching, NULL)) ;
203 80 : OK (GrB_reduce (&matching_value, NULL, GrB_PLUS_MONOID_FP64, use_weights, NULL)) ;
204 80 : OK (GrB_free (&use_weights)) ;
205 :
206 80 : which_threshold = 3 ;
207 : }
208 160 : if (which_threshold == 0) {
209 : // exact matching must have strict upper bound
210 40 : printf ("matching_value %g expected %g\n", matching_value, expected) ;
211 40 : TEST_CHECK (matching_value <= expected) ;
212 : }
213 160 : double acc = matching_value / expected ;
214 160 : if (tests [k].matching_type == 2) {
215 : // flip it for light matchings
216 40 : acc = expected / matching_value ;
217 40 : which_threshold = 2 ;
218 : }
219 160 : avg_acc += acc ;
220 160 : OK (GrB_free (&matching)) ;
221 160 : seed += num_nodes ;
222 : }
223 16 : avg_acc /= SEEDS_PER_TEST ;
224 16 : ok = (avg_acc >= thresholds [which_threshold]) ;
225 :
226 16 : TEST_CHECK (ok) ;
227 16 : printf ("Value of produced matching has %.5f accuracy, passing threshold is %.5f\n for case (%d)\n", avg_acc, thresholds [which_threshold], k) ;
228 :
229 16 : OK (GrB_free (&A)) ;
230 16 : OK (GrB_free (&E)) ;
231 16 : OK (GrB_free (&E_t)) ;
232 16 : OK (GrB_free (&weight)) ;
233 16 : OK (GrB_free (&node_degree)) ;
234 16 : OK (GrB_free (&hop_edges)) ;
235 16 : OK (GrB_free (&hop_nodes)) ;
236 :
237 16 : OK (LAGraph_Delete (&G, msg)) ;
238 : }
239 1 : OK (LAGraph_Finalize (msg)) ;
240 : #endif
241 1 : }
242 :
243 1 : void test_MaximalMatchingErrors (void)
244 : {
245 : #if LAGRAPH_SUITESPARSE
246 1 : OK (LAGraph_Init (msg)) ;
247 : // OK (LG_SET_BURBLE (true)) ;
248 :
249 1 : E = NULL ;
250 1 : matching = NULL ;
251 :
252 1 : OK (GrB_Matrix_new (&E, GrB_FP64, 1, 1)) ;
253 :
254 : // result pointer is null
255 1 : GrB_Info result = LAGraph_MaximalMatching (NULL, E, E, 0, 0, msg) ;
256 1 : printf ("\nresult: %d %s\n", result, msg) ;
257 1 : TEST_CHECK (result == GrB_NULL_POINTER) ;
258 :
259 : // E matrix is null
260 1 : result = LAGraph_MaximalMatching (&matching, NULL, E, 0, 0, msg) ;
261 1 : printf ("\nresult: %d %s\n", result, msg) ;
262 1 : TEST_CHECK (result == GrB_NULL_POINTER) ;
263 :
264 : // E_t matrix is null
265 1 : result = LAGraph_MaximalMatching (&matching, E, NULL, 0, 0, msg) ;
266 1 : printf ("\nresult: %d %s\n", result, msg) ;
267 1 : TEST_CHECK (result == GrB_NULL_POINTER) ;
268 :
269 1 : GrB_free (&E) ;
270 1 : OK (LAGraph_Finalize (msg)) ;
271 : #endif
272 1 : }
273 :
274 : TEST_LIST = {
275 : { "MaximalMatching", test_MaximalMatching },
276 : { "MaximalMatchingErrors", test_MaximalMatchingErrors },
277 : { NULL, NULL }
278 : } ;
|
