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