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