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 : #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 6 : int LAGraph_KCore_All
36 : (
37 : // outputs:
38 : GrB_Vector *decomp, // kcore decomposition
39 : uint64_t *kmax,
40 : // inputs:
41 : LAGraph_Graph G, // input graph
42 : char *msg
43 : )
44 : {
45 6 : LG_CLEAR_MSG ;
46 :
47 : // declare items
48 6 : GrB_Matrix A = NULL;
49 6 : GrB_Vector deg = NULL, q = NULL, done = NULL, delta = NULL;
50 :
51 6 : LG_ASSERT (decomp != NULL, GrB_NULL_POINTER) ;
52 5 : (*decomp) = NULL ;
53 :
54 5 : LG_TRY (LAGraph_CheckGraph (G, msg)) ;
55 :
56 4 : if (G->kind == LAGraph_ADJACENCY_UNDIRECTED ||
57 2 : (G->kind == LAGraph_ADJACENCY_DIRECTED &&
58 2 : G->is_symmetric_structure == LAGraph_TRUE))
59 : {
60 : // the structure of A is known to be symmetric
61 3 : 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 3 : LG_ASSERT_MSG (G->nself_edges == 0, -1004, "G->nself_edges must be zero") ;
71 :
72 : //create work scalars
73 2 : uint64_t level = 0; //don't set at 1 in case of empty graph getting returned as kmax = 1
74 : GrB_Index n, todo, nvals, maxDeg ;
75 2 : GRB_TRY (GrB_Matrix_nrows(&n, A)) ;
76 :
77 : //create deg vector using out_degree property
78 2 : LG_TRY (LAGraph_Cached_OutDegree(G, msg)) ;
79 :
80 2 : GRB_TRY (GrB_Vector_dup(°, G->out_degree)) ; //original deg vector is technically 1-core since 0 is omitted
81 2 : GRB_TRY (GrB_Vector_nvals(&todo, deg)) ; //use todo instead of n since some values are omitted (1-core)
82 :
83 : //retrieve the max degree level of the graph
84 2 : GRB_TRY (GrB_reduce(&maxDeg, GrB_NULL, GrB_MAX_MONOID_INT64, G->out_degree, GrB_NULL)) ;
85 :
86 : //select int type for work vectors and semirings
87 2 : GrB_Type int_type = (maxDeg > INT32_MAX) ? GrB_INT64 : GrB_INT32 ;
88 :
89 2 : GRB_TRY (GrB_Vector_new(&q, int_type, n));
90 2 : GRB_TRY (GrB_Vector_new(&done, GrB_BOOL, n)) ;
91 2 : GRB_TRY (GrB_Vector_new(&delta, int_type, n)) ;
92 : //set output to int64
93 2 : GRB_TRY (GrB_Vector_new(decomp, int_type, n)) ;
94 :
95 : //change deg vector to int32 if needed
96 2 : if(int_type == GrB_INT32){
97 2 : GrB_free (°) ;
98 2 : GRB_TRY (GrB_Vector_new(°, int_type, n)) ;
99 2 : GRB_TRY (GrB_assign (deg, G->out_degree, NULL, G->out_degree, GrB_ALL, n, NULL)) ;
100 : }
101 :
102 : // determine semiring types
103 2 : GrB_IndexUnaryOp valueEQ = (maxDeg > INT32_MAX) ? GrB_VALUEEQ_INT64 : GrB_VALUEEQ_INT32 ;
104 2 : GrB_IndexUnaryOp valueLE = (maxDeg > INT32_MAX) ? GrB_VALUELE_INT64 : GrB_VALUELE_INT32 ;
105 2 : GrB_BinaryOp minus_op = (maxDeg > INT32_MAX) ? GrB_MINUS_INT64 : GrB_MINUS_INT32 ;
106 2 : GrB_Semiring semiring = (maxDeg > INT32_MAX) ? LAGraph_plus_one_int64 : LAGraph_plus_one_int32 ;
107 :
108 : #if LG_SUITESPARSE
109 : GRB_TRY (GxB_set (done, GxB_SPARSITY_CONTROL, GxB_BITMAP + GxB_FULL)) ; // try this
110 : //GRB_TRY (GxB_set (*decomp, GxB_SPARSITY_CONTROL, GxB_BITMAP + GxB_FULL)) ; // try this ... likely not needed...
111 : #endif
112 :
113 : //printf ("\n================================== COMPUTING GrB_KCORE: ==================================\n") ;
114 12 : while(todo > 0){
115 : //printf("Level: %ld, todo: %ld\n", level, todo) ;
116 10 : level++;
117 : // Creating q
118 10 : GRB_TRY (GrB_select (q, GrB_NULL, GrB_NULL, valueEQ, deg, level, GrB_NULL)) ; // get all nodes with degree = level
119 10 : GRB_TRY (GrB_Vector_nvals(&nvals, q));
120 :
121 : //Assign values of deg into decomp (output)
122 10 : GRB_TRY (GrB_assign (*decomp, deg, NULL, level, GrB_ALL, n, GrB_NULL)) ;
123 :
124 10 : int round = 0;
125 : // while q not empty
126 24 : while(nvals > 0){
127 : // Decrease todo by number of nvals
128 14 : todo = todo - nvals ;
129 : //add anything in q as true into the done list
130 14 : GRB_TRY (GrB_assign (done, q, NULL, (bool) true, GrB_ALL, n, GrB_DESC_S)) ; //structure to take care of 0-node cases
131 :
132 : // Create delta (the nodes who lost friends, and how many they lost)
133 14 : 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 w/ replace command)
136 14 : GRB_TRY (GrB_eWiseAdd(deg, done, GrB_NULL, minus_op, deg, delta, GrB_DESC_RSC /* try GrB_DESC_RSC */)) ;
137 :
138 : // Update q, set new nvals
139 14 : GRB_TRY (GrB_select (q, GrB_NULL, GrB_NULL, valueLE, deg, level, GrB_NULL)) ;
140 :
141 14 : GRB_TRY (GrB_Vector_nvals(&nvals, q)) ;
142 14 : round++;
143 : }
144 : }
145 : //set kmax
146 2 : (*kmax) = level;
147 :
148 2 : LG_FREE_WORK ;
149 2 : return (GrB_SUCCESS) ;
150 : }
|
