Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LG_check_kcore: construct the kcore of a graph (simple method)
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 : // An implementation of the BZ algorithm (2003) for k-core decomposition.
19 : // This method is for testing only, to check the result of other, faster methods.
20 : // Do not benchmark this method; it is simple by design.
21 :
22 : #define LG_FREE_ALL \
23 : { \
24 : LAGraph_Free ((void **) &vert, msg) ; \
25 : LAGraph_Free ((void **) °, msg) ; \
26 : LAGraph_Free ((void **) &bin, msg) ; \
27 : LAGraph_Free ((void **) &pos, msg) ; \
28 : LAGraph_Free ((void **) &Ap, msg) ; \
29 : LAGraph_Free ((void **) &Aj, msg) ; \
30 : LAGraph_Free ((void **) &Ax, msg) ; \
31 : }
32 :
33 : #include "LG_internal.h"
34 : #include "LG_test.h"
35 : #include "LG_Xtest.h"
36 :
37 4 : int LG_check_kcore
38 : (
39 : // outputs:
40 : GrB_Vector *decomp, // kcore decomposition
41 : uint64_t *kmax, // max kcore- if kfinal == -1, kmax = -1
42 : // inputs
43 : LAGraph_Graph G, // input graph
44 : int64_t kfinal, // max k to check for graph.
45 : char *msg
46 : )
47 : {
48 :
49 : //--------------------------------------------------------------------------
50 : // check inputs
51 : //--------------------------------------------------------------------------
52 :
53 4 : LG_CLEAR_MSG ;
54 4 : uint64_t *vert = NULL, *pos = NULL, *bin = NULL, *deg = NULL ;
55 4 : uint64_t maxDeg = 0;
56 4 : GrB_Index *Ap = NULL, *Aj = NULL, *Ai = NULL ;
57 4 : void *Ax = NULL ;
58 : GrB_Index Ap_size, Aj_size, Ax_size, n, ncols, Ap_len, Aj_len, Ax_len ;
59 4 : LG_ASSERT (kmax != NULL, GrB_NULL_POINTER) ;
60 4 : LG_TRY (LAGraph_CheckGraph (G, msg)) ;
61 4 : LG_ASSERT (G->nself_edges == 0, LAGRAPH_NO_SELF_EDGES_ALLOWED) ;
62 4 : LG_ASSERT_MSG ((G->kind == LAGraph_ADJACENCY_UNDIRECTED ||
63 : (G->kind == LAGraph_ADJACENCY_DIRECTED &&
64 : G->is_symmetric_structure == LAGraph_TRUE)),
65 : LAGRAPH_SYMMETRIC_STRUCTURE_REQUIRED,
66 : "G->A must be known to be symmetric") ;
67 4 : GRB_TRY (GrB_Matrix_nrows (&n, G->A)) ; //set n to number of rows
68 4 : GRB_TRY (GrB_Matrix_ncols (&ncols, G->A)) ;
69 :
70 : //--------------------------------------------------------------------------
71 : // export the matrix in CSR form
72 : //--------------------------------------------------------------------------
73 :
74 : size_t typesize ;
75 4 : LG_TRY (LG_check_export (G, &Ap, &Aj, &Ax, &Ap_len, &Aj_len, &Ax_len,
76 : &typesize, msg)) ;
77 :
78 : //--------------------------------------------------------------------------
79 : // compute the k-core
80 : //--------------------------------------------------------------------------
81 : //printf ("\n================================== COMPUTING BZ_KCORE: ==================================\n") ;
82 : //printf("ap_len = %ld, aj_len = %ld, ax_len = %ld\n", Ap_len, Aj_len, Ax_len) ;
83 :
84 : //create the arrays
85 :
86 4 : LAGraph_Malloc((void **) °, n, sizeof(uint64_t), msg) ;
87 4 : LAGraph_Malloc((void **) &vert, n, sizeof(uint64_t), msg) ;
88 4 : LAGraph_Malloc((void **) &pos, n, sizeof(uint64_t), msg) ;
89 : //core = AGraph_Malloc(n, sizeof(uint64_t)) ;
90 :
91 206 : for(uint64_t i = 0; i < n; i++){
92 202 : deg[i] = Ap[i+1] - Ap[i];
93 202 : if (deg[i] > maxDeg)
94 12 : maxDeg = deg[i];
95 : }
96 :
97 : //setup output vector
98 4 : GrB_Type int_type = (maxDeg > INT32_MAX) ? GrB_INT64 : GrB_INT32 ;
99 4 : GRB_TRY (GrB_Vector_new(decomp, int_type, n)) ;
100 4 : GrB_IndexUnaryOp valueGE = (maxDeg > INT32_MAX) ? GrB_VALUEGE_INT64 : GrB_VALUEGE_INT32 ;
101 :
102 : //setup bin array
103 4 : LAGraph_Calloc((void **) &bin, maxDeg + 1, sizeof(uint64_t), msg) ;
104 :
105 206 : for(uint64_t i = 0; i < n; i++){
106 202 : bin[deg[i]]++;
107 : }
108 :
109 4 : uint64_t start = 0;
110 74 : for(uint64_t d = 0; d < maxDeg + 1; d++){
111 70 : uint64_t num = bin[d];
112 70 : bin[d] = start;
113 70 : start = start + num;
114 : }
115 :
116 : //Do bin-sort
117 : //vert -- contains the vertices in sorted order of degree
118 : //pos -- contains the positon of a vertex in vert array
119 206 : for(uint64_t i = 0; i < n; i++){
120 202 : pos[i] = bin[ deg[i] ];
121 202 : vert[pos[i]] = i;
122 202 : bin[deg[i]] ++;
123 : }
124 :
125 70 : for(uint64_t d = maxDeg; d >= 1; d --)
126 66 : bin[d] = bin[d-1];
127 4 : bin[0] = 0;
128 :
129 4 : uint64_t level = 0;
130 :
131 : //Compute k-core
132 206 : for(uint64_t i = 0; i < n; i++){
133 : //get the vertex to check
134 202 : uint64_t v = vert[i];
135 :
136 : //set the element in the output vector: if doing KCALL, then add deg.
137 : //If not, just set to kfinal's value.
138 202 : if((int64_t) deg[v] >= kfinal){
139 201 : if(kfinal == -1){
140 101 : GRB_TRY(GrB_Vector_setElement(*decomp, deg[v], v)) ;
141 : }
142 : else{
143 100 : GRB_TRY(GrB_Vector_setElement(*decomp, kfinal, v)) ;
144 : }
145 : }
146 :
147 202 : if(bin[deg[v]] == i){
148 12 : level = deg[v];
149 : }
150 :
151 202 : uint64_t start = Ap[v];
152 202 : int64_t original_deg = Ap[v+1] - Ap[v]; //original deg before decremented
153 1662 : for(uint64_t j = 0; j < original_deg; j++){
154 1460 : uint64_t u = Aj[start + j]; //a neighbor node of v
155 :
156 : //if we need to lower the neighbor's deg value, and relocate in bin
157 1460 : if(deg[u] > deg[v]){
158 462 : uint64_t du = deg[u];
159 462 : uint64_t pu = pos[u];
160 462 : uint64_t pw = bin[du];
161 462 : uint64_t w = vert[pw]; //the vertex situated at the beginning of the bin
162 :
163 : //swap around the vertices- w goes to the end, u goes to the beginning
164 462 : if(u != w){
165 296 : pos[u] = pw; vert[pu] = w;
166 296 : pos[w] = pu; vert[pw] = u;
167 : }
168 :
169 : //increase starting index of bin @ du
170 462 : bin[du]++;
171 : //decrease degree of u
172 462 : deg[u]--;
173 : }
174 : }
175 : }
176 :
177 4 : LG_FREE_ALL;
178 4 : (*kmax) = level ;
179 4 : GRB_TRY (GrB_Vector_wait(*decomp, GrB_MATERIALIZE));
180 4 : return (GrB_SUCCESS);
181 : }
|
