Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LAGraph_EstimateDiameter: Graph Diameter Estimation
3 : //------------------------------------------------------------------------------
4 :
5 : // LAGraph, (c) 2021 by The LAGraph Contributors, All Rights Reserved.
6 : // SPDX-License-Identifier: BSD-2-Clause
7 : // See additional acknowledgments in the LICENSE file,
8 : // or contact permission@sei.cmu.edu for the full terms.
9 :
10 : // Contributed by Alexandra Goff
11 :
12 : //------------------------------------------------------------------------------
13 :
14 : // TODO: almost ready for src; need to handle GxB
15 :
16 : // Takes in a graph and estimates the diameter
17 : // and optionally also finds pseudo-peripheral nodes of the graph
18 :
19 : // Outputs:
20 : // Diameter returns the estimated diameter of the graph
21 : // If not set to NULL, peripheral will be a vector with n elements
22 : // index i of peripheral is the estimated diameter if it's a pseudo-peripheral node or nothing if not
23 :
24 : // Inputs:
25 : // G is the graph to be analyzed
26 : // maxSrcs limits the number of sources used each cycle
27 : // maxLoops limits the number of times the core loop will run if a stable diameter isn't found
28 : // msg is a buffer for error messages
29 :
30 : #define LG_FREE_WORK \
31 : { \
32 : GrB_free (&ecc) ; \
33 : GrB_free (&candidateSrcs) ; \
34 : GrB_free (&srcs) ; \
35 : GrB_free (&level) ; \
36 : GrB_free (&Mod) ; \
37 : LAGraph_Free((void**) &sourceIndicies, NULL); \
38 : LAGraph_Free((void**) &sourceValues, NULL); \
39 : }
40 :
41 : #define LG_FREE_ALL \
42 : { \
43 : LG_FREE_WORK ; \
44 : GrB_free (&peri) ; \
45 : }
46 :
47 : #include "LG_internal.h"
48 : #include "LAGraphX.h"
49 :
50 : void mod32 (int32_t *z, const int32_t *x, const int32_t *y) ;
51 64 : void mod32 (int32_t *z, const int32_t *x, const int32_t *y)
52 : {
53 : /* make sure x is positive */
54 64 : int32_t t = ((*x) > 0) ? (*x) : -(*x) ;
55 64 : (*z) = t % (*y) ;
56 64 : }
57 :
58 : #define MOD32_DEFN \
59 : "void mod32 (int32_t *z, const int32_t *x, const int32_t *y) \n" \
60 : "{ \n" \
61 : " /* make sure x is positive */ \n" \
62 : " int32_t t = ((*x) > 0) ? (*x) : -(*x) ; \n" \
63 : " (*z) = t % (*y) ; \n" \
64 : "}"
65 :
66 : void mod64 (int64_t *z, const int64_t *x, const int64_t *y) ;
67 8 : void mod64 (int64_t *z, const int64_t *x, const int64_t *y)
68 : {
69 : /* make sure x is positive */
70 8 : int64_t t = ((*x) > 0) ? (*x) : -(*x) ;
71 8 : (*z) = t % (*y) ;
72 8 : }
73 :
74 : #define MOD64_DEFN \
75 : "void mod64 (int64_t *z, const int64_t *x, const int64_t *y) \n" \
76 : "{ \n" \
77 : " /* make sure x is positive */ \n" \
78 : " int64_t t = ((*x) > 0) ? (*x) : -(*x) ; \n" \
79 : " (*z) = t % (*y) ; \n" \
80 : "}"
81 :
82 21 : int LAGraph_EstimateDiameter
83 : (
84 : // outputs:
85 : GrB_Index *diameter,
86 : GrB_Vector *peripheral,
87 : // inputs:
88 : const LAGraph_Graph G,
89 : GrB_Index maxSrcs,
90 : GrB_Index maxLoops,
91 : uint64_t seed, // seed for randomization
92 : char *msg
93 : )
94 : {
95 : #if LAGRAPH_SUITESPARSE
96 :
97 : //--------------------------------------------------------------------------
98 : // check inputs
99 : //--------------------------------------------------------------------------
100 :
101 21 : LG_CLEAR_MSG ;
102 21 : GrB_Vector ecc = NULL ; // the eccentricity of the nodes
103 21 : GrB_Vector peri = NULL ; // vector to store peripheral node status in
104 21 : GrB_Index d = 0 ; // current diameter
105 21 : GrB_Index lastd = 0 ; // previous diameter
106 21 : GrB_Vector srcs = NULL ; // list of current sources
107 : GrB_Index nsrcs ; // number of current sources
108 21 : GrB_Matrix level = NULL ; // matrix for msbfs to put level info in
109 21 : GrB_Vector candidateSrcs = NULL ; // work vector for getting sources for the next iteration of the loop
110 21 : GrB_BinaryOp Mod = NULL ;
111 :
112 21 : GrB_Index *sourceIndicies = NULL ;
113 21 : int64_t *sourceValues = NULL ; // just need this so extractTuples will run
114 :
115 21 : bool compute_periphery = (peripheral != NULL) ;
116 21 : if (compute_periphery ) (*peripheral) = NULL ;
117 21 : bool compute_diameter = (diameter != NULL) ;
118 21 : LG_ASSERT_MSG (compute_diameter, GrB_NULL_POINTER,
119 : "Diameter destination must be non-NULL") ;
120 :
121 21 : LG_TRY (LAGraph_CheckGraph (G, msg)) ;
122 :
123 : //--------------------------------------------------------------------------
124 : // get the problem size and cached properties
125 : //--------------------------------------------------------------------------
126 :
127 21 : GrB_Matrix A = G->A ;
128 :
129 : GrB_Index n; // number of nodes in the graph
130 21 : GRB_TRY (GrB_Matrix_nrows (&n, A)) ;
131 :
132 21 : GrB_Type int_type = (n > INT32_MAX) ? GrB_INT64 : GrB_INT32 ;
133 :
134 : //--------------------------------------------------------------------------
135 : // set up the first maxSrcs random nodes
136 : //--------------------------------------------------------------------------
137 :
138 : // currently just doing the first maxSrcs, consider different randomization
139 : // check maxSrcs < n
140 21 : if (maxSrcs > n)
141 : {
142 2 : nsrcs = n;
143 : }
144 : else
145 : {
146 19 : nsrcs = maxSrcs;
147 : }
148 21 : GRB_TRY (GrB_Vector_new (&srcs, int_type, nsrcs)) ;
149 : // srcs (0:nsrcs-1) = 0
150 21 : GRB_TRY (GrB_assign (srcs, NULL, NULL, 0, GrB_ALL, nsrcs, NULL)) ;
151 21 : if (nsrcs == n)
152 : {
153 : // srcs = 0:n-1
154 4 : GrB_IndexUnaryOp op =
155 4 : (n > INT32_MAX) ? GrB_ROWINDEX_INT64 : GrB_ROWINDEX_INT32 ;
156 4 : GRB_TRY (GrB_apply (srcs, NULL, NULL, op, srcs, 0, NULL)) ;
157 : }
158 : else
159 : {
160 : // srcs = randomized, still of size nsrcs-1, values in range 0 to UINT64_MAX
161 : // TODO: if the graph is very sparse, select nodes at random with at
162 : // least one out-going edge.
163 17 : LAGRAPH_TRY (LAGraph_Random_Seed (srcs, seed, msg)) ;
164 17 : GRB_TRY (GxB_BinaryOp_new (&Mod,
165 : (n > INT32_MAX) ? ((GxB_binary_function)mod64) :
166 : ((GxB_binary_function)mod32),
167 : int_type, int_type, int_type,
168 : (n > INT32_MAX) ? "mod64" : "mod32",
169 : (n > INT32_MAX) ? MOD64_DEFN : MOD32_DEFN)) ;
170 17 : GRB_TRY (GrB_apply (srcs, NULL, NULL, Mod, srcs, n, NULL)) ;
171 17 : GrB_free (&Mod) ;
172 : }
173 :
174 : //--------------------------------------------------------------------------
175 : // core loop, run until current and previous diameters match or reach given limit
176 : //--------------------------------------------------------------------------
177 :
178 21 : GrB_Monoid max =
179 21 : (n > INT32_MAX) ? GrB_MAX_MONOID_INT64 : GrB_MAX_MONOID_INT32 ;
180 21 : GrB_IndexUnaryOp eqOp =
181 21 : (n > INT32_MAX) ? GrB_VALUEEQ_INT64 : GrB_VALUEEQ_INT32 ;
182 21 : bool incSrcs = false;
183 45 : for (int64_t i = 0; i < maxLoops; i++)
184 : {
185 : // save previous diameter
186 45 : lastd = d;
187 :
188 : // get new diameter
189 45 : GrB_free (&level) ;
190 45 : LG_TRY (LAGraph_MultiSourceBFS(&level, NULL, G, srcs, msg)) ;
191 45 : GrB_free (&ecc) ;
192 45 : GRB_TRY (GrB_Vector_new (&ecc, int_type, n)) ;
193 45 : GRB_TRY (GrB_reduce(ecc, NULL, NULL, max, level, GrB_DESC_T0)) ;
194 45 : GRB_TRY (GrB_reduce(&d, NULL, max, ecc, GrB_NULL)) ;
195 45 : GrB_free (&level) ;
196 :
197 : // check if done
198 45 : if (d == lastd){
199 21 : incSrcs = true;
200 21 : break;
201 : }
202 :
203 : // now with fewer for loops
204 : // said in last discussion: remaining for loop fine because of batch processing?
205 :
206 : // set up source list for next round
207 : // get the number of peripheral nodes
208 24 : GrB_Index nperi = 0;
209 24 : GRB_TRY (GrB_Vector_new (&candidateSrcs, int_type, n)) ;
210 24 : GRB_TRY (GrB_select(candidateSrcs, NULL, NULL, eqOp, ecc, d, NULL)) ;
211 24 : GRB_TRY (GrB_Vector_nvals(&nperi, candidateSrcs)) ;
212 :
213 :
214 : // select the number of sources
215 24 : if (nperi > maxSrcs) {
216 4 : nsrcs = maxSrcs;
217 : } else {
218 20 : nsrcs = nperi;
219 : }
220 :
221 : // choose sources
222 24 : GrB_free (&srcs) ;
223 24 : GRB_TRY (GrB_Vector_new (&srcs, int_type, nsrcs)) ;
224 :
225 24 : GRB_TRY (LAGraph_Calloc((void **) &sourceIndicies, nperi, sizeof(GrB_Index), msg)) ;
226 24 : GRB_TRY (LAGraph_Calloc((void **) &sourceValues, nperi, sizeof(int64_t), msg)) ;
227 24 : GRB_TRY (GrB_Vector_extractTuples(sourceIndicies, sourceValues, &nperi, candidateSrcs)) ;
228 126 : for (int64_t j = 0; j < nsrcs; j++) {
229 102 : GRB_TRY (GrB_Vector_setElement (srcs, sourceIndicies[j], j)) ;
230 : }
231 24 : LAGraph_Free((void**) &sourceIndicies, NULL);
232 24 : LAGraph_Free((void**) &sourceValues, NULL);
233 24 : GrB_free(&candidateSrcs) ;
234 : }
235 :
236 : //--------------------------------------------------------------------------
237 : // after loop, set up peripheral nodes if needed
238 : //--------------------------------------------------------------------------
239 21 : if (compute_periphery) {
240 21 : GRB_TRY (GrB_Vector_new (&peri, int_type, n)) ;
241 :
242 21 : GRB_TRY (GrB_select(peri, NULL, NULL, eqOp, ecc, d, NULL)) ;
243 :
244 21 : if (incSrcs) {
245 111 : for (int64_t i = 0; i < nsrcs; i++) {
246 : GrB_Index currsrc;
247 90 : GRB_TRY(GrB_Vector_extractElement(&currsrc, srcs, i));
248 90 : GRB_TRY (GrB_Vector_setElement (peri, d, currsrc)) ;
249 : }
250 : }
251 :
252 :
253 : }
254 :
255 : //--------------------------------------------------------------------------
256 : // free workspace and return result
257 : //--------------------------------------------------------------------------
258 :
259 21 : if (compute_periphery) (*peripheral) = peri ;
260 21 : (*diameter ) = d ;
261 21 : LG_FREE_WORK ;
262 21 : return (GrB_SUCCESS) ;
263 : #else
264 : return (GrB_NOT_IMPLEMENTED) ;
265 : #endif
266 : }
|
