Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LAGraph_cc_lacc.c
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 Scott McMillan, SEI, Carnegie Mellon University
15 :
16 : //------------------------------------------------------------------------------
17 :
18 : /**
19 : * Code is based on the algorithm described in the following paper Azad, Buluc;
20 : * LACC: a linear-algebraic algorithm for finding connected components in
21 : * distributed memory (IPDPS 2019)
22 : **/
23 :
24 : #define LG_FREE_ALL \
25 : { \
26 : free(I); \
27 : free(V); \
28 : GrB_free (&S2) ; \
29 : GrB_free (&stars); \
30 : GrB_free (&mask); \
31 : GrB_free (&parents); \
32 : GrB_free (&gp); \
33 : GrB_free (&mnp); \
34 : GrB_free (&hookMNP); \
35 : GrB_free (&hookP); \
36 : GrB_free (&pNonstars); \
37 : GrB_free (&tmp); \
38 : GrB_free (&nsgp); \
39 : }
40 :
41 : #include "LG_internal.h"
42 : #include <LAGraph.h>
43 : #include <LAGraphX.h>
44 :
45 : //****************************************************************************
46 : // mask = NULL, accumulator = GrB_MIN_UINT64, descriptor = NULL
47 188 : static GrB_Info Reduce_assign (GrB_Vector w,
48 : GrB_Vector src,
49 : GrB_Index *index,
50 : GrB_Index nLocs)
51 : {
52 : GrB_Index nw, ns;
53 188 : GrB_Vector_nvals(&nw, w);
54 188 : GrB_Vector_nvals(&ns, src);
55 188 : GrB_Index *mem = (GrB_Index*) malloc(sizeof(GrB_Index) * nw * 3);
56 188 : GrB_Index *ind = mem, *sval = mem + nw, *wval = sval + nw;
57 188 : GrB_Vector_extractTuples(ind, wval, &nw, w);
58 188 : GrB_Vector_extractTuples(ind, sval, &ns, src);
59 10346 : for (GrB_Index i = 0; i < nLocs; i++)
60 10158 : if (sval[i] < wval[index[i]])
61 9486 : wval[index[i]] = sval[i];
62 188 : GrB_Vector_clear(w);
63 188 : GrB_Vector_build(w, ind, wval, nw, GrB_PLUS_UINT64);
64 188 : free(mem);
65 188 : return GrB_SUCCESS;
66 : }
67 :
68 : //****************************************************************************
69 36 : int LAGraph_cc_lacc
70 : (
71 : GrB_Vector *result, // output: array of component identifiers
72 : GrB_Matrix A, // input matrix
73 : bool sanitize, // if true, ensure A is symmetric
74 : char *msg
75 : )
76 : {
77 : //--------------------------------------------------------------------------
78 : // check inputs
79 : //--------------------------------------------------------------------------
80 :
81 36 : LG_CLEAR_MSG ;
82 36 : if (result == NULL)
83 : {
84 12 : return (GrB_NULL_POINTER) ;
85 : }
86 :
87 : GrB_Info info;
88 :
89 24 : GrB_Vector stars = NULL, mask = NULL;
90 24 : GrB_Vector parents = NULL, gp = NULL, mnp = NULL;
91 24 : GrB_Vector hookMNP = NULL, hookP = NULL;
92 24 : GrB_Vector tmp = NULL, pNonstars = NULL, nsgp = NULL; // temporary
93 24 : GrB_Index *I = NULL;
94 24 : GrB_Index *V = NULL;
95 24 : GrB_Matrix S = NULL, S2 = NULL ;
96 :
97 : GrB_Index n ;
98 24 : GRB_TRY (GrB_Matrix_nrows (&n, A)) ;
99 : //GrB_Index nnz ;
100 : //GRB_TRY (GrB_Matrix_nvals (&nnz, A)) ;
101 : //printf ("number of nodes: %g\n", (double) n) ;
102 : //printf ("number of edges: %g\n", (double) nnz) ;
103 :
104 24 : if (sanitize)
105 : {
106 12 : GRB_TRY (GrB_Matrix_new (&S2, GrB_BOOL, n, n)) ;
107 12 : GRB_TRY (GrB_eWiseAdd (S2, NULL, NULL, GrB_LOR, A, A, GrB_DESC_T1)) ;
108 12 : S = S2 ;
109 : }
110 : else
111 : {
112 : // Use the input as-is, and assume it is binary and symmetric
113 12 : S = A ;
114 : }
115 :
116 : // vectors
117 24 : GRB_TRY (GrB_Vector_new (&stars, GrB_BOOL, n));
118 24 : GRB_TRY (GrB_Vector_new (&mask, GrB_BOOL, n));
119 24 : GRB_TRY (GrB_Vector_new (&parents, GrB_UINT64, n));
120 24 : GRB_TRY (GrB_Vector_new (&gp, GrB_UINT64, n));
121 24 : GRB_TRY (GrB_Vector_new (&hookMNP, GrB_UINT64, n));
122 24 : GRB_TRY (GrB_Vector_new (&hookP, GrB_UINT64, n));
123 24 : GRB_TRY (GrB_Vector_new (&pNonstars, GrB_UINT64, n));
124 :
125 : // temporary arrays
126 24 : I = malloc(sizeof(GrB_Index) * n);
127 24 : V = malloc(sizeof(GrB_Index) * n);
128 :
129 : // prepare the vectors
130 16284 : for (GrB_Index i = 0 ; i < n ; i++)
131 16260 : I[i] = V[i] = i;
132 24 : GRB_TRY (GrB_Vector_build (parents, I, V, n, GrB_PLUS_UINT64));
133 24 : GRB_TRY (GrB_Vector_dup (&mnp, parents));
134 24 : GRB_TRY (GrB_assign (stars, 0, 0, true, GrB_ALL, 0, 0)) ;
135 :
136 : // main computation
137 : GrB_Index nHooks, nStars, nNonstars;
138 : while (true) {
139 : // ---------------------------------------------------------
140 : // CondHook(A, parents, stars);
141 : // ---------------------------------------------------------
142 94 : GRB_TRY (GrB_mxv (mnp, 0, 0, GrB_MIN_SECOND_SEMIRING_UINT64,
143 : S, parents, 0));
144 94 : GRB_TRY (GrB_Vector_clear (mask));
145 94 : GRB_TRY (GrB_eWiseMult(mask, stars, 0, GrB_LT_UINT64, mnp, parents, 0));
146 94 : GRB_TRY (GrB_assign (hookMNP, mask, 0, mnp, GrB_ALL, n, 0));
147 94 : GRB_TRY (GrB_eWiseMult (hookP, 0, 0, GrB_SECOND_UINT64, hookMNP, parents, 0));
148 94 : GRB_TRY (GrB_Vector_clear (mnp));
149 94 : GRB_TRY (GrB_Vector_nvals (&nHooks, hookP));
150 94 : GRB_TRY (GrB_Vector_extractTuples (I, V, &nHooks, hookP));
151 94 : GRB_TRY (GrB_Vector_new (&tmp, GrB_UINT64, nHooks));
152 94 : GRB_TRY (GrB_extract (tmp, 0, 0, hookMNP, I, nHooks, 0));
153 94 : LG_TRY (Reduce_assign (parents, tmp, V, nHooks));
154 94 : GRB_TRY (GrB_Vector_clear (tmp));
155 : // modify the stars vector
156 94 : GRB_TRY (GrB_assign (stars, 0, 0, false, V, nHooks, 0));
157 94 : GRB_TRY (GrB_extract (tmp, 0, 0, parents, V, nHooks, 0)); // extract modified parents
158 94 : GRB_TRY (GrB_Vector_extractTuples (I, V, &nHooks, tmp));
159 94 : GRB_TRY (GrB_assign (stars, 0, 0, false, V, nHooks, 0));
160 94 : GRB_TRY (GrB_Vector_extractTuples (I, V, &n, parents));
161 94 : GRB_TRY (GrB_extract (mask, 0, 0, stars, V, n, 0));
162 94 : GRB_TRY (GrB_assign (stars, 0, GrB_LAND, mask, GrB_ALL, 0, 0));
163 : // clean up
164 94 : GRB_TRY (GrB_Vector_clear (hookMNP));
165 94 : GRB_TRY (GrB_Vector_clear (hookP));
166 94 : GRB_TRY (GrB_free (&tmp));
167 : // ---------------------------------------------------------
168 : // UnCondHook(A, parents, stars);
169 : // ---------------------------------------------------------
170 94 : GRB_TRY (GrB_assign (pNonstars, 0, 0, parents, GrB_ALL, 0, 0));
171 94 : GRB_TRY (GrB_assign (pNonstars, stars, 0, n, GrB_ALL, 0, 0));
172 94 : GRB_TRY (GrB_mxv (hookMNP, stars, 0, GrB_MIN_SECOND_SEMIRING_UINT64,
173 : S, pNonstars, 0));
174 : // select the valid elemenets (<n) of hookMNP
175 94 : GRB_TRY (GrB_assign (pNonstars, 0, 0, n, GrB_ALL, 0, 0));
176 94 : GRB_TRY (GrB_eWiseMult (mask, 0, 0, GrB_LT_UINT64, hookMNP, pNonstars, 0));
177 94 : GRB_TRY (GrB_eWiseMult (hookP, mask, 0, GrB_SECOND_UINT64, hookMNP, parents, 0));
178 94 : GRB_TRY (GrB_Vector_nvals (&nHooks, hookP));
179 94 : GRB_TRY (GrB_Vector_extractTuples (I, V, &nHooks, hookP));
180 94 : GRB_TRY (GrB_Vector_new (&tmp, GrB_UINT64, nHooks));
181 94 : GRB_TRY (GrB_extract (tmp, 0, 0, hookMNP, I, nHooks, 0));
182 94 : GRB_TRY (GrB_assign (parents, 0, 0, n, V, nHooks, 0)); // !!
183 94 : LG_TRY (Reduce_assign (parents, tmp, V, nHooks));
184 : // modify the star vector
185 94 : GRB_TRY (GrB_assign (stars, 0, 0, false, V, nHooks, 0));
186 94 : GRB_TRY (GrB_Vector_extractTuples (I, V, &n, parents));
187 94 : GRB_TRY (GrB_extract (mask, 0, 0, stars, V, n, 0));
188 94 : GRB_TRY (GrB_assign (stars, 0, GrB_LAND, mask, GrB_ALL, 0, 0));
189 : // check termination
190 94 : GRB_TRY (GrB_reduce (&nStars, 0, GrB_PLUS_MONOID_UINT64, stars, 0));
191 94 : if (nStars == n) break;
192 : // clean up
193 70 : GRB_TRY (GrB_Vector_clear(hookMNP));
194 70 : GRB_TRY (GrB_Vector_clear(hookP));
195 70 : GRB_TRY (GrB_Vector_clear(pNonstars));
196 70 : GRB_TRY (GrB_free (&tmp));
197 : // ---------------------------------------------------------
198 : // Shortcut(parents);
199 : // ---------------------------------------------------------
200 70 : GRB_TRY (GrB_Vector_extractTuples (I, V, &n, parents));
201 70 : GRB_TRY (GrB_extract (gp, 0, 0, parents, V, n, 0));
202 70 : GRB_TRY (GrB_assign (parents, 0, 0, gp, GrB_ALL, 0, 0));
203 : // ---------------------------------------------------------
204 : // StarCheck(parents, stars);
205 : // ---------------------------------------------------------
206 : // calculate grandparents
207 70 : GRB_TRY (GrB_Vector_extractTuples (I, V, &n, parents));
208 70 : GRB_TRY (GrB_extract (gp, 0, 0, parents, V, n, 0));
209 : // identify vertices whose parent and grandparent are different
210 70 : GRB_TRY (GrB_eWiseMult (mask, 0, 0, GrB_NE_UINT64, gp, parents, 0));
211 70 : GRB_TRY (GrB_Vector_new (&nsgp, GrB_UINT64, n));
212 70 : GRB_TRY (GrB_assign (nsgp, mask, 0, gp, GrB_ALL, 0, 0));
213 : // extract indices and values for assign
214 70 : GRB_TRY (GrB_Vector_nvals (&nNonstars, nsgp));
215 70 : GRB_TRY (GrB_Vector_extractTuples (I, V, &nNonstars, nsgp));
216 70 : GRB_TRY (GrB_free (&nsgp));
217 70 : GRB_TRY (GrB_assign (stars, 0, 0, true, GrB_ALL, 0, 0));
218 70 : GRB_TRY (GrB_assign (stars, 0, 0, false, I, nNonstars, 0));
219 70 : GRB_TRY (GrB_assign (stars, 0, 0, false, V, nNonstars, 0));
220 : // extract indices and values for assign
221 70 : GRB_TRY (GrB_Vector_extractTuples (I, V, &n, parents));
222 70 : GRB_TRY (GrB_extract (mask, 0, 0, stars, V, n, 0));
223 70 : GRB_TRY (GrB_assign (stars, 0, GrB_LAND, mask, GrB_ALL, 0, 0));
224 : }
225 24 : *result = parents;
226 24 : parents = NULL ; // return parents (set to NULL so it isn't freed)
227 :
228 24 : LG_FREE_ALL;
229 24 : return GrB_SUCCESS;
230 : }
|
