Skip to content

Commit 2ec46f3

Browse files
GomezGabGomezGab
committed
Allow splitting in Leiden Phase 1
1 parent 733623b commit 2ec46f3

2 files changed

Lines changed: 150 additions & 43 deletions

File tree

‎experimental/algorithm/LAGraph_Leiden.c‎

Lines changed: 90 additions & 43 deletions
Original file line numberDiff line numberDiff line change
@@ -107,10 +107,15 @@
107107
#undef LG_FREE_WORK
108108
#define LG_FREE_WORK \
109109
{ \
110+
GrB_free (&c_deg_vec); \
111+
GrB_free (&c_size_vec); \
110112
GrB_free (&neighbor_it); \
111113
GrB_free (&it); \
112-
GrB_free (&c_deg); \
113114
GrB_free (&x); \
115+
LAGraph_Free ((void **) &c_deg, NULL) ; \
116+
LAGraph_Free ((void **) &node_deg, NULL) ; \
117+
LAGraph_Free ((void **) &community_size, NULL) ; \
118+
LAGraph_Free ((void **) &empty_stack, NULL) ; \
114119
}
115120

116121
#undef LG_FREE_ALL
@@ -136,30 +141,62 @@ int LG_Leiden_move_nodes
136141
double m_inv2, // -1 / (2 * m)
137142
char* msg
138143
) {
139-
uint64_t node_id, com_id, n_deg, n;
140-
GrB_Vector x = NULL;
141-
GrB_Vector c_deg = NULL ;
142-
GxB_Iterator it = NULL, neighbor_it = NULL;
144+
uint64_t node_id, com_id, n ;
145+
GrB_Vector x = NULL ;
146+
GrB_Vector c_deg_vec = NULL ;
147+
GrB_Vector c_size_vec = NULL ;
148+
double *c_deg = NULL ;
149+
double *node_deg = NULL ;
150+
uint64_t *community_size = NULL ;
151+
uint64_t *empty_stack = NULL ;
152+
uint64_t empty_top = 0 ;
153+
GxB_Iterator it = NULL, neighbor_it = NULL ;
143154
GRB_TRY (GrB_Matrix_nrows (&n, A)) ;
144155
uint64_t queue_head = 0, queue_tail = n, queue_size = n + 1;
145156

146157
GRB_TRY (GxB_Iterator_new (&it)) ;
147-
GRB_TRY (GrB_Vector_new (&c_deg, GrB_FP64, n)) ;
148158
GRB_TRY (GrB_Vector_new (&x, GrB_FP64, n)) ;
159+
GRB_TRY (GrB_Vector_new (&c_deg_vec, GrB_FP64, n)) ;
160+
GRB_TRY (GrB_Vector_new (&c_size_vec, GrB_UINT64, n)) ;
149161
GRB_TRY (GxB_Iterator_new (&neighbor_it)) ;
150-
GRB_TRY (GxB_rowIterator_attach (neighbor_it, A, NULL));
162+
GRB_TRY (GxB_rowIterator_attach (neighbor_it, A, NULL)) ;
163+
LG_TRY (LAGraph_Malloc ((void **) &empty_stack, n, sizeof (uint64_t), msg)) ;
164+
165+
// initialize degree and community degree vectors, then unpack to C arrays
166+
GRB_TRY (GrB_assign (c_deg_vec, NULL, NULL, 0.0, GrB_ALL, n, NULL)) ;
167+
GRB_TRY (GrB_assign (c_size_vec, NULL, NULL, (uint64_t) 0, GrB_ALL, n, NULL)) ;
168+
GRB_TRY (GrB_vxm (c_deg_vec, NULL, GrB_PLUS_FP64, GxB_PLUS_FIRST_FP64, deg, C, NULL)) ;
169+
GRB_TRY (GrB_vxm (c_size_vec, NULL, GrB_PLUS_UINT64, GxB_PLUS_PAIR_UINT64, deg, C, NULL)) ;
170+
171+
GrB_Type node_type = NULL, cdeg_type = NULL, csize_type = NULL ;
172+
uint64_t node_nheld = 0, cdeg_nheld = 0, csize_nheld = 0 ;
173+
uint64_t node_size = 0, cdeg_size = 0, csize_size = 0 ;
174+
int node_handling = 0, cdeg_handling = 0, csize_handling = 0 ;
175+
GRB_TRY (GxB_Vector_unload (deg, (void **) &node_deg, &node_type,
176+
&node_nheld, &node_size, &node_handling, NULL)) ;
177+
GRB_TRY (GxB_Vector_unload (c_deg_vec, (void **) &c_deg, &cdeg_type,
178+
&cdeg_nheld, &cdeg_size, &cdeg_handling, NULL)) ;
179+
GRB_TRY (GxB_Vector_unload (c_size_vec, (void **) &community_size, &csize_type,
180+
&csize_nheld, &csize_size, &csize_handling, NULL)) ;
181+
182+
for (uint64_t c = 0 ; c < n ; c++)
183+
{
184+
if (community_size [c] == 0)
185+
{
186+
empty_stack [empty_top++] = c ;
187+
}
188+
}
151189

152-
GRB_TRY (GrB_assign (c_deg, NULL, NULL, 0.0, GrB_ALL, n, NULL)) ;
153-
GRB_TRY (GrB_vxm(c_deg, NULL, NULL, GxB_PLUS_FIRST_FP64, deg, C, NULL));
154190
// TODO: decide if queue should be made inside this function.
155191
uint64_t nodes_popped = 0, nodes_evaluated = 0, nodes_moved = 0;
156192
while (queue_head != queue_tail) { // while queue not empty
157193
nodes_popped++;
158194
LG_QUEUE_DEQUEUE (queue, queue_head, queue_size, node_id) ;
159-
enqueued [node_id] = false;
160-
double com_deg, n_deg;
195+
enqueued [node_id] = false ;
161196
uint64_t n_neighbors;
162197
com_id = community [node_id] ;
198+
const uint64_t old_size = community_size [com_id] ;
199+
const double degree_i = node_deg [node_id] ;
163200
GRB_TRY (GrB_Vector_clear (x));
164201
// GRB_TRY (GrB_Vector_setElement_FP64 (x, 0.0, node_id)) ;
165202
// GRB_TRY (GrB_vxm (x, NULL, GrB_PLUS_FP64, GxB_PLUS_SECOND_FP64, x, A, NULL)) ;
@@ -174,51 +211,65 @@ int LG_Leiden_move_nodes
174211
GRB_TRY (GrB_vxm (x, NULL, NULL, GxB_PLUS_FIRST_FP64, x, C, NULL)) ;
175212

176213
// momentarily remove node degree from the community total
177-
GRB_TRY (GrB_Vector_extractElement_FP64 (&n_deg, deg, node_id));
178-
179-
// c_deg [com_id] -= ndeg
180-
GRB_TRY (GrB_assign (c_deg, NULL, GrB_MINUS_FP64, n_deg, &com_id, 1, NULL));
214+
c_deg [com_id] -= degree_i ;
215+
community_size [com_id]-- ;
181216

182217
// Calculate gain in each neighboring community
183-
uint64_t max_gain_c;
184-
double max_gain_val = -1e100;
185-
double y = m_inv2 * n_deg;
186-
GRB_TRY (GxB_Vector_Iterator_attach (it, x, NULL));
187-
GrB_Info info = GxB_Vector_Iterator_seek (it, 0);
218+
uint64_t max_gain_c = com_id ;
219+
double max_gain_val = -1.0 ;
220+
double y = m_inv2 * degree_i ;
221+
GRB_TRY (GxB_Vector_Iterator_attach (it, x, NULL)) ;
222+
GrB_Info info = GxB_Vector_Iterator_seek (it, 0) ;
188223
while (info == GrB_SUCCESS) {
189-
uint64_t c = GxB_Vector_Iterator_getIndex (it);
190-
double gain = GxB_Iterator_get_FP64 (it);
191-
double com_deg;
192-
GRB_TRY (GrB_Vector_extractElement_FP64 (&com_deg, c_deg, c)) ;
193-
gain += y * com_deg ;
224+
uint64_t c = GxB_Vector_Iterator_getIndex (it) ;
225+
double gain = GxB_Iterator_get_FP64 (it) ;
226+
gain += y * c_deg [c] ;
194227
if (gain > max_gain_val) {
195-
max_gain_val = gain;
196-
max_gain_c = c;
228+
max_gain_val = gain ;
229+
max_gain_c = c ;
197230
}
198-
info = GxB_Vector_Iterator_next (it);
231+
info = GxB_Vector_Iterator_next (it) ;
232+
}
233+
234+
uint64_t new_com_id = com_id ;
235+
if (max_gain_val >= 0.0)
236+
{
237+
new_com_id = max_gain_c ;
238+
}
239+
else if (old_size > 1 && empty_top > 0)
240+
{
241+
new_com_id = empty_stack [--empty_top] ;
199242
}
200243

201-
community [node_id] = max_gain_c;
202-
// c_deg [node_id] += ndeg
203-
GRB_TRY (GrB_assign (c_deg, NULL, GrB_PLUS_FP64, n_deg, &max_gain_c, 1, NULL));
244+
community [node_id] = new_com_id ;
245+
c_deg [new_com_id] += degree_i ;
246+
community_size [new_com_id]++ ;
204247

205-
if (max_gain_c == com_id) continue; // no change in community
206-
nodes_moved++;
248+
if (new_com_id == com_id) continue; // no change in community
249+
nodes_moved++ ;
250+
if (community_size [com_id] == 0)
251+
{
252+
empty_stack [empty_top++] = com_id ;
253+
}
207254

208255
// push every neighbor in a different community that is not already in
209256
// the queue to the back of the queue
210-
info = GxB_rowIterator_seekRow (neighbor_it, node_id);
257+
info = GxB_rowIterator_seekRow (neighbor_it, node_id) ;
211258
while (info == GrB_SUCCESS) {
212-
uint64_t neighbor_id = GxB_rowIterator_getColIndex (neighbor_it);
213-
if (max_gain_c != community [neighbor_id]
259+
uint64_t neighbor_id = GxB_rowIterator_getColIndex (neighbor_it) ;
260+
if (new_com_id != community [neighbor_id]
214261
&& !enqueued [neighbor_id]) {
215262
LG_QUEUE_ENQUEUE (queue, queue_tail, queue_size, neighbor_id) ;
216-
enqueued[neighbor_id] = true;
263+
enqueued[neighbor_id] = true ;
217264
}
218265

219-
info = GxB_rowIterator_nextCol (neighbor_it);
266+
info = GxB_rowIterator_nextCol (neighbor_it) ;
220267
}
221268
}
269+
270+
GRB_TRY (GxB_Vector_load (deg, (void **) &node_deg, node_type,
271+
node_nheld, node_size, node_handling, NULL)) ;
272+
222273
if (nodes_popped_handle != NULL) (*nodes_popped_handle) = nodes_popped;
223274
if (nodes_evaluated_handle != NULL) (*nodes_evaluated_handle) = nodes_evaluated;
224275
if (nodes_moved_handle != NULL) (*nodes_moved_handle) = nodes_moved;
@@ -270,7 +321,6 @@ int LG_Leiden_refinement
270321
// input:
271322
const GrB_Matrix C, // community matrix
272323
const uint64_t *community, // community array (inside of C matrix)
273-
const GrB_Vector c_deg, // degree vector
274324
const GrB_Matrix A, // adjacency matrix
275325
const GrB_Vector deg, // degree vector
276326
uint64_t *queue, // queue to use (contains all nodes)
@@ -551,7 +601,6 @@ int LG_Leiden_aggregate
551601
GrB_free (&S); \
552602
if (free_A) GrB_free (&A) ; \
553603
GrB_free (&deg); \
554-
GrB_free (&c_deg); \
555604
GrB_free (&x); \
556605
GrB_free (&node_map); \
557606
GrB_free (&new_node_map); \
@@ -589,8 +638,6 @@ int LAGraph_Leiden
589638
GrB_Matrix S = NULL ; // contains readonly pointer to sub-community array
590639

591640
GrB_Vector deg = NULL ; // degree of each node
592-
GrB_Vector c_deg = NULL ; // degree of each community
593-
594641
GrB_Matrix A = NULL ; // G->A
595642
GrB_Vector x = NULL; // full boolean vector
596643
GrB_Matrix node_map = NULL ; // maps aggregate node to nodes it contains
@@ -779,7 +826,7 @@ int LAGraph_Leiden
779826
LG_LEIDEN_BURBLE_ON;
780827
// memcpy (sub_com, community, n * sizeof (uint64_t)) ;
781828
LG_TRY (LG_Leiden_refinement (S, sub_com, &refine_evaluated, C, community,
782-
c_deg, A, deg, queue, m_inv2, msg)) ;
829+
A, deg, queue, m_inv2, msg)) ;
783830
LG_TRY (LG_Leiden_refinement_stats (
784831
&refine_split_total, &refine_split_avg, &refine_within_parent,
785832
C, S, msg)) ;

