Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LAGraph_MaximalIndependentSet: maximal independent set, with constraints
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 : // Modified from the GraphBLAS C API Specification, by Aydin Buluc, Timothy
15 : // Mattson, Scott McMillan, Jose' Moreira, Carl Yang. Based on "GraphBLAS
16 : // Mathematics" by Jeremy Kepner. Revised by Timothy A. Davis, Texas A&M
17 : // University.
18 :
19 : //------------------------------------------------------------------------------
20 :
21 : #define LG_FREE_WORK \
22 : { \
23 : GrB_free (&neighbor_max) ; \
24 : GrB_free (&new_members) ; \
25 : GrB_free (&new_neighbors) ; \
26 : GrB_free (&candidates) ; \
27 : GrB_free (&empty) ; \
28 : GrB_free (&Seed) ; \
29 : GrB_free (&score) ; \
30 : GrB_free (°ree) ; \
31 : }
32 :
33 : #define LG_FREE_ALL \
34 : { \
35 : LG_FREE_WORK ; \
36 : GrB_free (&iset) ; \
37 : }
38 :
39 : #include "LG_internal.h"
40 : #include "LAGraphX.h"
41 :
42 : // A variant of Luby's randomized algorithm [Luby 1985].
43 :
44 : // Given a numeric n x n adjacency matrix A of an unweighted and undirected
45 : // graph (where the value true represents an edge), compute a maximal set of
46 : // independent nodes and return it in a boolean n-vector, mis where
47 : // mis[i] == true implies node i is a member of the set.
48 :
49 : // The graph cannot have any self edges, and it must be symmetric. Self-edges
50 : // (diagonal entries) will cause the method to stall, and thus G->nself_edges
51 : // must be zero on input. G->out_degree must be present on input. It must not
52 : // contain any explicit zeros (this is handled by LAGraph_Cached_OutDegree).
53 :
54 : // Singletons require special treatment. Since they have no neighbors, their
55 : // score is never greater than the max of their neighbors, so they never get
56 : // selected and cause the method to stall. To avoid this case they are removed
57 : // from the candidate set at the begining, and added to the independent set.
58 :
59 : // TODO: rename LAGr_MaximalIndependentSet (this is expert)
60 : // TODO: add a basic method
61 : // vanilla OK: no GxB used
62 :
63 371 : int LAGraph_MaximalIndependentSet // maximal independent set
64 : (
65 : // outputs:
66 : GrB_Vector *mis, // mis(i) = true if i is in the set
67 : // inputs:
68 : LAGraph_Graph G, // input graph
69 : uint64_t seed, // random number seed
70 : GrB_Vector ignore_node, // if NULL, no nodes are ignored. Otherwise
71 : // ignore_node(i) = true if node i is to be
72 : // ignored, and not treated as a candidate
73 : // added to maximal independent set.
74 : char *msg
75 : )
76 : {
77 :
78 : //--------------------------------------------------------------------------
79 : // check inputs
80 : //--------------------------------------------------------------------------
81 :
82 371 : LG_CLEAR_MSG ;
83 371 : GrB_Vector iset = NULL ; // independent set (output vector)
84 371 : GrB_Vector score = NULL ; // random score for each node
85 371 : GrB_Vector neighbor_max = NULL ; // value of max neighbor score
86 371 : GrB_Vector new_members = NULL ; // set of new members to add to iset
87 371 : GrB_Vector new_neighbors = NULL ; // new neighbors to new iset members
88 371 : GrB_Vector candidates = NULL ; // candidate nodes
89 371 : GrB_Vector empty = NULL ; // an empty vector
90 371 : GrB_Vector Seed = NULL ; // random number seed vector
91 371 : GrB_Vector degree = NULL ; // (float) G->out_degree
92 : GrB_Matrix A ; // G->A, the adjacency matrix
93 : GrB_Index n ; // # of nodes
94 :
95 371 : LG_TRY (LAGraph_CheckGraph (G, msg)) ;
96 371 : LG_ASSERT (mis != NULL, GrB_NULL_POINTER) ;
97 :
98 371 : if (G->kind == LAGraph_ADJACENCY_UNDIRECTED ||
99 48 : (G->kind == LAGraph_ADJACENCY_DIRECTED &&
100 48 : G->is_symmetric_structure == LAGraph_TRUE))
101 : {
102 : // the structure of A is known to be symmetric
103 355 : A = G->A ;
104 : }
105 : else
106 : {
107 : // A is not known to be symmetric
108 16 : LG_ASSERT_MSG (false, -105, "G->A must be symmetric") ;
109 : }
110 :
111 355 : LG_ASSERT_MSG (G->out_degree != NULL, -106,
112 : "G->out_degree must be defined") ;
113 355 : LG_ASSERT_MSG (G->nself_edges == 0, -107, "G->nself_edges must be zero") ;
114 :
115 : //--------------------------------------------------------------------------
116 : // initializations
117 : //--------------------------------------------------------------------------
118 :
119 355 : GRB_TRY (GrB_Matrix_nrows (&n, A)) ;
120 355 : GRB_TRY (GrB_Vector_new (&neighbor_max, GrB_FP32, n)) ;
121 355 : GRB_TRY (GrB_Vector_new (°ree, GrB_FP32, n)) ;
122 355 : GRB_TRY (GrB_Vector_new (&new_members, GrB_BOOL, n)) ;
123 355 : GRB_TRY (GrB_Vector_new (&new_neighbors, GrB_BOOL, n)) ;
124 355 : GRB_TRY (GrB_Vector_new (&candidates, GrB_BOOL, n)) ;
125 355 : GRB_TRY (GrB_Vector_new (&empty, GrB_BOOL, n)) ;
126 355 : GRB_TRY (GrB_Vector_new (&Seed, GrB_UINT64, n)) ;
127 355 : GRB_TRY (GrB_Vector_new (&score, GrB_FP32, n)) ;
128 355 : GRB_TRY (GrB_Vector_new (&iset, GrB_BOOL, n)) ;
129 :
130 : // degree = (float) G->out_degree
131 355 : GRB_TRY (GrB_assign (degree, NULL, NULL, G->out_degree, GrB_ALL, n, NULL)) ;
132 :
133 : //--------------------------------------------------------------------------
134 : // remove singletons (nodes of degree zero) and handle ignore_node
135 : //--------------------------------------------------------------------------
136 :
137 355 : GrB_Index nonsingletons = 0 ;
138 355 : GRB_TRY (GrB_Vector_nvals (&nonsingletons, degree)) ;
139 355 : if (nonsingletons == n)
140 : {
141 163 : if (ignore_node == NULL)
142 : {
143 : // all nodes have degree 1 or more; all nodes are candidates
144 : // candidates (0:n-1) = true
145 80 : GRB_TRY (GrB_assign (candidates, NULL, NULL, (bool) true, GrB_ALL,
146 : n, NULL)) ;
147 : // Seed vector starts out dense
148 : // Seed (0:n-1) = 0
149 80 : GRB_TRY (GrB_assign (Seed, NULL, NULL, 0, GrB_ALL, n, NULL)) ;
150 : }
151 : else
152 : {
153 : // all nodes have degree 1 or more, but some nodes are to be
154 : // ignored. Use ignore_node as a valued mask.
155 : // candidates<!ignore_node> = true
156 83 : GRB_TRY (GrB_assign (candidates, ignore_node, NULL, (bool) true,
157 : GrB_ALL, n, GrB_DESC_C)) ;
158 : // Seed vector starts out sparse
159 : // Seed{candidates} = 0
160 83 : GRB_TRY (GrB_assign (Seed, candidates, NULL, 0, GrB_ALL, n,
161 : GrB_DESC_S)) ;
162 : }
163 : }
164 : else
165 : {
166 : // one or more singleton is present.
167 : // candidates{degree} = 1
168 192 : GRB_TRY (GrB_assign (candidates, degree, NULL, (bool) true,
169 : GrB_ALL, n, GrB_DESC_S)) ;
170 : // add all singletons to iset
171 : // iset{!degree} = 1
172 192 : GRB_TRY (GrB_assign (iset, degree, NULL, (bool) true, GrB_ALL, n,
173 : GrB_DESC_SC)) ;
174 192 : if (ignore_node != NULL)
175 : {
176 : // one or more singletons are present, and some nodes are to be
177 : // ignored. The candidates are all those nodes with degree > 0
178 : // for which ignore_node(i) is false (or not present). Delete
179 : // any candidate i for which ignore_node(i) is true. Use
180 : // ignore_node as a valued mask.
181 : // candidates<ignore_node> = empty
182 80 : GRB_TRY (GrB_assign (candidates, ignore_node, NULL, empty,
183 : GrB_ALL, n, NULL)) ;
184 : // Delete any ignored nodes from iset
185 : // iset<ignore_node> = empty
186 80 : GRB_TRY (GrB_assign (iset, ignore_node, NULL, empty,
187 : GrB_ALL, n, NULL)) ;
188 : }
189 : // Seed vector starts out sparse
190 : // Seed{candidates} = 0
191 192 : GRB_TRY (GrB_assign (Seed, candidates, NULL, 0, GrB_ALL, n,
192 : GrB_DESC_S)) ;
193 : }
194 :
195 : // create the random number seeds
196 355 : LG_TRY (LAGraph_Random_Seed (Seed, seed, msg)) ;
197 :
198 : //--------------------------------------------------------------------------
199 : // iterate while there are candidates to check
200 : //--------------------------------------------------------------------------
201 :
202 355 : int nstall = 0 ;
203 : GrB_Index ncandidates ;
204 355 : GRB_TRY (GrB_Vector_nvals (&ncandidates, candidates)) ;
205 355 : GrB_Index last_ncandidates = ncandidates ;
206 355 : GrB_Index n1 = (GrB_Index) (0.04 * (double) n) ;
207 355 : GrB_Index n2 = (GrB_Index) (0.10 * (double) n) ;
208 :
209 1344 : while (ncandidates > 0)
210 : {
211 : // compute the score for each node; scale the Seed by degree
212 : // score = (float) Seed
213 1161 : GRB_TRY (GrB_assign (score, NULL, NULL, Seed, GrB_ALL, n, NULL)) ;
214 : // score = score / degree
215 1148 : GRB_TRY (GrB_eWiseMult (score, NULL, NULL, GrB_DIV_FP32, score, degree,
216 : NULL)) ;
217 :
218 : // compute the max score of all candidate neighbors (only candidates
219 : // have a score, so non-candidate neighbors are excluded)
220 : // neighbor_max{candidates,replace} = score * A
221 1148 : GRB_TRY (GrB_Vector_nvals (&ncandidates, candidates)) ;
222 1148 : if (ncandidates < n1)
223 : {
224 : // push
225 : // neighbor_max'{candidates,replace} = score' * A
226 113 : GRB_TRY (GrB_vxm (neighbor_max, candidates, NULL,
227 : GrB_MAX_FIRST_SEMIRING_FP32, score, A, GrB_DESC_RS)) ;
228 : }
229 : else
230 : {
231 : // pull
232 : // neighbor_max{candidates,replace} = A * score
233 1035 : GRB_TRY (GrB_mxv (neighbor_max, candidates, NULL,
234 : GrB_MAX_SECOND_SEMIRING_FP32, A, score, GrB_DESC_RS)) ;
235 : }
236 :
237 : // select node if its score is > than all its active neighbors
238 : // new_members = (score > neighbor_max) using set union so that nodes
239 : // with no neighbors fall through to the output, as true (since no
240 : // score is equal to zero).
241 1148 : GRB_TRY (GrB_eWiseAdd (new_members, NULL, NULL, GrB_GT_FP32,
242 : score, neighbor_max, NULL)) ;
243 :
244 : // drop explicit zeros from new_members
245 : // in particular, this replaces all 0s with empty
246 1148 : GRB_TRY (GrB_select (new_members, NULL, NULL, GrB_VALUEEQ_BOOL,
247 : new_members, (bool) true, NULL)) ;
248 :
249 : // add new members to independent set
250 : // iset{new_members} = true
251 1148 : GRB_TRY (GrB_assign (iset, new_members, NULL, (bool) true,
252 : GrB_ALL, n, GrB_DESC_S)) ;
253 :
254 : // remove new members from set of candidates
255 : // candidates{new_members} = empty
256 1148 : GRB_TRY (GrB_assign (candidates, new_members, NULL, empty,
257 : GrB_ALL, n, GrB_DESC_S)) ;
258 :
259 : // early exit if candidates is empty
260 1148 : GRB_TRY (GrB_Vector_nvals (&ncandidates, candidates)) ;
261 1148 : if (ncandidates == 0) { break ; }
262 :
263 : // Neighbors of new members can also be removed from candidates
264 : // new_neighbors{candidates,replace} = new_members * A
265 : GrB_Index n_new_members ;
266 1002 : GRB_TRY (GrB_Vector_nvals (&n_new_members, new_members)) ;
267 1002 : if (n_new_members < n2)
268 : {
269 : // push
270 : // new_neighbors{candidates,replace} = new_members' * A
271 398 : GRB_TRY (GrB_vxm (new_neighbors, candidates, NULL,
272 : LAGraph_any_one_bool, new_members, A, GrB_DESC_RS)) ;
273 : }
274 : else
275 : {
276 : // pull
277 : // new_neighbors{candidates,replace} = A * new_members
278 604 : GRB_TRY (GrB_mxv (new_neighbors, candidates, NULL,
279 : LAGraph_any_one_bool, A, new_members, GrB_DESC_RS)) ;
280 : }
281 :
282 : // remove new neighbors of new members from set of candidates
283 : // candidates{new_neighbors} = empty
284 1002 : GRB_TRY (GrB_assign (candidates, new_neighbors, NULL, empty,
285 : GrB_ALL, n, GrB_DESC_S)) ;
286 :
287 : // sparsify the random number seeds (just keep it for each candidate)
288 : // Seed{candidates,replace} = Seed
289 1002 : GRB_TRY (GrB_assign (Seed, candidates, NULL, Seed, GrB_ALL, n,
290 : GrB_DESC_RS)) ;
291 :
292 : // Check for stall (can only occur if the matrix has self-edges, or in
293 : // the exceedingly rare case that 2 nodes have the exact same score).
294 : // If the method happens to stall, with no nodes selected because
295 : // the scores happen to tie, try again with another random score.
296 1002 : GRB_TRY (GrB_Vector_nvals (&ncandidates, candidates)) ;
297 1002 : if (last_ncandidates == ncandidates)
298 : {
299 : // This case is nearly untestable since it can almost never occur.
300 429 : nstall++ ;
301 : // terminate if the method has stalled too many times
302 429 : LG_ASSERT_MSG (nstall <= 32, LAGRAPH_CONVERGENCE_FAILURE,
303 : "method has stalled") ;
304 : // recreate the random number seeds with a new starting seed
305 416 : LG_TRY (LAGraph_Random_Seed (Seed, seed + nstall, msg)) ;
306 : }
307 989 : last_ncandidates = ncandidates ;
308 :
309 : // get the next random Seed vector
310 989 : LG_TRY (LAGraph_Random_Next (Seed, msg)) ;
311 : }
312 :
313 : //--------------------------------------------------------------------------
314 : // free workspace and return result
315 : //--------------------------------------------------------------------------
316 :
317 342 : GRB_TRY (GrB_wait (iset, GrB_MATERIALIZE)) ;
318 342 : (*mis) = iset ;
319 342 : LG_FREE_WORK ;
320 342 : return (GrB_SUCCESS) ;
321 : }
|
