1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
//------------------------------------------------------------------------------
// LAGraph_AllKCore: Full K-core Decomposition Using the GraphBLAS API
//------------------------------------------------------------------------------
// LAGraph, (c) 2019-2022 by The LAGraph Contributors, All Rights Reserved.
// SPDX-License-Identifier: BSD-2-Clause
//
// For additional details (including references to third party source code and
// other files) see the LICENSE file or contact permission@sei.cmu.edu. See
// Contributors.txt for a full list of contributors. Created, in part, with
// funding and support from the U.S. Government (see Acknowledgments.txt file).
// DM22-0790
// Contributed by Pranav Konduri, Texas A&M University
//------------------------------------------------------------------------------
// The input is an undirected graph, or a directed graph with a symmetric
// adjacency matrix. Edge weights are ignored. On output, decomp(i) = k if
// node i is in the 1-cores to k-core, but is not present in the (k+1)-core.
#define LG_FREE_WORK \
{ \
GrB_free (°) ; \
GrB_free (&q) ; \
GrB_free (&delta) ; \
GrB_free (&done) ; \
}
#define LG_FREE_ALL \
{ \
LG_FREE_WORK \
GrB_free (decomp) ; \
}
#include "LG_internal.h"
// TODO: need both basic and expert methods; this is mixed
// TODO: match filename to function name (this name is OK)
// vanilla OK: no GxB used here
int LAGraph_KCore_All
(
// outputs:
GrB_Vector *decomp, // kcore decomposition
uint64_t *kmax,
// inputs:
LAGraph_Graph G, // input graph
char *msg
)
{
LG_CLEAR_MSG ;
// declare items
GrB_Matrix A = NULL;
GrB_Vector deg = NULL, q = NULL, done = NULL, delta = NULL;
LG_ASSERT (decomp != NULL, GrB_NULL_POINTER) ;
LG_ASSERT (kmax != NULL, GrB_NULL_POINTER) ;
(*decomp) = NULL ;
(*kmax) = 0 ;
LG_TRY (LAGraph_CheckGraph (G, msg)) ;
if (G->kind == LAGraph_ADJACENCY_UNDIRECTED ||
(G->kind == LAGraph_ADJACENCY_DIRECTED &&
G->is_symmetric_structure == LAGraph_TRUE))
{
// the structure of A is known to be symmetric
A = G->A ;
}
else
{
// A is not known to be symmetric
LG_ASSERT_MSG (false, -1005, "G->A must be symmetric") ;
}
// TODO: in basic: compute it, this is Advanced:
// no self edges can be present
LG_ASSERT_MSG (G->nself_edges == 0, -1004, "G->nself_edges must be zero") ;
//create work scalars
uint64_t level = 0; //don't set at 1 in case of empty graph getting returned as kmax = 1
GrB_Index n, todo, nvals, maxDeg ;
GRB_TRY (GrB_Matrix_nrows(&n, A)) ;
// TODO: do not call Cached in an advanced algorithm, this is Basic:
//create deg vector using out_degree property
LG_TRY (LAGraph_Cached_OutDegree(G, msg)) ;
GRB_TRY (GrB_Vector_dup(°, G->out_degree)) ; //original deg vector is technically 1-core since 0 is omitted
GRB_TRY (GrB_Vector_nvals(&todo, deg)) ; //use todo instead of n since some values are omitted (1-core)
//retrieve the max degree level of the graph
GRB_TRY (GrB_reduce(&maxDeg, GrB_NULL, GrB_MAX_MONOID_INT64, G->out_degree, GrB_NULL)) ;
//select int type for work vectors and semirings
GrB_Type int_type = (maxDeg > INT32_MAX) ? GrB_INT64 : GrB_INT32 ;
GRB_TRY (GrB_Vector_new(&q, int_type, n));
GRB_TRY (GrB_Vector_new(&done, GrB_BOOL, n)) ;
GRB_TRY (GrB_Vector_new(&delta, int_type, n)) ;
//set output to int64
GRB_TRY (GrB_Vector_new(decomp, int_type, n)) ;
//change deg vector to int32 if needed
if (int_type == GrB_INT32)
{
// TODO: deg is freed; it should never have been constructed above
GrB_free (°) ;
GRB_TRY (GrB_Vector_new(°, int_type, n)) ;
GRB_TRY (GrB_assign (deg, G->out_degree, NULL, G->out_degree, GrB_ALL, n, NULL)) ;
}
// determine semiring types
GrB_IndexUnaryOp valueEQ = (maxDeg > INT32_MAX) ? GrB_VALUEEQ_INT64 : GrB_VALUEEQ_INT32 ;
GrB_IndexUnaryOp valueLE = (maxDeg > INT32_MAX) ? GrB_VALUELE_INT64 : GrB_VALUELE_INT32 ;
GrB_BinaryOp minus_op = (maxDeg > INT32_MAX) ? GrB_MINUS_INT64 : GrB_MINUS_INT32 ;
GrB_Semiring semiring = (maxDeg > INT32_MAX) ? LAGraph_plus_one_int64 : LAGraph_plus_one_int32 ;
GRB_TRY (LG_SET_FORMAT_HINT (done, LG_BITMAP + LG_FULL)) ;
while (todo > 0)
{
level++;
// Creating q
// get all nodes with degree = level
GRB_TRY (GrB_select (q, GrB_NULL, GrB_NULL, valueEQ, deg, level, GrB_NULL)) ;
GRB_TRY (GrB_Vector_nvals(&nvals, q));
//Assign values of deg into decomp (output)
GRB_TRY (GrB_assign (*decomp, deg, NULL, level, GrB_ALL, n, GrB_NULL)) ;
int round = 0;
// while q not empty
while(nvals > 0){
// Decrease todo by number of nvals
todo = todo - nvals ;
//add anything in q as true into the done list
GRB_TRY (GrB_assign (done, q, NULL, (bool) true, GrB_ALL, n, GrB_DESC_S)) ; //structure to take care of 0-node cases
// Create delta (the nodes who lost friends, and how many they lost)
GRB_TRY (GrB_vxm (delta, GrB_NULL, GrB_NULL, semiring, q, A, GrB_NULL));
// Create new deg vector (keep anything not in done vector w/ replace command)
GRB_TRY (GrB_eWiseAdd(deg, done, GrB_NULL, minus_op, deg, delta, GrB_DESC_RSC /* try GrB_DESC_RSC */)) ;
// Update q, set new nvals
GRB_TRY (GrB_select (q, GrB_NULL, GrB_NULL, valueLE, deg, level, GrB_NULL)) ;
GRB_TRY (GrB_Vector_nvals(&nvals, q)) ;
round++;
}
}
//set kmax
(*kmax) = level;
LG_FREE_WORK ;
return (GrB_SUCCESS) ;
}