Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LAGraph_KCore: Single 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 k-core, or empty otherwise.
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: revise and add to src
39 : // TODO: need both basic and expert methods; this is mixed
40 : // vanilla OK: no GxB used here
41 :
42 8 : int LAGraph_KCore // TODO: LAGr_KCore (expert), cache is_symmetric_structure
43 : // TODO: cache nself_edges
44 : // TODO: cache out degree
45 : (
46 : // outputs:
47 : GrB_Vector *decomp, // kcore decomposition
48 : // inputs:
49 : LAGraph_Graph G, // input graph
50 : uint64_t k, // kcore to compute
51 : char *msg
52 : )
53 : {
54 8 : LG_CLEAR_MSG ;
55 :
56 : // declare items
57 8 : GrB_Matrix A = NULL;
58 8 : GrB_Vector deg = NULL, q = NULL, done = NULL, delta = NULL;
59 :
60 8 : LG_ASSERT (decomp != NULL, GrB_NULL_POINTER) ;
61 7 : (*decomp) = NULL ;
62 :
63 7 : LG_TRY (LAGraph_CheckGraph (G, msg)) ;
64 :
65 6 : if (G->kind == LAGraph_ADJACENCY_UNDIRECTED ||
66 3 : (G->kind == LAGraph_ADJACENCY_DIRECTED &&
67 3 : G->is_symmetric_structure == LAGraph_TRUE))
68 : {
69 : // the structure of A is known to be symmetric
70 5 : 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 : // no self edges can be present
79 5 : LG_ASSERT_MSG (G->nself_edges == 0, -1004, "G->nself_edges must be zero") ;
80 :
81 : //create work scalars
82 : GrB_Index n, qnvals, degnvals, maxDeg;
83 4 : GRB_TRY (GrB_Matrix_nrows(&n, A)) ;
84 :
85 : //create deg vector using rowdegree property
86 4 : LG_TRY (LAGraph_Cached_OutDegree(G, msg)) ;
87 4 : GRB_TRY (GrB_Vector_dup(°, G->out_degree)) ; //original deg vector is technically 1-core since 0 is omitted
88 4 : GRB_TRY (GrB_Vector_nvals(°nvals, deg)) ;
89 :
90 : //retrieve the max degree level of the graph
91 4 : GRB_TRY (GrB_reduce(&maxDeg, GrB_NULL, GrB_MAX_MONOID_INT64, G->out_degree, GrB_NULL)) ;
92 :
93 : //select int type for work vectors and semirings
94 4 : GrB_Type int_type = (maxDeg > INT32_MAX) ? GrB_INT64 : GrB_INT32 ;
95 :
96 4 : GRB_TRY (GrB_Vector_new(&q, int_type, n));
97 4 : GRB_TRY (GrB_Vector_new(&done, GrB_BOOL, n)) ;
98 4 : GRB_TRY (GrB_Vector_new(&delta, int_type, n)) ;
99 : //set output to int64
100 4 : GRB_TRY (GrB_Vector_new(decomp, int_type, n)) ;
101 :
102 : //change deg vector to int32 if needed
103 4 : if (int_type == GrB_INT32)
104 : {
105 : // TODO: deg is freed; it should never have been constructed above
106 4 : GrB_free (°) ;
107 4 : GRB_TRY (GrB_Vector_new(°, int_type, n)) ;
108 4 : GRB_TRY (GrB_assign (deg, G->out_degree, NULL, G->out_degree, GrB_ALL, n, NULL)) ;
109 : }
110 :
111 : // determine semiring types
112 4 : GrB_IndexUnaryOp valueLT = (maxDeg > INT32_MAX) ? GrB_VALUELT_INT64 : GrB_VALUELT_INT32 ;
113 4 : GrB_BinaryOp minus_op = (maxDeg > INT32_MAX) ? GrB_MINUS_INT64 : GrB_MINUS_INT32 ;
114 4 : GrB_Semiring semiring = (maxDeg > INT32_MAX) ? LAGraph_plus_one_int64 : LAGraph_plus_one_int32 ;
115 :
116 4 : GRB_TRY (LG_SET_FORMAT_HINT (done, LG_BITMAP + LG_FULL)) ;
117 :
118 : // Creating q
119 : // get all nodes with degree = level
120 4 : GRB_TRY (GrB_select (q, GrB_NULL, GrB_NULL, valueLT, deg, k, GrB_NULL)) ;
121 4 : GRB_TRY (GrB_Vector_nvals(&qnvals, q));
122 :
123 : // while q not empty
124 4 : int round = 0;
125 10 : while (qnvals > 0 && degnvals > 0)
126 : {
127 6 : round++;
128 : //add anything in q as true into the done list
129 : //structure to take care of 0-node cases
130 6 : GRB_TRY (GrB_assign (done, q, NULL, (bool) true, GrB_ALL, n, GrB_DESC_S)) ;
131 :
132 : // Create delta (the nodes who lost friends, and how many they lost) (push version)
133 6 : GRB_TRY (GrB_vxm (delta, GrB_NULL, GrB_NULL, semiring, q, A, GrB_NULL));
134 :
135 : // Create new deg vector (keep anything not in done vector)
136 6 : GRB_TRY (GrB_eWiseAdd(deg, done, GrB_NULL, minus_op, deg, delta, GrB_DESC_RSC)) ;
137 :
138 : // Update q, set new nvals
139 6 : GRB_TRY (GrB_select (q, GrB_NULL, GrB_NULL, valueLT, deg, k, GrB_NULL)) ;
140 6 : GRB_TRY (GrB_Vector_nvals(&qnvals, q)) ;
141 6 : GRB_TRY (GrB_Vector_nvals(°nvals, deg)) ;
142 : }
143 : //Assign values of deg to decomp
144 4 : GRB_TRY (GrB_assign (*decomp, deg, NULL, k, GrB_ALL, n, GrB_NULL)) ;
145 4 : GRB_TRY(GrB_Vector_wait(*decomp, GrB_MATERIALIZE));
146 4 : LG_FREE_WORK ;
147 4 : return (GrB_SUCCESS) ;
148 : }
|
