Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LAGraph_Coarsen_Matching: Coarsen an undirected graph using an edge matching
3 : //------------------------------------------------------------------------------
4 :
5 : // LAGraph, (c) 2022 by The LAGraph Contributors, All Rights Reserved.
6 : // SPDX-License-Identifier: BSD-2-Clause
7 :
8 : // Contributed by Vidith Madhu, Texas A&M University
9 :
10 : //------------------------------------------------------------------------------
11 :
12 : // TODO: ready for src? need a vanilla non-GxB, and incidence graphs.
13 :
14 : /*
15 : This method is used to coarsen an undirected graph. The coarsening is based on a maximal matching,
16 : which is handled by LAGraph_MaximalMatching.
17 :
18 : The coarsening step involves a reduction from a graph G to G', where we use a bijection f from
19 : nodes in G to nodes in G'. We can consider f(u) to be the parent of node u.
20 : For each edge (u, v) in G, we add an edge (f(u), f(v)) to G' iff f(u) != f(v). In our case,
21 : this bijection is given by the maximal matching, where for every matched edge, one of the endpoints of the edge is the
22 : parent (representative) of both endpoints, and any node not part of a matched edge is its own parent.
23 :
24 : This method performs a single coarsening step on the input graph.
25 :
26 : The inputs to this algorithm are as follows in order:
27 : 1. an LAGraph_Graph containing the target graph to coarsen
28 : 2. the type of matching to perform (random, heavy, or light)
29 : 3. whether to retain the size of the graph when coarsening. If 1, then nodes that are eliminated by a coarsening step
30 : are turned into singletons. If 0, the size of the graph is changed and nodes are explicitly relabeled.
31 : 4. whether edges that are combined during a coarsening step should have their edge weights summed (for an unweighted graph, this
32 : counts the number of combined edges). If this option is false, then only the pattern of combined edges is retained.
33 : 6. Random seed used for maximal matching (same for every coarsening step)
34 : 7. msg for LAGraph error reporting
35 :
36 : There are 4 outputs from the function:
37 : 1. A GrB_Matrix of the coarsened graph (if the input adjacency matrix is of type GrB_BOOL or GrB_UINT{8|16|32} or GrB_INT*, it will
38 : have type GrB_INT64. If it is of type GrB_FP32, it will have type GrB_FP64. Else, it will have the same type as the input matrix.
39 :
40 : 2. A full GrB_Vector (parent_result) of length n where if parent_result[u] = v,
41 : then node u has parent v. This parent mapping is derived from a maximal matching of the graph
42 : and is used for the coarsening step (meaning node u collapses into node v).
43 :
44 : 3. A GrB_Vector (newlabels_result) of length n where if newlabels_result[u] = v,
45 : then node u in G is relabeled as node v in G', where G' is the coarsened graph. In addition, newlabels_result[u] exists iff node u survives the i-th coarsening step.
46 : If preserve_mapping = 1, then this result is returned as NULL since no relabeling occurs. This result is used to interpret the contents of parent_result,
47 : since the labels of nodes may change in an arbitrary fashion for each coarsening step.
48 :
49 : 4. A full GrB_Vector (inv_newlabels_result) of length n' (the number of vertices in the coarsened graph) where if inv_newlabels_result[u] = v,
50 : then node u in G' had an original label as node v in G, where G' is the coarsened graph. In other words, this is simply the inverse of result (3).
51 : If preserve_mapping = 1, this is returned as NULL.
52 :
53 : NOTE: Results (2), (3), and (4) are only computed/returned if they are not passed as a NULL pointer on input.
54 : Passing a NULL pointer denotes that the user does not want that particular result, and no return value is given.
55 : This means that a NULL pointer may safely be passed on input.
56 :
57 : This method requires O(n + e) space for an undirected graph with e edges and n nodes
58 : */
59 :
60 : #include "LG_internal.h"
61 : #include "LAGraphX.h"
62 :
63 : // #define dbg
64 : // #define burble
65 :
66 : #undef LG_FREE_ALL
67 : #undef LG_FREE_WORK
68 :
69 : #define LG_FREE_WORK \
70 : { \
71 : GrB_free(&parent_cpy) ; \
72 : GrB_free(&one) ; \
73 : GrB_free(&VALUEEQ_ROWINDEX_UINT64) ; \
74 : LAGraph_Free ((void**) &original_indices, NULL) ; \
75 : LAGraph_Free ((void**) &original_values, NULL) ; \
76 : LAGraph_Free ((void**) &preserved_values, NULL) ; \
77 : LAGraph_Free ((void**) &S_rows, NULL) ; \
78 : LAGraph_Free ((void**) &S_cols, NULL) ; \
79 : } \
80 :
81 : #define LG_FREE_ALL \
82 : { \
83 : LG_FREE_WORK ; \
84 : GrB_free(&S) ; \
85 : } \
86 :
87 : #define F_INDEX_UNARY(f) ((void (*)(void *, const void *, GrB_Index, GrB_Index, const void *)) f)
88 :
89 : #if LAGRAPH_SUITESPARSE
90 :
91 6130 : void valueeq_index_func (bool *z, const uint64_t *x, GrB_Index i, GrB_Index j, const void *y) {
92 6130 : (*z) = ((*x) == i) ;
93 6130 : }
94 :
95 50 : static int LAGraph_Parent_to_S
96 : (
97 : // input/outputs:
98 : GrB_Matrix *result, // resulting S matrix
99 : GrB_Vector *newlabels, // The contents of some newlabels_result[i], where newlabels_result is as described at the top of the file.
100 : // if NULL on input, will not return anything. If preserve_mapping = 1, the return value is a NULL GrB_Vector.
101 :
102 : GrB_Vector *inv_newlabels, // The contents of some inv_newlabels_result[i], where inv_newlabels_result is as described at the top of the file.
103 : // if NULL on input, will not return anything. If preserve_mapping = 1, the return value is a NULL GrB_Vector.
104 :
105 : // strictly inputs:
106 : GrB_Vector parent, // dense integer vector of size n. parent[i] -> representative of node i
107 : int preserve_mapping, // whether to preserve the original namespace of nodes, or to compress it down
108 : GrB_Type S_type, // type of constructed S matrix
109 : char *msg
110 : )
111 : {
112 50 : GrB_Vector parent_cpy = NULL ; // used so we don't modify the input parent vector. Also useful to have for computing newlabels
113 50 : GrB_Matrix S = NULL ; // stores the resulting S matrix
114 :
115 : // ------------------------ BUILDING S MATRIX --------------------------
116 : // used to unpack parent_cpy and build S
117 50 : GrB_Index *S_cols = NULL, *S_rows = NULL, S_cols_size, S_rows_size ;
118 50 : GrB_Scalar one = NULL ;
119 : GrB_Index nvals ;
120 : // ---------------------------------------------------------------------
121 :
122 :
123 : // ----------------------- NODE COMPRESSION -----------------------------
124 : // No need to free this since it gets packed back
125 50 : uint64_t *ramp = NULL ;
126 : // used to unpack preserved nodes
127 : // note: No need to free the array since it is packed back
128 50 : GrB_Index *preserved_indices = NULL, preserved_indices_size, preserved_values_size ;
129 : // need to free this (not packed back)
130 50 : uint64_t *preserved_values = NULL ;
131 : // used to extractTuples for original parent
132 50 : GrB_Index *original_indices = NULL ;
133 50 : uint64_t *original_values = NULL ;
134 :
135 : GrB_Index num_preserved ;
136 : bool is_jumbled ;
137 :
138 50 : GrB_IndexUnaryOp VALUEEQ_ROWINDEX_UINT64 = NULL ;
139 : // ---------------------------------------------------------------------
140 :
141 : // number of nodes in original graph
142 : GrB_Index n ;
143 :
144 50 : GRB_TRY (GrB_Vector_nvals (&n, parent)) ;
145 :
146 50 : if (preserve_mapping) {
147 : // parent_cpy will be the same as parent
148 24 : GRB_TRY (GrB_Vector_dup (&parent_cpy, parent)) ;
149 : } else {
150 : // we want an empty vector for the compression step (see below code)
151 26 : GRB_TRY (GrB_Vector_new (&parent_cpy, GrB_UINT64, n)) ;
152 : }
153 :
154 50 : if (!preserve_mapping) {
155 : /*
156 : new code:
157 : - identify preserved nodes (GrB_select to parent_cpy)
158 : - unpack to get indices of preserved nodes
159 : - build ramp vector
160 : - pack back into parent_cpy with ramp as values, preserved node indices as indices (performs compression)
161 : - GrB_extract into parent_cpy from parent_cpy with row indices as values from original parent
162 : - This fills in the new parents for discarded nodes
163 : */
164 :
165 26 : GRB_TRY (GrB_IndexUnaryOp_new (&VALUEEQ_ROWINDEX_UINT64, F_INDEX_UNARY(valueeq_index_func), GrB_BOOL, GrB_UINT64, GrB_UINT64)) ;
166 :
167 : // identify preserved nodes
168 26 : GRB_TRY (GrB_select (parent_cpy, NULL, NULL, VALUEEQ_ROWINDEX_UINT64, parent, 0, NULL)) ;
169 26 : GRB_TRY (GrB_free (&VALUEEQ_ROWINDEX_UINT64)) ;
170 :
171 : // get indices of preserved nodes
172 26 : GRB_TRY (GxB_Vector_unpack_CSC (
173 : parent_cpy,
174 : &preserved_indices,
175 : (void**) &preserved_values,
176 : &preserved_indices_size,
177 : &preserved_values_size,
178 : NULL,
179 : &num_preserved,
180 : &is_jumbled,
181 : NULL
182 : )) ;
183 :
184 26 : LG_TRY (LAGraph_Free ((void**)(&preserved_values), msg)) ;
185 :
186 : // build ramp vector
187 26 : LG_TRY (LAGraph_Malloc ((void**) &ramp, num_preserved, sizeof(uint64_t), msg)) ;
188 :
189 : int64_t i;
190 : #pragma omp parallel for
191 3125 : for (i = 0 ; i < num_preserved ; i++) {
192 3099 : ramp [i] = i ;
193 : }
194 :
195 26 : if (inv_newlabels != NULL) {
196 24 : GRB_TRY (GrB_Vector_new (inv_newlabels, GrB_UINT64, num_preserved)) ;
197 24 : GRB_TRY (GrB_Vector_build (*inv_newlabels, ramp, preserved_indices, num_preserved, NULL)) ;
198 : }
199 :
200 : // pack back into parent_cpy (parent_cpy will now store the new labels of preserved nodes)
201 26 : GRB_TRY (GxB_Vector_pack_CSC (
202 : parent_cpy,
203 : &preserved_indices,
204 : (void**) &ramp,
205 : num_preserved * sizeof(GrB_Index),
206 : num_preserved * sizeof(uint64_t),
207 : false,
208 : num_preserved,
209 : is_jumbled,
210 : NULL
211 : )) ;
212 :
213 26 : if (newlabels != NULL) {
214 25 : GRB_TRY (GrB_Vector_dup (newlabels, parent_cpy)) ;
215 : }
216 :
217 26 : LG_TRY (LAGraph_Malloc ((void**) &original_indices, n, sizeof(GrB_Index), msg)) ;
218 26 : LG_TRY (LAGraph_Malloc ((void**) &original_values, n, sizeof(uint64_t), msg)) ;
219 :
220 26 : GRB_TRY (GrB_Vector_extractTuples (original_indices, original_values, &n, parent)) ;
221 :
222 : // fill in entries for discarded nodes
223 26 : GRB_TRY (GrB_Vector_extract (parent_cpy, NULL, NULL, parent_cpy, original_values, n, NULL)) ;
224 :
225 26 : GRB_TRY (GrB_Matrix_new (&S, S_type, num_preserved, n)) ;
226 :
227 : } else {
228 : // result dim: n by n
229 24 : GRB_TRY (GrB_Matrix_new (&S, S_type, n, n)) ;
230 : // newlabels is the identity map, signified by null return values
231 24 : if (newlabels != NULL) {
232 24 : (*newlabels) = NULL ;
233 : }
234 24 : if (inv_newlabels != NULL) {
235 24 : (*inv_newlabels) = NULL ;
236 : }
237 : }
238 :
239 50 : GRB_TRY (GxB_Vector_unpack_CSC (parent_cpy, &S_cols, (void**) &S_rows, &S_cols_size, &S_rows_size, NULL, &nvals, NULL, NULL)) ;
240 50 : GRB_TRY (GrB_Scalar_new (&one, S_type)) ;
241 50 : GRB_TRY (GrB_Scalar_setElement (one, 1)) ;
242 :
243 50 : GRB_TRY (GxB_Matrix_build_Scalar (S, S_rows, S_cols, one, nvals)) ;
244 :
245 50 : (*result) = S ;
246 :
247 50 : LG_FREE_WORK ;
248 50 : return (GrB_SUCCESS) ;
249 : }
250 : #endif
251 :
252 :
253 : #undef LG_FREE_ALL
254 : #undef LG_FREE_WORK
255 :
256 : #define LG_FREE_WORK \
257 : { \
258 : GrB_free(&E) ; \
259 : GrB_free(&S) ; \
260 : GrB_free(&matched_edges) ; \
261 : GrB_free(&E_t) ; \
262 : GrB_free(&S_t) ; \
263 : GrB_free(&edge_parent) ; \
264 : GrB_free(&node_parent) ; \
265 : GrB_free(&full) ; \
266 : LAGraph_Delete(&G_cpy, msg) ; \
267 : }
268 :
269 : #define LG_FREE_ALL \
270 : { \
271 : LG_FREE_WORK ; \
272 : }
273 :
274 : #ifdef burble
275 : #define CHKPT(msg){ printf("*** [CHKPT] *** %s\n", msg) ; }
276 : #else
277 : #define CHKPT(msg){}
278 : #endif
279 :
280 : #define OPTIMIZE_PUSH_PULL
281 :
282 53 : int LAGraph_Coarsen_Matching
283 : (
284 : // outputs:
285 : GrB_Matrix *coarsened, // coarsened adjacency
286 : GrB_Vector *parent_result, // refer to comments at top of file
287 : GrB_Vector *newlabel_result, // refer to comments at top of file
288 : GrB_Vector *inv_newlabel_result, // refer to comments at top of file
289 :
290 : // inputs:
291 : LAGraph_Graph G, // input graph
292 : LAGraph_Matching_kind matching_type, // how to perform the coarsening
293 : bool preserve_mapping, // preserve original namespace of nodes
294 : bool combine_weights, // whether to sum edge weights or just keep the pattern
295 : uint64_t seed, // seed used for matching
296 : char *msg
297 : )
298 : {
299 : #if LAGRAPH_SUITESPARSE
300 :
301 53 : LG_CLEAR_MSG ;
302 :
303 53 : LAGraph_Graph G_cpy = NULL ; // used for the IncidenceMatrix function
304 53 : GrB_Matrix C = NULL ; // resulting adjacency matrix (used for output)
305 53 : GrB_Matrix E = NULL ; // incidence matrix
306 53 : GrB_Matrix E_t = NULL ; // transpose of incidence
307 53 : GrB_Matrix S = NULL ; // S matrix (S[i][j] -> node j maps to node i in coarsened graph)
308 53 : GrB_Matrix S_t = NULL ; // transpose of S
309 53 : GrB_Vector matched_edges = NULL ; // result of maximal matching
310 53 : GrB_Vector edge_parent = NULL ; // points to parent (representative) node for each edge
311 53 : GrB_Vector node_parent = NULL ; // points to parent (representative) node for each node
312 53 : GrB_Vector full = NULL ; // full vector
313 :
314 : GrB_Index nvals, nrows ;
315 : GrB_Type A_type ;
316 :
317 : // check properties (no self-loops, undirected
318 53 : LG_ASSERT_MSG (G->nself_edges == 0, LAGRAPH_NO_SELF_EDGES_ALLOWED, "G->nself_edges must be zero") ;
319 :
320 52 : LG_ASSERT (coarsened != NULL, GrB_NULL_POINTER) ;
321 :
322 : //------------------------------------------------------------------------------
323 : // check input graph, build local adjacency matrix to use for coarsening
324 : //------------------------------------------------------------------------------
325 :
326 51 : if (G->kind == LAGraph_ADJACENCY_UNDIRECTED)
327 : {
328 : char typename[LAGRAPH_MAX_NAME_LEN] ;
329 : GrB_Type type ;
330 50 : LG_TRY (LAGraph_Matrix_TypeName (typename, G->A, msg)) ;
331 50 : LG_TRY (LAGraph_TypeFromName (&type, typename, msg)) ;
332 :
333 50 : if ((type == GrB_FP64) || (type == GrB_INT64 || type == GrB_UINT64)) {
334 : // output will keep the same type as input
335 34 : GRB_TRY (GrB_Matrix_dup (&C, G->A)) ;
336 34 : A_type = type ;
337 : } else {
338 : // output will become int64/fp64
339 : // reasoning: want to prevent overflow from combining edges and accomodate negative edge weights
340 : #ifdef dbg
341 : printf("Rebuilding with GrB_INT64/FP64, orig type was %s\n", typename);
342 : #endif
343 :
344 16 : bool is_float = (type == GrB_FP32) ;
345 16 : GRB_TRY (GrB_Matrix_nrows (&nrows, G->A)) ;
346 16 : A_type = (is_float ? GrB_FP64 : GrB_INT64) ;
347 16 : GRB_TRY (GrB_Matrix_new (&C, A_type, nrows, nrows)) ;
348 16 : GRB_TRY (GrB_assign (C, NULL, NULL, G->A, GrB_ALL, nrows, GrB_ALL, nrows, NULL)) ;
349 : }
350 : }
351 : else
352 : {
353 : // G is not undirected
354 1 : LG_ASSERT_MSG (false, LAGRAPH_INVALID_GRAPH, "G must be undirected") ;
355 : }
356 : CHKPT("Done with building C");
357 :
358 : // make new LAGraph_Graph to use for LAGraph_IncidenceMatrix and for useful functions (delete self-edges)
359 50 : LG_TRY (LAGraph_New (&G_cpy, &C, LAGraph_ADJACENCY_UNDIRECTED, msg)) ;
360 : ASSERT (C == NULL) ;
361 50 : LG_TRY (LAGraph_Cached_NSelfEdges (G_cpy, msg)) ;
362 :
363 : GrB_Index num_nodes ;
364 : GrB_Index num_edges ;
365 :
366 50 : GRB_TRY (GrB_Matrix_nrows (&num_nodes, G_cpy->A)) ;
367 50 : GRB_TRY (GrB_Matrix_nvals (&num_edges, G_cpy->A)) ;
368 50 : num_edges /= 2 ; // since undirected
369 :
370 : CHKPT("Done building G_cpy");
371 :
372 50 : GRB_TRY (GrB_Matrix_new (&E_t, A_type, num_edges, num_nodes)) ;
373 50 : GRB_TRY (GrB_Vector_new (&edge_parent, GrB_UINT64, num_edges)) ;
374 :
375 50 : GRB_TRY (GrB_Vector_new (&node_parent, GrB_UINT64, num_nodes)) ;
376 :
377 50 : GRB_TRY (GrB_Vector_new (&full, GrB_BOOL, num_nodes)) ;
378 50 : GRB_TRY (GrB_assign (full, NULL, NULL, true, GrB_ALL, num_nodes, NULL)) ;
379 :
380 : // for push/pull optimization
381 50 : double sparsity_thresh =
382 : #ifdef OPTIMIZE_PUSH_PULL
383 : 0.04 ;
384 : #else
385 : 1.0 ;
386 : #endif
387 :
388 50 : GrB_Index curr_level = 0 ;
389 : CHKPT("Starting coarsening step");
390 :
391 : //------------------------------------------------------------------------------
392 : // coarsening step
393 : //------------------------------------------------------------------------------
394 :
395 : // get incidence matrix
396 50 : LG_TRY (LAGraph_Incidence_Matrix (&E, G_cpy, msg)) ;
397 : CHKPT("Done with LAGraph_IncidenceMatrix");
398 :
399 50 : GRB_TRY (GrB_transpose (E_t, NULL, NULL, E, NULL)) ;
400 : // set to row major incase Incidence_Matrix gave col_major
401 50 : GRB_TRY (GrB_set(E, GrB_ROWMAJOR, GrB_STORAGE_ORIENTATION_HINT)) ;
402 : CHKPT("Starting maximal matching");
403 : // run maximal matching
404 50 : LG_TRY (LAGraph_MaximalMatching (&matched_edges, E, E_t, matching_type, seed, msg)) ;
405 : CHKPT("Done with maximal matching");
406 :
407 : // make edge_parent
408 : // want to do E_t * full and get the first entry for each edge (mask output with matched_edges)
409 50 : GRB_TRY (GrB_mxv (edge_parent, matched_edges, NULL, GxB_MIN_SECONDI_INT64, E_t, full, GrB_DESC_RS)) ;
410 :
411 : #ifdef dbg
412 : printf("Printing edge_parent for level (%lld)\n", curr_level) ;
413 : LG_TRY (LAGraph_Vector_Print (edge_parent, LAGraph_COMPLETE, stdout, msg)) ;
414 : printf("Printing E for level (%lld)\n", curr_level) ;
415 : LG_TRY (LAGraph_Matrix_Print (E, LAGraph_COMPLETE, stdout, msg)) ;
416 : #endif
417 : // now, we have edge_parent (each edge points to its parent node)
418 : // can do E * edge_parent with min_second to get node_parent
419 : GrB_Index num_matched ;
420 50 : GRB_TRY (GrB_Vector_nvals (&num_matched, edge_parent)) ;
421 :
422 50 : if (num_matched > sparsity_thresh * num_edges) {
423 24 : GRB_TRY (LG_SET_FORMAT_HINT (edge_parent, LG_BITMAP)) ;
424 24 : GRB_TRY (GrB_mxv (node_parent, NULL, NULL, GrB_MIN_SECOND_SEMIRING_UINT64, E, edge_parent, NULL)) ;
425 : } else {
426 26 : GRB_TRY (LG_SET_FORMAT_HINT (edge_parent, LG_SPARSE)) ;
427 26 : GRB_TRY (GrB_vxm (node_parent, NULL, NULL, GrB_MIN_FIRST_SEMIRING_UINT64, edge_parent, E_t, NULL)) ;
428 : }
429 :
430 : // populate non-existent entries in node_parent with their index
431 : // handles nodes that are not engaged in a matching
432 50 : GrB_apply (node_parent, node_parent, NULL, GrB_ROWINDEX_INT64, full, (uint64_t) 0, GrB_DESC_SC) ;
433 :
434 50 : if (parent_result != NULL) {
435 : // record a deep copy of the current node_parent for the output parent vector
436 48 : GRB_TRY (GrB_Vector_dup (parent_result, node_parent)) ;
437 : }
438 :
439 : #ifdef dbg
440 : printf("Printing node_parent for level (%lld)\n", curr_level) ;
441 : LG_TRY (LAGraph_Vector_Print (node_parent, LAGraph_COMPLETE, stdout, msg)) ;
442 : printf("Printing matched edges for level (%lld)\n", curr_level) ;
443 : LG_TRY (LAGraph_Vector_Print (matched_edges, LAGraph_COMPLETE, stdout, msg)) ;
444 : #endif
445 :
446 : // build the S matrix
447 50 : LG_TRY (LAGraph_Parent_to_S (
448 : &S,
449 : newlabel_result,
450 : inv_newlabel_result,
451 : node_parent,
452 : preserve_mapping,
453 : A_type,
454 : msg
455 : )) ;
456 :
457 : #ifdef dbg
458 : printf("Printing S for level (%lld)\n", curr_level) ;
459 : LG_TRY (LAGraph_Matrix_Print (S, LAGraph_COMPLETE, stdout, msg)) ;
460 : printf("Printing C for level (%lld)\n", curr_level) ;
461 : LG_TRY (LAGraph_Matrix_Print (G_cpy->A, LAGraph_COMPLETE, stdout, msg)) ;
462 : #endif
463 :
464 : GrB_Index S_nrows, S_ncols ;
465 :
466 : // create S_t now that we know the dimensions of S
467 50 : GRB_TRY (GrB_Matrix_nrows (&S_nrows, S)) ;
468 50 : GRB_TRY (GrB_Matrix_ncols (&S_ncols, S)) ;
469 :
470 50 : GRB_TRY (GrB_Matrix_new (&S_t, A_type, S_ncols, S_nrows)) ;
471 :
472 50 : GRB_TRY (GrB_transpose (S_t, NULL, NULL, S, NULL)) ;
473 :
474 : // choose right semiring based on combine_weights and type of adjacency matrix
475 50 : GrB_Semiring combine_semiring = (A_type == GrB_FP64) ? GrB_PLUS_TIMES_SEMIRING_FP64 : GrB_PLUS_TIMES_SEMIRING_INT64 ;
476 50 : GrB_Semiring semiring = combine_weights ? combine_semiring : LAGraph_any_one_bool ;
477 :
478 50 : GRB_TRY (GrB_mxm (S, NULL, NULL, semiring, S, G_cpy->A, NULL)) ;
479 :
480 : #ifdef dbg
481 : printf("Printing S * C for level (%lld)\n", curr_level) ;
482 : LG_TRY (LAGraph_Matrix_Print (S, LAGraph_COMPLETE, stdout, msg)) ;
483 : #endif
484 :
485 50 : if (!preserve_mapping) {
486 : // re-instantiate adjacency matrix with new dimensions
487 26 : GRB_TRY (GrB_free (&G_cpy->A)) ;
488 26 : GRB_TRY (GrB_Matrix_new (&(G_cpy->A), A_type, S_nrows, S_nrows)) ;
489 : }
490 50 : GRB_TRY (GrB_mxm (G_cpy->A, NULL, NULL, semiring, S, S_t, NULL)) ;
491 :
492 : // make nself_edges unknown for delete self edges to work
493 50 : G_cpy->nself_edges = LAGRAPH_UNKNOWN ;
494 : // parent nodes for matched edges will form self-edges; need to delete
495 50 : LG_TRY (LAGraph_DeleteSelfEdges (G_cpy, msg)) ;
496 :
497 : //------------------------------------------------------------------------------
498 : // coarsening step done
499 : //------------------------------------------------------------------------------
500 :
501 50 : (*coarsened) = G_cpy->A ;
502 50 : G_cpy->A = NULL ;
503 :
504 50 : LG_FREE_WORK ;
505 50 : return (GrB_SUCCESS) ;
506 : #else
507 : return (GrB_NOT_IMPLEMENTED) ;
508 : #endif
509 : }
510 :
|
