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