Line data Source code
1 : //------------------------------------------------------------------------------
2 : // test_HITS.c: Test suite for HITS algorithm using GraphBLAS and LAGraph
3 : //------------------------------------------------------------------------------
4 :
5 : #include <stdio.h>
6 : #include <acutest.h>
7 : #include "LAGraphX.h"
8 : #include "LAGraph_test.h"
9 :
10 : #define LEN 512
11 : char msg[LAGRAPH_MSG_LEN];
12 : char filename[LEN + 1];
13 : LAGraph_Graph G = NULL;
14 :
15 : // Utility function to compare vectors with expected results
16 6 : float difference(GrB_Vector vector, double *expected_result, GrB_Index n)
17 : {
18 6 : GrB_Vector diff = NULL;
19 6 : float err = 0.0;
20 6 : OK(GrB_Vector_new(&diff, GrB_FP32, n));
21 222 : for (GrB_Index i = 0; i < n; i++) {
22 216 : OK(GrB_Vector_setElement_FP64(diff, expected_result[i], i));
23 : }
24 6 : OK(GrB_eWiseAdd(diff, NULL, NULL, GrB_MINUS_FP32, vector, diff, NULL));
25 6 : OK(GrB_apply(diff, NULL, NULL, GrB_ABS_FP32, diff, NULL));
26 6 : OK(GrB_reduce(&err, NULL, GrB_MAX_MONOID_FP32, diff, NULL));
27 6 : OK(GrB_free(&diff));
28 6 : return err;
29 : }
30 :
31 : // Test function for a specific graph
32 6 : void test_HITS_on_graph
33 : (
34 : const char *graph_file,
35 : bool directed,
36 : double *expected_hubs,
37 : double *expected_authorities
38 : )
39 : {
40 6 : GrB_Vector hubs = NULL, authorities = NULL;
41 6 : GrB_Matrix A = NULL ;
42 6 : int iters = 0 ;
43 6 : float tol = 1e-4 ;
44 6 : int itermax = 100 ;
45 6 : GrB_Index n = 0 ;
46 :
47 : // Load the graph
48 6 : printf ("HITS test: %s\n", graph_file) ;
49 6 : snprintf (filename, LEN, LG_DATA_DIR "%s", graph_file);
50 6 : FILE *f = fopen(filename, "r");
51 6 : TEST_CHECK (f != NULL);
52 6 : OK (LAGraph_MMRead (&A, f, msg));
53 6 : OK (fclose(f));
54 6 : OK (GrB_Matrix_nrows (&n, A)) ;
55 6 : int kind = directed ? LAGraph_ADJACENCY_DIRECTED : LAGraph_ADJACENCY_UNDIRECTED ;
56 6 : OK (LAGraph_New (&G, &A, kind, msg)) ;
57 6 : TEST_CHECK (A == NULL) ; // A has been moved into G->A
58 6 : OK (LAGraph_Cached_OutDegree (G, msg)) ;
59 6 : if (directed)
60 : {
61 3 : OK (LAGraph_Cached_InDegree (G, msg)) ;
62 3 : OK (LAGraph_Cached_AT(G, msg)) ;
63 : }
64 :
65 : // Run HITS algorithm
66 6 : OK (LAGr_HITS (&hubs, &authorities, &iters, G, tol, itermax, msg)) ;
67 6 : OK (LAGraph_Vector_Print (hubs, 2, stdout, msg)) ;
68 6 : OK (LAGraph_Vector_Print (authorities, 2, stdout, msg)) ;
69 :
70 : // Compare results with expected values
71 6 : if (expected_hubs != NULL && expected_authorities != NULL)
72 : {
73 3 : float err_hubs = difference(hubs, expected_hubs, n);
74 3 : float err_auth = difference(authorities, expected_authorities, n);
75 3 : TEST_CHECK(err_hubs < 1e-4 && err_auth < 1e-4);
76 : }
77 :
78 : // Clean up
79 6 : OK(GrB_free(&hubs));
80 6 : OK(GrB_free(&authorities));
81 6 : OK(LAGraph_Delete(&G, msg));
82 6 : }
83 :
84 : // Test cases for different graphs
85 1 : void test_HITS(void)
86 : {
87 1 : LAGraph_Init(msg);
88 :
89 : // Test case for Graph 1
90 : // Define expected hubs and authorities values for the first graph
91 1 : double structure_hubs[] ={
92 : 0.13865498151112815,
93 : 0.13865498151112823,
94 : -7.52772710372611e-17,
95 : 0.19608775534362824,
96 : -7.52772710372611e-17,
97 : 0.15423823730232433,
98 : 0.3723640443317912
99 : };
100 :
101 1 : double structure_authorities[] = {
102 : 0.0884024498169609,
103 : 0.06250997173907646,
104 : 0.3258111125561342,
105 : 0.230383247074376,
106 : 0.23038324707437605,
107 : -1.5901485815586466e-16,
108 : 0.06250997173907653};
109 :
110 1 : test_HITS_on_graph ("structure.mtx", true, structure_hubs, structure_authorities) ;
111 :
112 : // Additional test cases can be added here
113 1 : double karate_authorities[] = {
114 : 0.07141272880825196,
115 : 0.05342723123552997,
116 : 0.06371906455637479,
117 : 0.042422737124709016,
118 : 0.01526095970620749,
119 : 0.01596691350305964,
120 : 0.015966913503059642,
121 : 0.03434316721905367,
122 : 0.0456819251197503,
123 : 0.020625667749388638,
124 : 0.015260959706207484,
125 : 0.010617891511071214,
126 : 0.01692545079230685,
127 : 0.045494864068056355,
128 : 0.020370345825614276,
129 : 0.02037034582561427,
130 : 0.004748031847301578,
131 : 0.018561637037432098,
132 : 0.020370345825614273,
133 : 0.02971333388643479,
134 : 0.02037034582561427,
135 : 0.018561637037432088,
136 : 0.02037034582561428,
137 : 0.030156497509356398,
138 : 0.011460952230971697,
139 : 0.011893664396281381,
140 : 0.015182734330338388,
141 : 0.026813494117104757,
142 : 0.0263315057779539,
143 : 0.027111539628217676,
144 : 0.035106237976714395,
145 : 0.038375741862956045,
146 : 0.06200184647383098,
147 : 0.0750029421565755
148 : };
149 :
150 1 : double karate_hubs[] = {
151 : 0.07141272880825197,
152 : 0.053427231235529976,
153 : 0.06371906455637479,
154 : 0.04242273712470899,
155 : 0.015260959706207477,
156 : 0.01596691350305964,
157 : 0.015966913503059642,
158 : 0.034343167219053644,
159 : 0.045681925119750305,
160 : 0.020625667749388638,
161 : 0.01526095970620748,
162 : 0.010617891511071217,
163 : 0.01692545079230686,
164 : 0.045494864068056355,
165 : 0.020370345825614276,
166 : 0.020370345825614276,
167 : 0.004748031847301572,
168 : 0.018561637037432077,
169 : 0.020370345825614276,
170 : 0.02971333388643479,
171 : 0.020370345825614276,
172 : 0.018561637037432077,
173 : 0.020370345825614276,
174 : 0.030156497509356388,
175 : 0.011460952230971698,
176 : 0.011893664396281383,
177 : 0.015182734330338387,
178 : 0.026813494117104767,
179 : 0.02633150577795389,
180 : 0.02711153962821767,
181 : 0.03510623797671438,
182 : 0.038375741862956045,
183 : 0.062001846473830974,
184 : 0.07500294215657549
185 : };
186 :
187 1 : test_HITS_on_graph ("karate.mtx", true, karate_hubs, karate_authorities) ;
188 :
189 1 : double west0067_authorities[] = {
190 : 0.06732949417782225,
191 : 0.018574729659429256,
192 : 0.01857472965942926,
193 : 0.01857472965942926,
194 : 0.018574729659429263,
195 : 0.01632186793713691,
196 : 0.02078477532361338,
197 : 0.00585934344896191,
198 : 0.005859343448961904,
199 : 0.005859343448961908,
200 : 0.005859343448961906,
201 : 0.005021016999031531,
202 : 0.010146952711582115,
203 : 0.010146952711582124,
204 : 0.010146952711582119,
205 : 0.010146952711582119,
206 : 0.00934188807096454,
207 : 0.004684063920168795,
208 : 0.0017875587394001404,
209 : 0.031838153971749474,
210 : 0.007677720669689195,
211 : 0.007677720669689193,
212 : 0.007677720669689198,
213 : 0.007677720669689193,
214 : 0.007670735848683439,
215 : 0.010841557047533654,
216 : 0.010841557047533668,
217 : 0.010841557047533652,
218 : 0.010841557047533656,
219 : 0.00986797158919092,
220 : 0.06988287712194143,
221 : 0.016889037721065245,
222 : 0.01688903772106524,
223 : 0.016889037721065234,
224 : 0.01688903772106524,
225 : 0.016689246436020627,
226 : 0.07502520998403943,
227 : 0.026249126706735713,
228 : 0.026249126706735668,
229 : 0.026249126706735685,
230 : 0.026249126706735678,
231 : 0.024022620819215273,
232 : 0.012673130182575166,
233 : 0.009449644899966868,
234 : 0.009449644899966867,
235 : 0.009449644899966863,
236 : 0.009449644899966867,
237 : 0.008733252034310393,
238 : 0.04586314226355754,
239 : 0.01109388908937864,
240 : 0.01109388908937864,
241 : 0.011093889089378639,
242 : 0.011093889089378646,
243 : 0.010913504446435658,
244 : 0.02538051304910646,
245 : 0.009214716813144334,
246 : 0.009214716813144336,
247 : 0.00921471681314433,
248 : 0.009214716813144331,
249 : 0.008201611896653702,
250 : 0.005149806847527351,
251 : 0.003335596853625951,
252 : 0.0033355968536259548,
253 : 0.003335596853625953,
254 : 0.0033355968536259574,
255 : 0.002725698164004691,
256 : 0.002762597692399429
257 : };
258 :
259 1 : double west0067_hubs[] = {
260 : 0.003526088046054016,
261 : 0.003526088046054016,
262 : 0.003526088046054016,
263 : 0.003526088046054016,
264 : 0.020909950936193765,
265 : 0.02090995093619377,
266 : 0.020909950936193765,
267 : 0.020909950936193765,
268 : 0.020245944586658682,
269 : 0.009307374813197,
270 : 0.008463627562768736,
271 : 0.008463627562768737,
272 : 0.008463627562768737,
273 : 0.008463627562768736,
274 : 0.008629875592757835,
275 : 0.023369827672566602,
276 : 0.023369827672566602,
277 : 0.023369827672566602,
278 : 0.023369827672566602,
279 : 0.023168668350737887,
280 : 0.009798738937493466,
281 : 0.00979873893749346,
282 : 0.009798738937493461,
283 : 0.009798738937493461,
284 : 0.046687128336499024,
285 : 0.04668712833649902,
286 : 0.04668712833649902,
287 : 0.04668712833649902,
288 : 0.045889697736916354,
289 : 0.02414744714926618,
290 : 0.028576497121579458,
291 : 0.02857649712157945,
292 : 0.02857649712157945,
293 : 0.028576497121579454,
294 : 0.028044221597879726,
295 : 0.0042956652047794405,
296 : 0.004295665204779443,
297 : 0.004295665204779439,
298 : 0.0042956652047794405,
299 : 0.01745013702794716,
300 : 0.017450137027947163,
301 : 0.01745013702794716,
302 : 0.017450137027947163,
303 : 0.017080820240550767,
304 : 0.00855692644069361,
305 : 0.0026496905128096547,
306 : 0.002649690512809655,
307 : 0.0026496905128096542,
308 : 0.0026496905128096555,
309 : 0.008074664429681208,
310 : 0.008074664429681208,
311 : 0.008074664429681204,
312 : 0.008074664429681206,
313 : 0.007675980312928068,
314 : 0.0032091586092053287,
315 : 0.0003046389467379955,
316 : 0.004849929687076762,
317 : 0.008509108290457435,
318 : 0.0065410638456684465,
319 : 0.014357250780909648,
320 : 0.015443755981969173,
321 : 0.02198766971337126,
322 : 0.009422460296381946,
323 : 0.00907226721772279,
324 : 0.007679287178074854,
325 : 0.007930037691283138,
326 : 0.0027383517860651856
327 : };
328 :
329 1 : test_HITS_on_graph ("west0067.mtx", true, west0067_hubs, west0067_authorities) ;
330 :
331 1 : LAGraph_Finalize(msg);
332 1 : }
333 :
334 1 : void test_HITS2 (void)
335 : {
336 1 : LAGraph_Init (msg) ;
337 1 : printf ("\n") ;
338 1 : test_HITS_on_graph ("karate.mtx", false, NULL, NULL) ;
339 1 : test_HITS_on_graph ("karate_verysparse.mtx", false, NULL, NULL) ;
340 1 : test_HITS_on_graph ("diamonds.mtx", false, NULL, NULL) ;
341 1 : LAGraph_Finalize (msg);
342 1 : }
343 :
344 : // List of tests to run
345 : TEST_LIST = {
346 : {"test_HITS", test_HITS},
347 : {"test_HITS2", test_HITS2},
348 : {NULL, NULL}
349 : };
350 :
|
