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 368 : int LAGraph_MaximalIndependentSet // maximal independent set
60 : (
61 : // outputs:
62 : GrB_Vector *mis, // mis(i) = true if i is in the set
63 : // inputs:
64 : LAGraph_Graph G, // input graph
65 : uint64_t seed, // random number seed
66 : GrB_Vector ignore_node, // if NULL, no nodes are ignored. Otherwise
67 : // ignore_node(i) = true if node i is to be
68 : // ignored, and not treated as a candidate
69 : // added to maximal independent set.
70 : char *msg
71 : )
72 : {
73 :
74 : //--------------------------------------------------------------------------
75 : // check inputs
76 : //--------------------------------------------------------------------------
77 :
78 368 : LG_CLEAR_MSG ;
79 368 : GrB_Vector iset = NULL ; // independent set (output vector)
80 368 : GrB_Vector score = NULL ; // random score for each node
81 368 : GrB_Vector neighbor_max = NULL ; // value of max neighbor score
82 368 : GrB_Vector new_members = NULL ; // set of new members to add to iset
83 368 : GrB_Vector new_neighbors = NULL ; // new neighbors to new iset members
84 368 : GrB_Vector candidates = NULL ; // candidate nodes
85 368 : GrB_Vector empty = NULL ; // an empty vector
86 368 : GrB_Vector Seed = NULL ; // random number seed vector
87 368 : GrB_Vector degree = NULL ; // (float) G->out_degree
88 : GrB_Matrix A ; // G->A, the adjacency matrix
89 : GrB_Index n ; // # of nodes
90 :
91 368 : LG_TRY (LAGraph_CheckGraph (G, msg)) ;
92 368 : LG_ASSERT (mis != NULL, GrB_NULL_POINTER) ;
93 :
94 368 : if (G->kind == LAGraph_ADJACENCY_UNDIRECTED ||
95 48 : (G->kind == LAGraph_ADJACENCY_DIRECTED &&
96 48 : G->is_symmetric_structure == LAGraph_TRUE))
97 : {
98 : // the structure of A is known to be symmetric
99 352 : A = G->A ;
100 : }
101 : else
102 : {
103 : // A is not known to be symmetric
104 16 : LG_ASSERT_MSG (false, -105, "G->A must be symmetric") ;
105 : }
106 :
107 352 : LG_ASSERT_MSG (G->out_degree != NULL, -106,
108 : "G->out_degree must be defined") ;
109 352 : LG_ASSERT_MSG (G->nself_edges == 0, -107, "G->nself_edges must be zero") ;
110 :
111 : //--------------------------------------------------------------------------
112 : // initializations
113 : //--------------------------------------------------------------------------
114 :
115 352 : GRB_TRY (GrB_Matrix_nrows (&n, A)) ;
116 352 : GRB_TRY (GrB_Vector_new (&neighbor_max, GrB_FP32, n)) ;
117 352 : GRB_TRY (GrB_Vector_new (°ree, GrB_FP32, n)) ;
118 352 : GRB_TRY (GrB_Vector_new (&new_members, GrB_BOOL, n)) ;
119 352 : GRB_TRY (GrB_Vector_new (&new_neighbors, GrB_BOOL, n)) ;
120 352 : GRB_TRY (GrB_Vector_new (&candidates, GrB_BOOL, n)) ;
121 352 : GRB_TRY (GrB_Vector_new (&empty, GrB_BOOL, n)) ;
122 352 : GRB_TRY (GrB_Vector_new (&Seed, GrB_UINT64, n)) ;
123 352 : GRB_TRY (GrB_Vector_new (&score, GrB_FP32, n)) ;
124 352 : GRB_TRY (GrB_Vector_new (&iset, GrB_BOOL, n)) ;
125 :
126 : // degree = (float) G->out_degree
127 352 : GRB_TRY (GrB_assign (degree, NULL, NULL, G->out_degree, GrB_ALL, n, NULL)) ;
128 :
129 : //--------------------------------------------------------------------------
130 : // remove singletons (nodes of degree zero) and handle ignore_node
131 : //--------------------------------------------------------------------------
132 :
133 352 : GrB_Index nonsingletons = 0 ;
134 352 : GRB_TRY (GrB_Vector_nvals (&nonsingletons, degree)) ;
135 352 : if (nonsingletons == n)
136 : {
137 160 : if (ignore_node == NULL)
138 : {
139 : // all nodes have degree 1 or more; all nodes are candidates
140 : // candidates (0:n-1) = true
141 80 : GRB_TRY (GrB_assign (candidates, NULL, NULL, (bool) true, GrB_ALL,
142 : n, NULL)) ;
143 : // Seed vector starts out dense
144 : // Seed (0:n-1) = 0
145 80 : GRB_TRY (GrB_assign (Seed, NULL, NULL, 0, GrB_ALL, n, NULL)) ;
146 : }
147 : else
148 : {
149 : // all nodes have degree 1 or more, but some nodes are to be
150 : // ignored. Use ignore_node as a valued mask.
151 : // candidates<!ignore_node> = true
152 80 : GRB_TRY (GrB_assign (candidates, ignore_node, NULL, (bool) true,
153 : GrB_ALL, n, GrB_DESC_C)) ;
154 : // Seed vector starts out sparse
155 : // Seed{candidates} = 0
156 80 : GRB_TRY (GrB_assign (Seed, candidates, NULL, 0, GrB_ALL, n,
157 : GrB_DESC_S)) ;
158 : }
159 : }
160 : else
161 : {
162 : // one or more singleton is present.
163 : // candidates{degree} = 1
164 192 : GRB_TRY (GrB_assign (candidates, degree, NULL, (bool) true,
165 : GrB_ALL, n, GrB_DESC_S)) ;
166 : // add all singletons to iset
167 : // iset{!degree} = 1
168 192 : GRB_TRY (GrB_assign (iset, degree, NULL, (bool) true, GrB_ALL, n,
169 : GrB_DESC_SC)) ;
170 192 : if (ignore_node != NULL)
171 : {
172 : // one or more singletons are present, and some nodes are to be
173 : // ignored. The candidates are all those nodes with degree > 0
174 : // for which ignore_node(i) is false (or not present). Delete
175 : // any candidate i for which ignore_node(i) is true. Use
176 : // ignore_node as a valued mask.
177 : // candidates<ignore_node> = empty
178 80 : GRB_TRY (GrB_assign (candidates, ignore_node, NULL, empty,
179 : GrB_ALL, n, NULL)) ;
180 : // Delete any ignored nodes from iset
181 : // iset<ignore_node> = empty
182 80 : GRB_TRY (GrB_assign (iset, ignore_node, NULL, empty,
183 : GrB_ALL, n, NULL)) ;
184 : }
185 : // Seed vector starts out sparse
186 : // Seed{candidates} = 0
187 192 : GRB_TRY (GrB_assign (Seed, candidates, NULL, 0, GrB_ALL, n,
188 : GrB_DESC_S)) ;
189 : }
190 :
191 : // create the random number seeds
192 352 : LG_TRY (LAGraph_Random_Seed (Seed, seed, msg)) ;
193 :
194 : //--------------------------------------------------------------------------
195 : // iterate while there are candidates to check
196 : //--------------------------------------------------------------------------
197 :
198 352 : int nstall = 0 ;
199 : GrB_Index ncandidates ;
200 352 : GRB_TRY (GrB_Vector_nvals (&ncandidates, candidates)) ;
201 352 : GrB_Index last_ncandidates = ncandidates ;
202 352 : GrB_Index n1 = (GrB_Index) (0.04 * (double) n) ;
203 352 : GrB_Index n2 = (GrB_Index) (0.10 * (double) n) ;
204 :
205 1362 : while (ncandidates > 0)
206 : {
207 : // compute the score for each node; scale the Seed by degree
208 : // score = (float) Seed
209 1165 : GRB_TRY (GrB_assign (score, NULL, NULL, Seed, GrB_ALL, n, NULL)) ;
210 : // score = score / degree
211 1152 : GRB_TRY (GrB_eWiseMult (score, NULL, NULL, GrB_DIV_FP32, score, degree,
212 : NULL)) ;
213 :
214 : // compute the max score of all candidate neighbors (only candidates
215 : // have a score, so non-candidate neighbors are excluded)
216 : // neighbor_max{candidates,replace} = score * A
217 1152 : GRB_TRY (GrB_Vector_nvals (&ncandidates, candidates)) ;
218 1152 : if (ncandidates < n1)
219 : {
220 : // push
221 : // neighbor_max'{candidates,replace} = score' * A
222 84 : GRB_TRY (GrB_vxm (neighbor_max, candidates, NULL,
223 : GrB_MAX_FIRST_SEMIRING_FP32, score, A, GrB_DESC_RS)) ;
224 : }
225 : else
226 : {
227 : // pull
228 : // neighbor_max{candidates,replace} = A * score
229 1068 : GRB_TRY (GrB_mxv (neighbor_max, candidates, NULL,
230 : GrB_MAX_SECOND_SEMIRING_FP32, A, score, GrB_DESC_RS)) ;
231 : }
232 :
233 : // select node if its score is > than all its active neighbors
234 : // new_members = (score > neighbor_max) using set union so that nodes
235 : // with no neighbors fall through to the output, as true (since no
236 : // score is equal to zero).
237 1152 : GRB_TRY (GrB_eWiseAdd (new_members, NULL, NULL, GrB_GT_FP32,
238 : score, neighbor_max, NULL)) ;
239 :
240 : // drop explicit zeros from new_members
241 1152 : GRB_TRY (GrB_select (new_members, NULL, NULL, GrB_VALUEEQ_BOOL,
242 : new_members, (bool) true, NULL)) ;
243 :
244 : // add new members to independent set
245 : // iset{new_members} = true
246 1152 : GRB_TRY (GrB_assign (iset, new_members, NULL, (bool) true,
247 : GrB_ALL, n, GrB_DESC_S)) ;
248 :
249 : // remove new members from set of candidates
250 : // candidates{new_members} = empty
251 1152 : GRB_TRY (GrB_assign (candidates, new_members, NULL, empty,
252 : GrB_ALL, n, GrB_DESC_S)) ;
253 :
254 : // early exit if candidates is empty
255 1152 : GRB_TRY (GrB_Vector_nvals (&ncandidates, candidates)) ;
256 1152 : if (ncandidates == 0) { break ; }
257 :
258 : // Neighbors of new members can also be removed from candidates
259 : // new_neighbors{candidates,replace} = new_members * A
260 : GrB_Index n_new_members ;
261 1023 : GRB_TRY (GrB_Vector_nvals (&n_new_members, new_members)) ;
262 1023 : if (n_new_members < n2)
263 : {
264 : // push
265 : // new_neighbors{candidates,replace} = new_members' * A
266 388 : GRB_TRY (GrB_vxm (new_neighbors, candidates, NULL,
267 : LAGraph_any_one_bool, new_members, A, GrB_DESC_RS)) ;
268 : }
269 : else
270 : {
271 : // pull
272 : // new_neighbors{candidates,replace} = A * new_members
273 635 : GRB_TRY (GrB_mxv (new_neighbors, candidates, NULL,
274 : LAGraph_any_one_bool, A, new_members, GrB_DESC_RS)) ;
275 : }
276 :
277 : // remove new neighbors of new members from set of candidates
278 : // candidates{new_neighbors} = empty
279 1023 : GRB_TRY (GrB_assign (candidates, new_neighbors, NULL, empty,
280 : GrB_ALL, n, GrB_DESC_S)) ;
281 :
282 : // sparsify the random number seeds (just keep it for each candidate)
283 : // Seed{candidates,replace} = Seed
284 1023 : GRB_TRY (GrB_assign (Seed, candidates, NULL, Seed, GrB_ALL, n,
285 : GrB_DESC_RS)) ;
286 :
287 : // Check for stall (can only occur if the matrix has self-edges, or in
288 : // the exceedingly rare case that 2 nodes have the exact same score).
289 : // If the method happens to stall, with no nodes selected because
290 : // the scores happen to tie, try again with another random score.
291 1023 : GRB_TRY (GrB_Vector_nvals (&ncandidates, candidates)) ;
292 1023 : if (last_ncandidates == ncandidates)
293 : {
294 : // This case is nearly untestable since it can almost never occur.
295 429 : nstall++ ;
296 : // terminate if the method has stalled too many times
297 429 : LG_ASSERT_MSG (nstall <= 32, -111, "stall") ;
298 : // recreate the random number seeds with a new starting seed
299 416 : LG_TRY (LAGraph_Random_Seed (Seed, seed + nstall, msg)) ;
300 : }
301 1010 : last_ncandidates = ncandidates ;
302 :
303 : // get the next random Seed vector
304 1010 : LG_TRY (LAGraph_Random_Next (Seed, msg)) ;
305 : }
306 :
307 : //--------------------------------------------------------------------------
308 : // free workspace and return result
309 : //--------------------------------------------------------------------------
310 :
311 339 : GRB_TRY (GrB_wait (iset, GrB_MATERIALIZE)) ;
312 339 : (*mis) = iset ;
313 339 : LG_FREE_WORK ;
314 339 : return (GrB_SUCCESS) ;
315 : }
|
