1 //------------------------------------------------------------------------------
2 // GraphBLAS/Demo/Source/mis.c: maximal independent set
3 //------------------------------------------------------------------------------
4
5 // SuiteSparse:GraphBLAS, Timothy A. Davis, (c) 2017-2021, All Rights Reserved.
6 // SPDX-License-Identifier: Apache-2.0
7
8 //------------------------------------------------------------------------------
9
10 // Modified from the GraphBLAS C API Specification, by Aydin Buluc, Timothy
11 // Mattson, Scott McMillan, Jose' Moreira, Carl Yang. Based on "GraphBLAS
12 // Mathematics" by Jeremy Kepner.
13
14 // No copyright claim is made for this particular file; the above copyright
15 // applies to all of SuiteSparse:GraphBLAS, not this file.
16
17 // This method has been updated as of Version 2.2 of SuiteSparse:GraphBLAS. It
18 // now uses GrB_vxm instead of GrB_mxv.
19
20 #include "GraphBLAS.h"
21 #undef GB_PUBLIC
22 #define GB_LIBRARY
23 #include "graphblas_demos.h"
24
25 //------------------------------------------------------------------------------
26 // mis: maximal independent set
27 //------------------------------------------------------------------------------
28
29 // A variant of Luby's randomized algorithm [Luby 1985].
30
31 // Given a numeric n x n adjacency matrix A of an unweighted and undirected
32 // graph (where the value true represents an edge), compute a maximal set of
33 // independent nodes and return it in a boolean n-vector, 'iset' where
34 // set[i] == true implies node i is a member of the set (the iset vector
35 // should be uninitialized on input.)
36
37 // The graph cannot have any self edges, and it must be symmetric. These
38 // conditions are not checked. Self-edges will cause the method to stall.
39
40 // Singletons require special treatment. Since they have no neighbors, their
41 // prob is never greater than the max of their neighbors, so they never get
42 // selected and cause the method to stall. To avoid this case they are removed
43 // from the candidate set at the begining, and added to the iset.
44
45 GB_PUBLIC
mis(GrB_Vector * iset_output,const GrB_Matrix A,int64_t seed)46 GrB_Info mis // compute a maximal independent set
47 (
48 GrB_Vector *iset_output, // iset(i) = true if i is in the set
49 const GrB_Matrix A, // symmetric Boolean matrix
50 int64_t seed // random number seed
51 )
52 {
53
54 GrB_Vector iset = NULL ;
55 GrB_Vector prob = NULL ; // random probability for each node
56 GrB_Vector neighbor_max = NULL ; // value of max neighbor probability
57 GrB_Vector new_members = NULL ; // set of new members to iset
58 GrB_Vector new_neighbors = NULL ; // new neighbors to new iset members
59 GrB_Vector candidates = NULL ; // candidate members to iset
60 GrB_Semiring maxSelect1st = NULL ; // Max/Select1st "semiring"
61 GrB_BinaryOp set_random = NULL ;
62 GrB_Vector degrees = NULL ;
63
64 GrB_Index n ;
65
66 GrB_Matrix_nrows (&n, A) ; // n = # of nodes in graph
67
68 GrB_Vector_new (&prob, GrB_FP64, n) ;
69 GrB_Vector_new (&neighbor_max, GrB_FP64, n) ;
70 GrB_Vector_new (&new_members, GrB_BOOL, n) ;
71 GrB_Vector_new (&new_neighbors, GrB_BOOL, n) ;
72 GrB_Vector_new (&candidates, GrB_BOOL, n) ;
73
74 // Initialize independent set vector, bool
75 GrB_Vector_new (&iset, GrB_BOOL, n) ;
76
77 // create the maxSelect1st semiring
78 GrB_Semiring_new (&maxSelect1st, GrB_MAX_MONOID_FP64, GrB_FIRST_FP64) ;
79
80 // create the random number seeds
81 GrB_Vector Seed, X ;
82 prand_init ( ) ;
83 prand_seed (&Seed, seed, n, 0) ;
84 GrB_Vector_new (&X, GrB_FP64, n) ;
85
86 // create the mis_score binary operator
87 GrB_BinaryOp_new (&set_random, mis_score2, GrB_FP64, GrB_UINT32, GrB_FP64) ;
88
89 // compute the degree of each nodes
90 GrB_Vector_new (°rees, GrB_FP64, n) ;
91 GrB_Matrix_reduce_Monoid (degrees, NULL, NULL, GrB_PLUS_MONOID_FP64,
92 A, NULL) ;
93
94 // singletons are not candidates; they are added to iset first instead
95 // candidates[degree != 0] = 1
96 GrB_Vector_assign_BOOL (candidates, degrees, NULL, true, GrB_ALL, n, NULL);
97
98 // add all singletons to iset
99 // iset[degree == 0] = 1
100 GrB_Vector_assign_BOOL (iset, degrees, NULL, true, GrB_ALL, n, GrB_DESC_RC);
101
102 // Iterate while there are candidates to check.
103 GrB_Index nvals ;
104 GrB_Vector_nvals (&nvals, candidates) ;
105
106 int64_t last_nvals = nvals ;
107
108 while (nvals > 0)
109 {
110 // sparsify the random number seeds (just keep it for each candidate)
111 GrB_Vector_assign (Seed, candidates, NULL, Seed, GrB_ALL, n, GrB_DESC_R) ;
112
113 // compute a random probability scaled by inverse of degree
114 // GrB_Vector_apply (prob, candidates, NULL, set_random, degrees,
115 // GrB_DESC_R) ;
116 prand_xget (X, Seed) ;
117 GrB_Vector_eWiseMult_BinaryOp (prob, candidates, NULL, set_random,
118 degrees, X, GrB_DESC_R) ;
119
120 // compute the max probability of all neighbors
121 GrB_vxm (neighbor_max, candidates, NULL, maxSelect1st,
122 prob, A, GrB_DESC_R) ;
123
124 // select node if its probability is > than all its active neighbors
125 GrB_Vector_eWiseAdd_BinaryOp (new_members, NULL, NULL, GrB_GT_FP64,
126 prob, neighbor_max, NULL) ;
127
128 // add new members to independent set.
129 GrB_Vector_eWiseAdd_BinaryOp (iset, NULL, NULL, GrB_LOR, iset,
130 new_members, NULL) ;
131
132 // remove new members from set of candidates
133 // candidates<!new_members> = candidates
134 GrB_Vector_apply (candidates, new_members, NULL, GrB_IDENTITY_BOOL,
135 candidates, GrB_DESC_RC) ;
136
137 GrB_Vector_nvals (&nvals, candidates) ;
138 if (nvals == 0) { break ; } // early exit condition
139
140 // Neighbors of new members can also be removed from candidates
141 GrB_vxm (new_neighbors, candidates, NULL, GrB_LOR_LAND_SEMIRING_BOOL,
142 new_members, A, NULL) ;
143 // candidates<!new_neighbors> = candidates
144 GrB_Vector_apply (candidates, new_neighbors, NULL, GrB_IDENTITY_BOOL,
145 candidates, GrB_DESC_RC) ;
146
147 GrB_Vector_nvals (&nvals, candidates) ;
148
149 // this will not occur, unless the input is corrupted somehow
150 if (last_nvals == nvals) { printf ("stall!\n") ; exit (1) ; }
151 last_nvals = nvals ;
152 }
153
154 // drop explicit false values
155 GrB_Vector_apply (iset, iset, NULL, GrB_IDENTITY_BOOL, iset, GrB_DESC_R) ;
156
157 // return result
158 *iset_output = iset ;
159
160 // free workspace
161 GrB_Vector_free (&prob) ;
162 GrB_Vector_free (&neighbor_max) ;
163 GrB_Vector_free (&new_members) ;
164 GrB_Vector_free (&new_neighbors) ;
165 GrB_Vector_free (&candidates) ;
166 GrB_Semiring_free (&maxSelect1st) ;
167 GrB_BinaryOp_free (&set_random) ;
168 GrB_Vector_free (°rees) ;
169 GrB_Vector_free (&Seed) ;
170 GrB_Vector_free (&X) ;
171 prand_finalize ( ) ;
172
173 return (GrB_SUCCESS) ;
174 }
175
176