Line data Source code
1 : //----------------------------------------------------------------------------
2 : // LAGraph/experimental/test/test_lcc.c: tests for Local Clustering Coefficient
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 : // todo: write a simple lcc method, as LG_check_lcc, and compare its results
19 : // with LAGraph_lcc
20 :
21 : #include <stdio.h>
22 : #include <acutest.h>
23 :
24 : #include <LAGraphX.h>
25 : #include <LAGraph_test.h>
26 :
27 : char msg [LAGRAPH_MSG_LEN] ;
28 : LAGraph_Graph G = NULL ;
29 : GrB_Matrix A = NULL ;
30 : #define LEN 512
31 : char filename [LEN+1] ;
32 :
33 : typedef struct
34 : {
35 : bool symmetric ;
36 : const char *name ;
37 : }
38 : matrix_info ;
39 :
40 : // this known solution is listed here in lower precision than double allows
41 : double lcc_west0067 [67] = {
42 : 0.0909091,
43 : 0.0238095,
44 : 0.0714286,
45 : 0.0238095,
46 : 0.125,
47 : 0.119048,
48 : 0.178571,
49 : 0.133333,
50 : 0.0952381,
51 : 0.0833333,
52 : 0.0666667,
53 : 0.1,
54 : 0.0892857,
55 : 0.0714286,
56 : 0.138889,
57 : 0.0555556,
58 : 0.0694444,
59 : 0.0555556,
60 : 0.0714286,
61 : 0.0769231,
62 : 0.0333333,
63 : 0.0666667,
64 : 0.0666667,
65 : 0.0333333,
66 : 0.0694444,
67 : 0.0444444,
68 : 0.0555556,
69 : 0.0777778,
70 : 0.0333333,
71 : 0,
72 : 0.0904762,
73 : 0.0535714,
74 : 0.0714286,
75 : 0.107143,
76 : 0.0892857,
77 : 0,
78 : 0.0681818,
79 : 0.0357143,
80 : 0.0178571,
81 : 0.0666667,
82 : 0.0555556,
83 : 0.0694444,
84 : 0.0666667,
85 : 0.111111,
86 : 0.0444444,
87 : 0.142857,
88 : 0.166667,
89 : 0.2,
90 : 0.0448718,
91 : 0.166667,
92 : 0.166667,
93 : 0.119048,
94 : 0.166667,
95 : 0.190476,
96 : 0.104167,
97 : 0.0333333,
98 : 0.0444444,
99 : 0.0444444,
100 : 0.0777778,
101 : 0.0416667,
102 : 0.0222222,
103 : 0.0972222,
104 : 0.142857,
105 : 0.0416667,
106 : 0.0555556,
107 : 0.196429,
108 : 0.155556
109 : } ;
110 :
111 : const matrix_info files [ ] =
112 : {
113 : { 1, "A.mtx" },
114 : { 1, "jagmesh7.mtx" },
115 : { 0, "west0067.mtx" }, // unsymmetric
116 : { 1, "bcsstk13.mtx" },
117 : { 1, "karate.mtx" },
118 : { 1, "ldbc-cdlp-undirected-example.mtx" },
119 : { 1, "ldbc-undirected-example-bool.mtx" },
120 : { 1, "ldbc-undirected-example-unweighted.mtx" },
121 : { 1, "ldbc-undirected-example.mtx" },
122 : { 1, "ldbc-wcc-example.mtx" },
123 : { 0, "" },
124 : } ;
125 :
126 : //****************************************************************************
127 1 : void test_lcc (void)
128 : {
129 1 : LAGraph_Init (msg) ;
130 : #if LAGRAPH_SUITESPARSE
131 :
132 1 : for (int k = 0 ; ; k++)
133 10 : {
134 :
135 : // load the matrix as A
136 11 : const char *aname = files [k].name ;
137 11 : bool symmetric = files [k].symmetric ;
138 11 : if (strlen (aname) == 0) break;
139 10 : printf ("\n================================== %s:\n", aname) ;
140 10 : TEST_CASE (aname) ;
141 10 : snprintf (filename, LEN, LG_DATA_DIR "%s", aname) ;
142 10 : FILE *f = fopen (filename, "r") ;
143 10 : TEST_CHECK (f != NULL) ;
144 10 : OK (LAGraph_MMRead (&A, f, msg)) ;
145 :
146 : // construct a directed graph G with adjacency matrix A
147 10 : OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_DIRECTED, msg)) ;
148 10 : TEST_CHECK (A == NULL) ;
149 :
150 : // check for self-edges
151 10 : OK (LAGraph_Cached_NSelfEdges (G, msg)) ;
152 10 : bool sanitize = (G->nself_edges != 0) ;
153 :
154 10 : GrB_Vector c = NULL ;
155 : double t [2] ;
156 :
157 : // compute the local clustering coefficient
158 10 : OK (LAGraph_lcc (&c, G->A, symmetric, sanitize, t, msg)) ;
159 :
160 : GrB_Index n ;
161 10 : OK (GrB_Vector_size (&n, c)) ;
162 10 : LAGraph_PrintLevel pr = (n <= 100) ? LAGraph_COMPLETE : LAGraph_SHORT ;
163 :
164 : // check result c for west0067
165 10 : if (strcmp (aname, "west0067.mtx") == 0)
166 : {
167 1 : GrB_Vector cgood = NULL ;
168 1 : OK (GrB_Vector_new (&cgood, GrB_FP64, n)) ;
169 68 : for (int k = 0 ; k < n ; k++)
170 : {
171 67 : OK (GrB_Vector_setElement (cgood, lcc_west0067 [k], k)) ;
172 : }
173 1 : OK (GrB_wait (cgood, GrB_MATERIALIZE)) ;
174 1 : printf ("\nlcc (known result, but with float precision):\n") ;
175 1 : OK (LAGraph_Vector_Print (cgood, pr, stdout, msg)) ;
176 : // cgood = abs (cgood - c)
177 1 : OK (GrB_eWiseAdd (cgood, NULL, NULL, GrB_MINUS_FP64, cgood, c,
178 : NULL)) ;
179 1 : OK (GrB_apply (cgood, NULL, NULL, GrB_ABS_FP64, cgood, NULL)) ;
180 1 : double err = 0 ;
181 : // err = max (cgood)
182 1 : OK (GrB_reduce (&err, NULL, GrB_MAX_MONOID_FP64, cgood, NULL)) ;
183 1 : printf ("err: %g\n", err) ;
184 1 : TEST_CHECK (err < 1e-6) ;
185 1 : OK (GrB_free (&cgood)) ;
186 : }
187 :
188 10 : printf ("\nlcc:\n") ;
189 10 : OK (LAGraph_Vector_Print (c, pr, stdout, msg)) ;
190 10 : OK (GrB_free (&c)) ;
191 :
192 10 : OK (LAGraph_Delete (&G, msg)) ;
193 : }
194 :
195 : #else
196 : printf ("test skipped\n") ;
197 : #endif
198 1 : LAGraph_Finalize (msg) ;
199 1 : }
200 :
201 : //------------------------------------------------------------------------------
202 : // test_errors
203 : //------------------------------------------------------------------------------
204 :
205 1 : void test_errors (void)
206 : {
207 1 : LAGraph_Init (msg) ;
208 : #if LAGRAPH_SUITESPARSE
209 :
210 1 : snprintf (filename, LEN, LG_DATA_DIR "%s", "karate.mtx") ;
211 1 : FILE *f = fopen (filename, "r") ;
212 1 : TEST_CHECK (f != NULL) ;
213 1 : OK (LAGraph_MMRead (&A, f, msg)) ;
214 1 : TEST_MSG ("Loading of adjacency matrix failed") ;
215 :
216 : // construct an undirected graph G with adjacency matrix A
217 1 : OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_UNDIRECTED, msg)) ;
218 1 : TEST_CHECK (A == NULL) ;
219 :
220 1 : OK (LAGraph_Cached_NSelfEdges (G, msg)) ;
221 :
222 1 : GrB_Vector c = NULL ;
223 : double t [2] ;
224 :
225 : // c is NULL
226 1 : int result = LAGraph_lcc (NULL, G->A, true, false, t, msg) ;
227 1 : printf ("\nresult: %d\n", result) ;
228 1 : TEST_CHECK (result == GrB_NULL_POINTER) ;
229 :
230 : // G->A is held by column
231 1 : OK (GxB_set (G->A, GxB_FORMAT, GxB_BY_COL)) ;
232 1 : result = LAGraph_lcc (&c, G->A, true, true, t, msg) ;
233 1 : printf ("\nresult: %d\n", result) ;
234 1 : TEST_CHECK (result == GrB_INVALID_VALUE) ;
235 1 : TEST_CHECK (c == NULL) ;
236 :
237 1 : OK (LAGraph_Delete (&G, msg)) ;
238 : #else
239 : printf ("test skipped\n") ;
240 : #endif
241 1 : LAGraph_Finalize (msg) ;
242 1 : }
243 :
244 : //****************************************************************************
245 :
246 : TEST_LIST = {
247 : {"lcc", test_lcc},
248 : {"lcc_errors", test_errors},
249 : {NULL, NULL}
250 : };
|