‎experimental/test/test_leiden.c‎

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -20,6 +20,21 @@ GrB_Matrix A = NULL ;
2020
#define LEN 512
2121
char filename[LEN + 1] ;
2222

23+
int LG_Leiden_move_nodes
24+
(
25+
GrB_Matrix C,
26+
uint64_t *community,
27+
uint64_t *nodes_popped_handle,
28+
uint64_t *nodes_evaluated_handle,
29+
uint64_t *nodes_moved_handle,
30+
const GrB_Matrix A,
31+
const GrB_Vector deg,
32+
uint64_t *queue,
33+
bool *enqueued,
34+
double m_inv2,
35+
char *msg
36+
) ;
37+
2338
typedef struct
2439
{
2540
const char *matrix_file ;
@@ -141,6 +156,7 @@ void test_Leiden (void)
141156

142157
GrB_Info info = LAGraph_Leiden (&c, G, seed, msg) ;
143158
TEST_CHECK (info == GrB_SUCCESS) ;
159+
144160
if (info != GrB_SUCCESS)
145161
{
146162
GrB_free (&c) ;
@@ -244,6 +260,49 @@ void test_Leiden_NonfiniteInputs (void)
244260
LAGraph_Finalize (msg) ;
245261
}
246262

263+
void test_Leiden_Phase1SingletonSplit (void)
264+
{
265+
LAGraph_Init (msg) ;
266+
267+
const GrB_Index n = 4 ;
268+
GrB_Matrix B = NULL, C = NULL ;
269+
GrB_Vector deg = NULL ;
270+
OK (GrB_Matrix_new (&B, GrB_FP64, n, n)) ;
271+
OK (GrB_Matrix_new (&C, GrB_BOOL, n, n)) ;
272+
OK (GrB_Vector_new (&deg, GrB_FP64, n)) ;
273+
274+
GrB_Index Ai [4] = { 0, 2, 0, 3 } ;
275+
GrB_Index Aj [4] = { 2, 0, 3, 0 } ;
276+
double Ax [4] = { 1.0, 1.0, 1.0, 1.0 } ;
277+
OK (GrB_Matrix_build_FP64 (B, Ai, Aj, Ax, 4, GrB_PLUS_FP64)) ;
278+
279+
uint64_t community [4] = { 0, 0, 2, 3 } ;
280+
for (GrB_Index i = 0 ; i < n ; i++)
281+
{
282+
OK (GrB_Matrix_setElement_BOOL (C, true, i, community [i])) ;
283+
}
284+
285+
// Deliberately chosen to force negative neighbor gains for node 0.
286+
OK (GrB_Vector_setElement_FP64 (deg, 100.0, 0)) ;
287+
OK (GrB_Vector_setElement_FP64 (deg, 100.0, 1)) ;
288+
OK (GrB_Vector_setElement_FP64 (deg, 100.0, 2)) ;
289+
OK (GrB_Vector_setElement_FP64 (deg, 100.0, 3)) ;
290+
291+
uint64_t queue [5] = { 0, 1, 2, 3, 0 } ;
292+
bool enqueued [4] = { true, true, true, true } ;
293+
uint64_t popped = 0, evaluated = 0, moved = 0 ;
294+
OK (LG_Leiden_move_nodes (C, community, &popped, &evaluated, &moved,
295+
B, deg, queue, enqueued, -1.0 / 400.0, msg)) ;
296+
297+
// Community 1 starts empty; node 0 should split into it.
298+
TEST_CHECK (community [0] == 1) ;
299+
300+
OK (GrB_free (&deg)) ;
301+
OK (GrB_free (&C)) ;
302+
OK (GrB_free (&B)) ;
303+
LAGraph_Finalize (msg) ;
304+
}
305+
247306
#if LG_BRUTAL_TESTS
248307
void test_Leiden_brutal (void)
249308
{
@@ -292,6 +351,7 @@ TEST_LIST =
292351
{
293352
{ "Leiden", test_Leiden },
294353
{ "Leiden nonfinite inputs", test_Leiden_NonfiniteInputs },
354+
{ "Leiden phase1 singleton split", test_Leiden_Phase1SingletonSplit },
295355
#if LG_BRUTAL_TESTS
296356
{ "Leiden brutal", test_Leiden_brutal },
297357
#endif

0 commit comments

Comments
 (0)