Line data Source code
1 : #include <acutest.h>
2 : #include <stdio.h>
3 :
4 : #include "LG_internal.h"
5 : #include <LAGraphX.h>
6 : #include <LAGraph_test.h>
7 : #include <LG_Xtest.h>
8 :
9 : char msg[LAGRAPH_MSG_LEN];
10 : LAGraph_Graph G = NULL;
11 : GrB_Vector mateC = NULL;
12 : GrB_Vector mateR = NULL;
13 : GrB_Vector mateC_init = NULL;
14 : GrB_Vector mateR_init = NULL;
15 :
16 : #define LEN 512
17 : char filename[LEN + 1];
18 :
19 : #define NTESTS 5
20 :
21 : const char *filenames[NTESTS] = {"random_weighted_bipartite2.mtx",
22 : "test_FW_2500.mtx", "LFAT5_hypersparse.mtx",
23 : "lp_afiro_structure.mtx", "sources_7.mtx"};
24 : const uint64_t spranks[NTESTS] = {298, 2009, 14, 27, 1};
25 :
26 : #if 0
27 : #undef OK
28 : #define OK(method) \
29 : { \
30 : GrB_Info info2 = method ; \
31 : if (info2 != GrB_SUCCESS) \
32 : { \
33 : printf ("info: %d, msg: %s\n", info2, msg) ; \
34 : TEST_CHECK (false) ; \
35 : } \
36 : }
37 : #endif
38 :
39 1 : void test_MCM(void)
40 : {
41 : #if LAGRAPH_SUITESPARSE
42 1 : LAGraph_Init(msg);
43 :
44 : // OK(LG_SET_BURBLE(1));
45 :
46 3 : for (uint8_t jit = 0; jit < 2; jit++)
47 : {
48 2 : uint8_t JIT_flag = jit * 4; // JIT_OFF = 0 and JIT_ON = 4
49 2 : OK (LG_SET_JIT (JIT_flag)) ;
50 12 : for (uint64_t test = 0; test < NTESTS; test++)
51 : {
52 :
53 10 : printf ("\n%s =======================\n", filenames [test]) ;
54 10 : GrB_Matrix A = NULL;
55 10 : GrB_Matrix AT = NULL;
56 10 : snprintf(filename, LEN, LG_DATA_DIR "%s", filenames[test]);
57 10 : FILE *f = fopen(filename, "r");
58 10 : TEST_CHECK(f != NULL);
59 10 : OK(LAGraph_MMRead(&A, f, msg));
60 10 : OK(fclose(f));
61 10 : GrB_Index nrows = 0, ncols = 0, nvals = 0;
62 10 : OK(GrB_Matrix_nrows(&nrows, A));
63 10 : OK(GrB_Matrix_ncols(&ncols, A));
64 10 : OK(GrB_Matrix_nvals(&nvals, A));
65 :
66 : // make A a bool matrix and iso-valued
67 : GrB_Index *I, *J, *X;
68 : double *dummy;
69 : bool *iso_value;
70 :
71 10 : OK(LAGraph_Malloc((void **)&I, nvals, sizeof(GrB_Index), msg));
72 10 : OK(LAGraph_Malloc((void **)&J, nvals, sizeof(GrB_Index), msg));
73 10 : OK(LAGraph_Malloc((void **)&dummy, nvals, sizeof(double), msg));
74 10 : OK(LAGraph_Malloc((void **)&iso_value, nvals, sizeof(bool), msg));
75 :
76 19094 : for (uint64_t i = 0; i < nvals; i++)
77 : {
78 19084 : iso_value[i] = 1;
79 : }
80 10 : OK(GrB_Matrix_extractTuples_FP64(I, J, dummy, &nvals, A));
81 10 : TEST_CHECK(I != NULL);
82 :
83 10 : OK(GrB_free(&A));
84 10 : OK(GrB_Matrix_new(&A, GrB_BOOL, nrows, ncols));
85 10 : OK(GrB_Matrix_build_BOOL(A, I, J, iso_value, nvals,
86 : GrB_FIRST_BOOL));
87 :
88 10 : OK(LAGraph_Free((void **)&I, msg));
89 10 : OK(LAGraph_Free((void **)&J, msg));
90 10 : OK(LAGraph_Free((void **)&dummy, msg));
91 10 : OK(LAGraph_Free((void **)&iso_value, msg));
92 :
93 10 : OK(GrB_Vector_new(&mateC, GrB_UINT64, ncols));
94 :
95 10 : if (!strcmp(filenames[test], "lp_afiro_structure.mtx"))
96 : {
97 2 : OK(GrB_Vector_new(&mateC_init, GrB_UINT64, ncols));
98 2 : OK(GrB_Vector_new(&mateR_init, GrB_UINT64, nrows));
99 2 : OK(GrB_Vector_setElement_UINT64(
100 : mateC_init, 0, 19)); // col 20 matched with row 1 (1-based)
101 2 : OK(GrB_Vector_setElement_UINT64(
102 : mateR_init, 19, 0)); // col 20 matched with row 1 (1-based)
103 2 : OK(GrB_Matrix_new(&AT, GrB_BOOL, ncols,
104 : nrows)); // transpose matrix has the reverse
105 : // dimensions from the original
106 2 : OK(GrB_transpose(AT, NULL, NULL, A, NULL));
107 : }
108 :
109 10 : OK(GrB_free(&mateC));
110 10 : OK(LAGr_MaximumMatching(&mateC, NULL, A, AT, mateC_init, true,
111 : msg));
112 : // printf("\nmsg: %s\n", msg);
113 :
114 10 : GrB_Index nmatched = 0;
115 :
116 10 : OK(GrB_Vector_new(&mateR, GrB_UINT64, nrows));
117 :
118 : // invert to check for dups
119 10 : GrB_Index Ibytes = 0, Jbytes = 0, Xbytes = 0;
120 10 : bool jumbled = 1;
121 10 : OK(GxB_Vector_unpack_CSC(mateC, (GrB_Index **)&J, (void **)&X,
122 : &Jbytes, &Xbytes, NULL, &nmatched,
123 : &jumbled, NULL));
124 10 : OK(GrB_Vector_build_UINT64(mateR, X, J, nmatched,
125 : GrB_FIRST_UINT64));
126 10 : GrB_Index nmateR = 0;
127 10 : OK(GrB_Vector_nvals(&nmateR, mateR));
128 : // if nvals of mateC and mateR don't match, then there's at least
129 : // one row that is used in at least one matching
130 10 : TEST_CHECK(nmatched == nmateR);
131 10 : printf ("# of matches: %" PRIu64 "\n", nmatched) ;
132 :
133 : // pack matched values in a matrix
134 10 : GrB_Matrix M = NULL;
135 : bool *val;
136 10 : OK(LAGraph_Malloc((void **)&val, nmatched, sizeof(bool), msg));
137 4708 : for (uint64_t i = 0; i < nmatched; i++)
138 : {
139 4698 : val[i] = 1;
140 : }
141 10 : OK(GrB_Matrix_new(&M, GrB_BOOL, nrows, ncols));
142 10 : OK(GrB_Matrix_build_BOOL(M, X, J, val, nmatched, NULL));
143 10 : OK(LAGraph_Free((void **)&val, msg));
144 10 : OK(LAGraph_Free((void **)&J, msg));
145 10 : OK(LAGraph_Free((void **)&X, msg));
146 : // mask with matrix A to check if all edges are present in A
147 10 : OK(GrB_Matrix_assign(M, M, NULL, A, GrB_ALL, nrows, GrB_ALL, ncols,
148 : GrB_DESC_S));
149 10 : GrB_Index nvalsM = 0;
150 10 : OK(GrB_Matrix_nvals(&nvalsM, M));
151 : // if values have been eliminated then edges do not exist in A
152 10 : TEST_CHECK(nvalsM == nmatched);
153 :
154 : // sprank must be equal to nvals of mateC (nmatched)
155 10 : TEST_CHECK(nmatched == spranks[test]);
156 :
157 10 : OK(GrB_free(&mateC));
158 10 : OK(GrB_free(&mateR));
159 10 : OK(GrB_free(&M));
160 :
161 : // return both mateR and mateC
162 10 : OK(LAGr_MaximumMatching(&mateC, &mateR, A, AT, mateC_init, true,
163 : msg));
164 10 : GrB_Index nmateC = 0 ;
165 10 : nmateR = 0 ;
166 10 : OK(GrB_Vector_nvals(&nmateC, mateC));
167 10 : OK(GrB_Vector_nvals(&nmateR, mateR));
168 10 : TEST_CHECK(nmateC == nmateR);
169 10 : TEST_CHECK(nmateC == nmatched);
170 10 : OK(GrB_free(&mateC));
171 10 : OK(GrB_free(&mateR));
172 :
173 : // ensure AT exists, and pass in AT only, and use mateR_init
174 10 : if (AT == NULL)
175 : {
176 8 : OK(GrB_Matrix_new(&AT, GrB_BOOL, ncols, nrows));
177 8 : OK(GrB_transpose(AT, NULL, NULL, A, NULL));
178 : }
179 10 : OK(LAGr_MaximumMatching(&mateC, &mateR, NULL, AT, mateR_init, false,
180 : msg));
181 10 : nmateC = 0 ;
182 10 : nmateR = 0 ;
183 10 : OK(GrB_Vector_nvals(&nmateC, mateC));
184 10 : OK(GrB_Vector_nvals(&nmateR, mateR));
185 10 : TEST_CHECK(nmateC == nmateR);
186 10 : TEST_CHECK(nmateC == nmatched);
187 10 : OK(GrB_free(&mateC));
188 10 : OK(GrB_free(&mateR));
189 :
190 10 : OK(GrB_free(&mateC_init));
191 10 : OK(GrB_free(&mateR_init));
192 10 : OK(GrB_free(&A));
193 10 : OK(GrB_free(&AT));
194 :
195 : }
196 : }
197 1 : LAGraph_Finalize(msg);
198 : #endif
199 1 : }
200 :
201 : TEST_LIST = {{"MaximumMatching", test_MCM}, // just one test in this example
202 : {NULL, NULL}};
203 :
|
