Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LAGraph/src/test/test_PageRank.c: test cases for pagerank
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 <LAGraphX.h>
22 : #include <LAGraph_test.h>
23 : #include "LG_Xtest.h"
24 :
25 : #define LEN 512
26 : char msg [LAGRAPH_MSG_LEN] ;
27 : char filename [LEN+1] ;
28 : LAGraph_Graph G = NULL ;
29 :
30 : //------------------------------------------------------------------------------
31 : // difference: compare the LAGraph and MATLAB results
32 : //------------------------------------------------------------------------------
33 :
34 : float difference (GrB_Vector centrality, double *matlab_result) ;
35 :
36 6 : float difference (GrB_Vector centrality, double *matlab_result)
37 : {
38 6 : GrB_Vector diff = NULL, cmatlab = NULL ;
39 6 : GrB_Index n = 0 ;
40 6 : OK (GrB_Vector_size (&n, centrality)) ;
41 6 : OK (GrB_Vector_new (&cmatlab, GrB_FP32, n)) ;
42 228 : for (int i = 0 ; i < n ; i++)
43 : {
44 222 : OK (GrB_Vector_setElement_FP64 (cmatlab, matlab_result [i], i)) ;
45 : }
46 : // diff = max (abs (cmatlab - centrality))
47 6 : OK (GrB_Vector_new (&diff, GrB_FP32, n)) ;
48 6 : OK (GrB_eWiseAdd (diff, NULL, NULL, GrB_MINUS_FP32, cmatlab, centrality,
49 : NULL)) ;
50 6 : OK (GrB_apply (diff, NULL, NULL, GrB_ABS_FP32, diff, NULL)) ;
51 6 : float err = 0 ;
52 6 : OK (GrB_reduce (&err, NULL, GrB_MAX_MONOID_FP32, diff, NULL)) ;
53 6 : OK (GrB_free (&diff)) ;
54 6 : OK (GrB_free (&cmatlab)) ;
55 6 : return (err) ;
56 : }
57 :
58 : //------------------------------------------------------------------------------
59 : // valid results for karate graph and west0067 graphs
60 : //------------------------------------------------------------------------------
61 :
62 : // The first two matrices have no sinks (nodes with zero outdegree) so the
63 : // MATLAB centrality (G, 'pagerank') and LAGr_PageRank
64 : // results will be essentially the same.
65 :
66 : // MATLAB computes in double precision, while LAGraph_*PageRank* computes in
67 : // single precision, so the difference will be about 1e-5 or so.
68 :
69 : double karate_rank [34] = {
70 : 0.0970011147,
71 : 0.0528720584,
72 : 0.0570750515,
73 : 0.0358615175,
74 : 0.0219857202,
75 : 0.0291233505,
76 : 0.0291233505,
77 : 0.0244945048,
78 : 0.0297681451,
79 : 0.0143104668,
80 : 0.0219857202,
81 : 0.0095668739,
82 : 0.0146475355,
83 : 0.0295415677,
84 : 0.0145381625,
85 : 0.0145381625,
86 : 0.0167900065,
87 : 0.0145622041,
88 : 0.0145381625,
89 : 0.0196092670,
90 : 0.0145381625,
91 : 0.0145622041,
92 : 0.0145381625,
93 : 0.0315206825,
94 : 0.0210719482,
95 : 0.0210013837,
96 : 0.0150430281,
97 : 0.0256382216,
98 : 0.0195723309,
99 : 0.0262863139,
100 : 0.0245921424,
101 : 0.0371606178,
102 : 0.0716632142,
103 : 0.1008786453 } ;
104 :
105 : double west0067_rank [67] = {
106 : 0.0233753869,
107 : 0.0139102552,
108 : 0.0123441027,
109 : 0.0145657095,
110 : 0.0142018541,
111 : 0.0100791606,
112 : 0.0128753395,
113 : 0.0143945684,
114 : 0.0110203141,
115 : 0.0110525383,
116 : 0.0119311961,
117 : 0.0072382247,
118 : 0.0188680398,
119 : 0.0141596605,
120 : 0.0174877889,
121 : 0.0170362099,
122 : 0.0120433909,
123 : 0.0219844489,
124 : 0.0195274443,
125 : 0.0394465722,
126 : 0.0112038726,
127 : 0.0090174094,
128 : 0.0140088120,
129 : 0.0122532937,
130 : 0.0153346283,
131 : 0.0135241334,
132 : 0.0158714693,
133 : 0.0149689529,
134 : 0.0144097230,
135 : 0.0137583019,
136 : 0.0314386080,
137 : 0.0092857745,
138 : 0.0081814168,
139 : 0.0102137827,
140 : 0.0096547214,
141 : 0.0129622400,
142 : 0.0244173417,
143 : 0.0173963657,
144 : 0.0127705717,
145 : 0.0143297446,
146 : 0.0140509341,
147 : 0.0104117131,
148 : 0.0173516407,
149 : 0.0149175105,
150 : 0.0119979624,
151 : 0.0095043613,
152 : 0.0153295328,
153 : 0.0077710930,
154 : 0.0259969472,
155 : 0.0126926269,
156 : 0.0088870166,
157 : 0.0080836101,
158 : 0.0096023576,
159 : 0.0091000837,
160 : 0.0246131958,
161 : 0.0159589365,
162 : 0.0183500031,
163 : 0.0155811507,
164 : 0.0157693756,
165 : 0.0116319823,
166 : 0.0230649292,
167 : 0.0149070613,
168 : 0.0157469640,
169 : 0.0134396036,
170 : 0.0189218603,
171 : 0.0114528518,
172 : 0.0223213267 } ;
173 :
174 : // ldbc-directed-example.mtx has two sinks: nodes 3 and 9
175 : // its pagerank must be computed with LAGr_PageRank.
176 : double ldbc_directed_example_rank [10] = {
177 : 0.1697481823,
178 : 0.0361514465,
179 : 0.1673241104,
180 : 0.1669092572,
181 : 0.1540948145,
182 : 0.0361514465,
183 : 0.0361514465,
184 : 0.1153655134,
185 : 0.0361514465,
186 : 0.0819523364 } ;
187 :
188 : //------------------------------------------------------------------------------
189 : // tesk_ranker
190 : //------------------------------------------------------------------------------
191 :
192 1 : void test_ranker(void)
193 : {
194 1 : LAGraph_Init (msg) ;
195 1 : GrB_Matrix A = NULL ;
196 1 : GrB_Vector centrality = NULL, cmatlab = NULL, diff = NULL ;
197 1 : int niters = 0 ;
198 :
199 : //--------------------------------------------------------------------------
200 : // karate: no sinks
201 : //--------------------------------------------------------------------------
202 :
203 : // create the karate graph
204 1 : snprintf (filename, LEN, LG_DATA_DIR "%s", "karate.mtx") ;
205 1 : FILE *f = fopen (filename, "r") ;
206 1 : TEST_CHECK (f != NULL) ;
207 1 : OK (LAGraph_MMRead (&A, f, msg)) ;
208 1 : OK (fclose (f)) ;
209 1 : OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_UNDIRECTED, msg)) ;
210 1 : TEST_CHECK (A == NULL) ; // A has been moved into G->A
211 1 : OK (LAGraph_Cached_OutDegree (G, msg)) ;
212 :
213 : // compute its pagerank using the standard method
214 1 : OK (LAGr_PageRank (¢rality, &niters, G, 0.85, 1e-4, 100, msg)) ;
215 :
216 : // compare with MATLAB: cmatlab = centrality (G, 'pagerank')
217 1 : float err = difference (centrality, karate_rank) ;
218 1 : float rsum = 0 ;
219 1 : OK (GrB_reduce (&rsum, NULL, GrB_PLUS_MONOID_FP32, centrality, NULL)) ;
220 1 : printf ("karate: err: %e (standard), sum(r): %e iters: %d\n",
221 : err, rsum, niters) ;
222 1 : TEST_CHECK (err < 1e-4) ;
223 1 : OK (GrB_free (¢rality)) ;
224 :
225 : // compute its pagerank using the LDBC Graphalytics method
226 1 : OK (LAGr_PageRankGX (¢rality, &niters, G, 0.85, 100, msg)) ;
227 :
228 : // compare with MATLAB: cmatlab = centrality (G, 'pagerank')
229 1 : err = difference (centrality, karate_rank) ;
230 1 : OK (GrB_reduce (&rsum, NULL, GrB_PLUS_MONOID_FP32, centrality, NULL)) ;
231 1 : printf ("karate: err: %e (Graphalytics), sum(r): %e iters: %d\n",
232 : err, rsum, niters) ;
233 1 : TEST_CHECK (err < 1e-4) ;
234 1 : OK (GrB_free (¢rality)) ;
235 :
236 : // test for failure to converge
237 1 : int status = LAGr_PageRank (¢rality, &niters, G, 0.85, 1e-4, 2, msg) ;
238 1 : printf ("status: %d msg: %s\n", status, msg) ;
239 1 : TEST_CHECK (status == LAGRAPH_CONVERGENCE_FAILURE) ;
240 :
241 1 : OK (LAGraph_Delete (&G, msg)) ;
242 :
243 : //--------------------------------------------------------------------------
244 : // west0067: no sinks
245 : //--------------------------------------------------------------------------
246 :
247 : // create the west0067 graph
248 1 : snprintf (filename, LEN, LG_DATA_DIR "%s", "west0067.mtx") ;
249 1 : f = fopen (filename, "r") ;
250 1 : TEST_CHECK (f != NULL) ;
251 1 : OK (LAGraph_MMRead (&A, f, msg)) ;
252 1 : OK (fclose (f)) ;
253 1 : OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_DIRECTED, msg)) ;
254 1 : TEST_CHECK (A == NULL) ; // A has been moved into G->A
255 1 : OK (LAGraph_Cached_AT (G, msg)) ;
256 1 : OK (LAGraph_Cached_OutDegree (G, msg)) ;
257 :
258 : // compute its pagerank using the standard method
259 1 : OK (LAGr_PageRank (¢rality, &niters, G, 0.85, 1e-4, 100, msg)) ;
260 :
261 : // compare with MATLAB: cmatlab = centrality (G, 'pagerank')
262 1 : err = difference (centrality, west0067_rank) ;
263 1 : printf ("west0067: err: %e (standard), sum(r): %e iters: %d\n",
264 : err, rsum, niters) ;
265 1 : TEST_CHECK (err < 1e-4) ;
266 1 : OK (GrB_free (¢rality)) ;
267 :
268 : // compute its pagerank using the LDBC Graphalytics method
269 1 : OK (LAGr_PageRankGX (¢rality, &niters, G, 0.85, 100, msg)) ;
270 :
271 : // compare with MATLAB: cmatlab = centrality (G, 'pagerank')
272 1 : err = difference (centrality, west0067_rank) ;
273 1 : printf ("west0067: err: %e (standard), sum(r): %e iters: %d\n",
274 : err, rsum, niters) ;
275 1 : TEST_CHECK (err < 1e-4) ;
276 1 : OK (GrB_free (¢rality)) ;
277 :
278 1 : OK (LAGraph_Delete (&G, msg)) ;
279 :
280 : //--------------------------------------------------------------------------
281 : // ldbc-directed-example: has 2 sinks
282 : //--------------------------------------------------------------------------
283 :
284 : // create the ldbc-directed-example graph
285 1 : snprintf (filename, LEN, LG_DATA_DIR "%s", "ldbc-directed-example.mtx") ;
286 1 : f = fopen (filename, "r") ;
287 1 : TEST_CHECK (f != NULL) ;
288 1 : OK (LAGraph_MMRead (&A, f, msg)) ;
289 1 : OK (fclose (f)) ;
290 1 : OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_DIRECTED, msg)) ;
291 1 : TEST_CHECK (A == NULL) ; // A has been moved into G->A
292 1 : OK (LAGraph_Cached_AT (G, msg)) ;
293 1 : OK (LAGraph_Cached_OutDegree (G, msg)) ;
294 :
295 1 : printf ("\n=========== ldbc-directed-example, with sink nodes 3 and 9:\n") ;
296 1 : OK (LAGraph_Graph_Print (G, LAGraph_COMPLETE, stdout, msg)) ;
297 :
298 : // compute its pagerank using the standard method
299 1 : OK (LAGr_PageRank (¢rality, &niters, G, 0.85, 1e-4, 100, msg)) ;
300 :
301 : // compare with MATLAB: cmatlab = centrality (G, 'pagerank')
302 1 : err = difference (centrality, ldbc_directed_example_rank) ;
303 1 : OK (GrB_reduce (&rsum, NULL, GrB_PLUS_MONOID_FP32, centrality, NULL)) ;
304 1 : printf ("\nwith sinks handled properly:\n") ;
305 1 : printf ("ldbc-directed: err: %e (standard), sum(r): %e, niters %d\n",
306 : err, rsum, niters) ;
307 1 : TEST_CHECK (err < 1e-4) ;
308 1 : printf ("This is the correct pagerank, with sinks handled properly:\n") ;
309 1 : OK (LAGraph_Vector_Print (centrality, LAGraph_COMPLETE, stdout, msg)) ;
310 1 : OK (GrB_free (¢rality)) ;
311 :
312 : // compute its pagerank using the LDBC Graphalytics method
313 1 : OK (LAGr_PageRankGX (¢rality, &niters, G, 0.85, 100, msg)) ;
314 :
315 : // compare with MATLAB: cmatlab = centrality (G, 'pagerank')
316 1 : err = difference (centrality, ldbc_directed_example_rank) ;
317 1 : OK (GrB_reduce (&rsum, NULL, GrB_PLUS_MONOID_FP32, centrality, NULL)) ;
318 1 : printf ("\nwith sinks handled properly:\n") ;
319 1 : printf ("ldbc-directed: err: %e (standard), sum(r): %e, niters %d\n",
320 : err, rsum, niters) ;
321 1 : TEST_CHECK (err < 1e-4) ;
322 1 : printf ("This is the correct pagerank, with sinks handled properly:\n") ;
323 1 : OK (LAGraph_Vector_Print (centrality, LAGraph_COMPLETE, stdout, msg)) ;
324 1 : OK (GrB_free (¢rality)) ;
325 :
326 1 : OK (LAGraph_Delete (&G, msg)) ;
327 :
328 : //--------------------------------------------------------------------------
329 :
330 1 : LAGraph_Finalize (msg) ;
331 1 : }
332 :
333 : //------------------------------------------------------------------------------
334 : // list of tests
335 : //------------------------------------------------------------------------------
336 :
337 : TEST_LIST = {
338 : {"test_ranker", test_ranker},
339 : {NULL, NULL}
340 : };
|
