Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LAGraph/src/test/test_Betweenness.c: test cases for BC (GAP 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 Timothy A. Davis, Texas A&M University
15 :
16 : //------------------------------------------------------------------------------
17 :
18 : #include <stdio.h>
19 : #include <acutest.h>
20 :
21 : #include <LAGraph_test.h>
22 :
23 : #define LEN 512
24 : char msg [LAGRAPH_MSG_LEN] ;
25 : char filename [LEN+1] ;
26 : LAGraph_Graph G = NULL ;
27 :
28 : //------------------------------------------------------------------------------
29 : // difference: compare the LAGraph and GAP results
30 : //------------------------------------------------------------------------------
31 :
32 : float difference (GrB_Vector bc, double *gap_result) ;
33 :
34 3 : float difference (GrB_Vector bc, double *gap_result)
35 : {
36 3 : GrB_Vector diff = NULL, gap_bc = NULL ;
37 3 : GrB_Index n = 0 ;
38 3 : OK (GrB_Vector_size (&n, bc)) ;
39 3 : OK (GrB_Vector_new (&gap_bc, GrB_FP32, n)) ;
40 138 : for (int i = 0 ; i < n ; i++)
41 : {
42 135 : OK (GrB_Vector_setElement_FP64 (gap_bc, gap_result [i], i)) ;
43 : }
44 : // diff = max (abs (gap_bc - bc))
45 3 : OK (GrB_Vector_new (&diff, GrB_FP32, n)) ;
46 3 : OK (GrB_eWiseAdd (diff, NULL, NULL, GrB_MINUS_FP32, gap_bc, bc,
47 : NULL)) ;
48 3 : OK (GrB_apply (diff, NULL, NULL, GrB_ABS_FP32, diff, NULL)) ;
49 3 : float err = 0 ;
50 3 : OK (GrB_reduce (&err, NULL, GrB_MAX_MONOID_FP32, diff, NULL)) ;
51 3 : OK (GrB_free (&diff)) ;
52 3 : OK (GrB_free (&gap_bc)) ;
53 3 : return (err) ;
54 : }
55 :
56 : //------------------------------------------------------------------------------
57 : // results for karate graph
58 : //------------------------------------------------------------------------------
59 :
60 : // Results obtained from GAP/bc.cc, but with each source node reduce by n-1
61 : // where n is the # of nodes in the graph, and prior to normalization.
62 : // (The GAP benchmark results are incorrect for the 4 source nodes, since the
63 : // score includes n-1 paths of length zero, which LAGraph excludes).
64 :
65 : // Read Time: 0.00770
66 : // Build Time: 0.00021
67 : // Graph has 34 nodes and 156 directed edges for degree: 4
68 : // Read Time: 0.00163
69 : // Graph has 34 nodes and 156 directed edges for degree: 4
70 : // a 0.00001
71 : // source: 6
72 : // b 0.00143
73 : // p 0.00118
74 : // source: 29
75 : // b 0.00012
76 : // p 0.00010
77 : // source: 0
78 : // b 0.00009
79 : // p 0.00007
80 : // source: 9
81 : // b 0.00010
82 : // p 0.00008
83 :
84 : GrB_Index karate_sources [4] = { 6, 29, 0, 9 } ;
85 :
86 : double karate_bc [34] = {
87 : 43.7778,
88 : 2.83333,
89 : 26.9143,
90 : 0.722222,
91 : 0.333333,
92 : 1.83333,
93 : 1.5,
94 : 0,
95 : 9.09524,
96 : 0,
97 : 0,
98 : 0,
99 : 0,
100 : 5.19206,
101 : 0,
102 : 0,
103 : 0,
104 : 0,
105 : 0,
106 : 4.58095,
107 : 0,
108 : 0,
109 : 0,
110 : 2.4,
111 : 0,
112 : 0.422222,
113 : 0,
114 : 1.28889,
115 : 0,
116 : 0,
117 : 0.733333,
118 : 14.5508,
119 : 17.1873,
120 : 40.6349 } ;
121 :
122 : // Trial Time: 0.00369
123 : // Average Time: 0.00369
124 :
125 : //------------------------------------------------------------------------------
126 : // results for west0067 graph
127 : //------------------------------------------------------------------------------
128 :
129 : // Read Time: 0.00213
130 : // Build Time: 0.00019
131 : // Graph has 67 nodes and 292 directed edges for degree: 4
132 : // Read Time: 0.00158
133 : // Graph has 67 nodes and 292 directed edges for degree: 4
134 : // a 0.00001
135 : // source: 13
136 : // b 0.00285
137 : // p 0.00013
138 : // source: 58
139 : // b 0.00028
140 : // p 0.00515
141 : // source: 1
142 : // b 0.00015
143 : // p 0.00012
144 : // source: 18
145 : // b 0.00012
146 : // p 0.00009
147 :
148 : GrB_Index west0067_sources [4] = { 13, 58, 1, 18 } ;
149 :
150 : double west0067_bc [67] = {
151 : 7.37262,
152 : 5.3892,
153 : 4.53788,
154 : 3.25952,
155 : 11.9139,
156 : 5.73571,
157 : 5.65336,
158 : 1.5,
159 : 19.2719,
160 : 0.343137,
161 : 0.0833333,
162 : 0.666667,
163 : 1.80882,
164 : 12.4246,
165 : 1.92647,
166 : 22.0458,
167 : 4.7381,
168 : 34.8611,
169 : 0.1,
170 : 29.8358,
171 : 9.52807,
172 : 9.71836,
173 : 17.3334,
174 : 54.654,
175 : 23.3118,
176 : 7.31765,
177 : 2.52381,
178 : 6.96905,
179 : 19.2291,
180 : 6.97003,
181 : 33.0464,
182 : 7.20128,
183 : 3.78571,
184 : 7.87698,
185 : 15.3556,
186 : 7.43333,
187 : 7.19091,
188 : 9.20411,
189 : 1.10325,
190 : 6.38095,
191 : 17.808,
192 : 5.18172,
193 : 25.8441,
194 : 7.91581,
195 : 1.13501,
196 : 0,
197 : 2.53004,
198 : 2.48168,
199 : 8.84857,
200 : 3.80708,
201 : 1.16978,
202 : 0.0714286,
203 : 1.76786,
204 : 3.06661,
205 : 12.0742,
206 : 1.6,
207 : 4.73908,
208 : 2.3701,
209 : 3.75,
210 : 1.08571,
211 : 1.69697,
212 : 0,
213 : 0.571429,
214 : 0,
215 : 0,
216 : 2.22381,
217 : 0.659341 } ;
218 :
219 : // Trial Time: 0.00912
220 : // Average Time: 0.00912
221 :
222 : //------------------------------------------------------------------------------
223 : // test_bc
224 : //------------------------------------------------------------------------------
225 :
226 1 : void test_bc (void)
227 : {
228 1 : LAGraph_Init (msg) ;
229 1 : GrB_Matrix A = NULL ;
230 1 : GrB_Vector centrality = NULL ;
231 1 : int niters = 0 ;
232 :
233 : // create the karate graph
234 1 : snprintf (filename, LEN, LG_DATA_DIR "%s", "karate.mtx") ;
235 1 : FILE *f = fopen (filename, "r") ;
236 1 : TEST_CHECK (f != NULL) ;
237 1 : OK (LAGraph_MMRead (&A, f, msg)) ;
238 1 : OK (fclose (f)) ;
239 1 : OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_UNDIRECTED, msg)) ;
240 1 : TEST_CHECK (A == NULL) ; // A has been moved into G->A
241 :
242 : // compute its betweenness centrality
243 1 : OK (LAGr_Betweenness (¢rality, G, karate_sources, 4, msg)) ;
244 1 : printf ("\nkarate bc:\n") ;
245 1 : OK (LAGraph_Delete (&G, msg)) ;
246 :
247 : // compare with GAP:
248 1 : float err = difference (centrality, karate_bc) ;
249 1 : printf ("karate: err: %e\n", err) ;
250 1 : TEST_CHECK (err < 1e-4) ;
251 1 : OK (GrB_free (¢rality)) ;
252 :
253 : // create the west0067 graph
254 1 : snprintf (filename, LEN, LG_DATA_DIR "%s", "west0067.mtx") ;
255 1 : f = fopen (filename, "r") ;
256 1 : TEST_CHECK (f != NULL) ;
257 1 : OK (LAGraph_MMRead (&A, f, msg)) ;
258 1 : OK (fclose (f)) ;
259 1 : OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_DIRECTED, msg)) ;
260 1 : TEST_CHECK (A == NULL) ; // A has been moved into G->A
261 1 : OK (LAGraph_Cached_AT (G, msg)) ;
262 :
263 : // compute its betweenness centrality
264 1 : OK (LAGr_Betweenness (¢rality, G, west0067_sources, 4, msg)) ;
265 1 : printf ("\nwest0067 bc:\n") ;
266 1 : OK (LAGraph_Delete (&G, msg)) ;
267 :
268 : // compare with GAP:
269 1 : err = difference (centrality, west0067_bc) ;
270 1 : printf ("west0067: err: %e\n", err) ;
271 1 : TEST_CHECK (err < 1e-4) ;
272 1 : OK (GrB_free (¢rality)) ;
273 :
274 1 : LAGraph_Finalize (msg) ;
275 1 : }
276 :
277 : //------------------------------------------------------------------------------
278 : // test_bc_brutal: test BetweenessCentraliy with brutal malloc debugging
279 : //------------------------------------------------------------------------------
280 :
281 : #if LAGRAPH_SUITESPARSE
282 1 : void test_bc_brutal (void)
283 : {
284 1 : OK (LG_brutal_setup (msg)) ;
285 :
286 1 : GrB_Matrix A = NULL ;
287 1 : GrB_Vector centrality = NULL ;
288 1 : int niters = 0 ;
289 :
290 : // create the karate graph
291 1 : snprintf (filename, LEN, LG_DATA_DIR "%s", "karate.mtx") ;
292 1 : FILE *f = fopen (filename, "r") ;
293 1 : TEST_CHECK (f != NULL) ;
294 1 : OK (LAGraph_MMRead (&A, f, msg)) ;
295 1 : OK (fclose (f)) ;
296 1 : OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_UNDIRECTED, msg)) ;
297 1 : TEST_CHECK (A == NULL) ; // A has been moved into G->A
298 1 : printf ("\n") ;
299 :
300 : // compute its betweenness centrality
301 141 : LG_BRUTAL_BURBLE (LAGr_Betweenness (¢rality, G,
302 : karate_sources, 4, msg)) ;
303 :
304 : // compare with GAP:
305 1 : float err = difference (centrality, karate_bc) ;
306 1 : printf ("karate: err: %e\n", err) ;
307 1 : TEST_CHECK (err < 1e-4) ;
308 1 : OK (GrB_free (¢rality)) ;
309 1 : OK (LAGraph_Delete (&G, msg)) ;
310 :
311 1 : OK (LG_brutal_teardown (msg)) ;
312 1 : }
313 : #endif
314 :
315 : //------------------------------------------------------------------------------
316 : // list of tests
317 : //------------------------------------------------------------------------------
318 :
319 : TEST_LIST = {
320 : {"test_bc", test_bc},
321 : #if LAGRAPH_SUITESPARSE
322 : {"test_bc_brutal", test_bc_brutal },
323 : #endif
324 : {NULL, NULL}
325 : };
|
