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 : #define LG_FREE_WORK \
19 : { \
20 : GrB_free (°) ; \
21 : GrB_free (&q) ; \
22 : GrB_free (&delta) ; \
23 : GrB_free (&done) ; \
24 : }
25 :
26 : #define LG_FREE_ALL \
27 : { \
28 : LG_FREE_WORK \
29 : GrB_free (decomp) ; \
30 : }
31 :
32 : #include "LG_internal.h"
33 :
34 :
35 8 : int LAGraph_KCore
36 : (
37 : // outputs:
38 : GrB_Vector *decomp, // kcore decomposition
39 : // inputs:
40 : LAGraph_Graph G, // input graph
41 : uint64_t k, //k level to compare to
42 : char *msg
43 : )
44 : {
45 8 : LG_CLEAR_MSG ;
46 :
47 : // declare items
48 8 : GrB_Matrix A = NULL;
49 8 : GrB_Vector deg = NULL, q = NULL, done = NULL, delta = NULL;
50 :
51 8 : LG_ASSERT (decomp != NULL, GrB_NULL_POINTER) ;
52 7 : (*decomp) = NULL ;
53 :
54 7 : LG_TRY (LAGraph_CheckGraph (G, msg)) ;
55 :
56 6 : if (G->kind == LAGraph_ADJACENCY_UNDIRECTED ||
57 3 : (G->kind == LAGraph_ADJACENCY_DIRECTED &&
58 3 : G->is_symmetric_structure == LAGraph_TRUE))
59 : {
60 : // the structure of A is known to be symmetric
61 5 : A = G->A ;
62 : }
63 : else
64 : {
65 : // A is not known to be symmetric
66 1 : LG_ASSERT_MSG (false, -1005, "G->A must be symmetric") ;
67 : }
68 :
69 : // no self edges can be present
70 5 : LG_ASSERT_MSG (G->nself_edges == 0, -1004, "G->nself_edges must be zero") ;
71 :
72 : //create work scalars
73 : GrB_Index n, qnvals, degnvals, maxDeg;
74 4 : GRB_TRY (GrB_Matrix_nrows(&n, A)) ;
75 :
76 : //create deg vector using rowdegree property
77 4 : LG_TRY (LAGraph_Cached_OutDegree(G, msg)) ;
78 4 : GRB_TRY (GrB_Vector_dup(°, G->out_degree)) ; //original deg vector is technically 1-core since 0 is omitted
79 4 : GRB_TRY (GrB_Vector_nvals(°nvals, deg)) ;
80 :
81 : //retrieve the max degree level of the graph
82 4 : GRB_TRY (GrB_reduce(&maxDeg, GrB_NULL, GrB_MAX_MONOID_INT64, G->out_degree, GrB_NULL)) ;
83 :
84 : //select int type for work vectors and semirings
85 4 : GrB_Type int_type = (maxDeg > INT32_MAX) ? GrB_INT64 : GrB_INT32 ;
86 :
87 4 : GRB_TRY (GrB_Vector_new(&q, int_type, n));
88 4 : GRB_TRY (GrB_Vector_new(&done, GrB_BOOL, n)) ;
89 4 : GRB_TRY (GrB_Vector_new(&delta, int_type, n)) ;
90 : //set output to int64
91 4 : GRB_TRY (GrB_Vector_new(decomp, int_type, n)) ;
92 :
93 : //change deg vector to int32 if needed
94 4 : if(int_type == GrB_INT32){
95 4 : GRB_TRY (GrB_Vector_new(°, int_type, n)) ;
96 4 : GRB_TRY (GrB_assign (deg, G->out_degree, NULL, G->out_degree, GrB_ALL, n, NULL)) ;
97 : }
98 :
99 : // determine semiring types
100 4 : GrB_IndexUnaryOp valueLT = (maxDeg > INT32_MAX) ? GrB_VALUELT_INT64 : GrB_VALUELT_INT32 ;
101 4 : GrB_BinaryOp minus_op = (maxDeg > INT32_MAX) ? GrB_MINUS_INT64 : GrB_MINUS_INT32 ;
102 4 : GrB_Semiring semiring = (maxDeg > INT32_MAX) ? LAGraph_plus_one_int64 : LAGraph_plus_one_int32 ;
103 :
104 :
105 : #if LG_SUITESPARSE
106 : GRB_TRY (GxB_set (done, GxB_SPARSITY_CONTROL, GxB_BITMAP + GxB_FULL)) ; // try this
107 : //GRB_TRY (GxB_set (*decomp, GxB_SPARSITY_CONTROL, GxB_BITMAP + GxB_FULL)) ; // try this ... likely not needed
108 : #endif
109 :
110 : // Creating q
111 4 : GRB_TRY (GrB_select (q, GrB_NULL, GrB_NULL, valueLT, deg, k, GrB_NULL)) ; // get all nodes with degree = level
112 4 : GRB_TRY (GrB_Vector_nvals(&qnvals, q));
113 :
114 : // while q not empty
115 4 : int round = 0;
116 10 : while(qnvals > 0 && degnvals > 0){
117 6 : round++;
118 : //add anything in q as true into the done list
119 6 : GRB_TRY (GrB_assign (done, q, NULL, (bool) true, GrB_ALL, n, GrB_DESC_S)) ; //structure to take care of 0-node cases
120 :
121 : // Create delta (the nodes who lost friends, and how many they lost) (push version)
122 6 : GRB_TRY (GrB_vxm (delta, GrB_NULL, GrB_NULL, semiring, q, A, GrB_NULL));
123 :
124 : // Create new deg vector (keep anything not in done vector)
125 6 : GRB_TRY (GrB_eWiseAdd(deg, done, GrB_NULL, minus_op, deg, delta, GrB_DESC_RSC)) ;
126 :
127 : // Update q, set new nvals
128 6 : GRB_TRY (GrB_select (q, GrB_NULL, GrB_NULL, valueLT, deg, k, GrB_NULL)) ;
129 6 : GRB_TRY (GrB_Vector_nvals(&qnvals, q)) ;
130 6 : GRB_TRY (GrB_Vector_nvals(°nvals, deg)) ;
131 : }
132 : //Assign values of deg to decomp
133 4 : GRB_TRY (GrB_assign (*decomp, deg, NULL, k, GrB_ALL, n, GrB_NULL)) ;
134 4 : GRB_TRY(GrB_Vector_wait(*decomp, GrB_MATERIALIZE));
135 4 : LG_FREE_WORK ;
136 4 : return (GrB_SUCCESS) ;
137 : }
|
