Line data Source code
1 : //----------------------------------------------------------------------------
2 : // LAGraph/src/test/test_quality_metrics.c: test cases for both Partition
3 : // Quality and Modularity graph clustering metrics
4 : // ----------------------------------------------------------------------------
5 :
6 : // LAGraph, (c) 2019-2022 by The LAGraph Contributors, All Rights Reserved.
7 : // SPDX-License-Identifier: BSD-2-Clause
8 : //
9 : // For additional details (including references to third party source code and
10 : // other files) see the LICENSE file or contact permission@sei.cmu.edu. See
11 : // Contributors.txt for a full list of contributors. Created, in part, with
12 : // funding and support from the U.S. Government (see Acknowledgments.txt file).
13 : // DM22-0790
14 :
15 : // Contributed by Cameron Quilici, Texas A&M University
16 :
17 : //-----------------------------------------------------------------------------
18 :
19 : #include <acutest.h>
20 : #include <stdio.h>
21 :
22 : #include "LG_Xtest.h"
23 : #include <LAGraphX.h>
24 : #include <LAGraph_test.h>
25 :
26 : char msg[LAGRAPH_MSG_LEN];
27 :
28 : LAGraph_Graph G = NULL;
29 : GrB_Matrix A = NULL;
30 : GrB_Vector c = NULL;
31 : #define LEN 512
32 : char filename[LEN + 1];
33 : char cluster_filename[LEN + 1];
34 :
35 : typedef struct
36 : {
37 : const char *name;
38 : const char *cluster_name;
39 : } matrix_info;
40 :
41 : const matrix_info files[] = {
42 : {"A.mtx", "A_cluster.mtx"},
43 : {"jagmesh7.mtx", "jagmesh7_cluster.mtx"},
44 : {"west0067.mtx", "west0067_cluster.mtx"}, // unsymmetric
45 : {"bcsstk13.mtx", "bcsstk13_cluster.mtx"},
46 : {"karate.mtx", "karate_cluster.mtx"},
47 : {"mcl.mtx", "mcl_cluster.mtx"},
48 : {"", ""},
49 : };
50 :
51 : const int nfiles = 6;
52 :
53 : const double coverage[] = {1.000000, 0.653359, 0.181507,
54 : 0.048510, 0.243590, 0.833333};
55 :
56 : const double performance[] = {0.714286, 0.989642, 0.841701,
57 : 0.977048, 0.887701, 0.866667};
58 :
59 : const double modularity[] = {0.000000, 0.641262, 0.043324,
60 : 0.042696, 0.158120, 0.500000};
61 :
62 : //****************************************************************************
63 1 : void test_quality_metrics(void)
64 : {
65 : #if LAGRAPH_SUITESPARSE
66 1 : LAGraph_Init(msg);
67 :
68 1 : for (int k = 0;; k++)
69 6 : {
70 : // load the matrix as A
71 7 : const char *aname = files[k].name;
72 7 : const char *aname_cluster = files[k].cluster_name;
73 7 : if (strlen(aname) == 0 || strlen(aname_cluster) == 0)
74 : break;
75 6 : printf("\n================================== %s:, %s\n", aname,
76 : aname_cluster);
77 6 : TEST_CASE(aname);
78 6 : TEST_CASE(aname_cluster);
79 6 : snprintf(filename, LEN, LG_DATA_DIR "%s", aname);
80 6 : FILE *f1 = fopen(filename, "r");
81 6 : TEST_CHECK(f1 != NULL);
82 6 : OK(LAGraph_MMRead(&A, f1, msg));
83 6 : fclose (f1) ;
84 :
85 6 : snprintf(cluster_filename, LEN, LG_DATA_DIR "%s", aname_cluster);
86 6 : FILE *f2 = fopen(cluster_filename, "r");
87 6 : TEST_CHECK(f2 != NULL);
88 6 : OK(LAGraph_MMRead((GrB_Matrix *)&c, f2, msg));
89 6 : fclose (f2) ;
90 :
91 : // construct a directed graph G with adjacency matrix A
92 6 : OK(LAGraph_New(&G, &A, LAGraph_ADJACENCY_DIRECTED, msg));
93 6 : TEST_CHECK(A == NULL);
94 :
95 : // compute is_symmetric_structure
96 6 : OK(LAGraph_Cached_IsSymmetricStructure(G, msg));
97 6 : TEST_CHECK(G->is_symmetric_structure != LAGRAPH_UNKNOWN);
98 :
99 : // compute quality metrics (coverage and performance)
100 : double cov, perf, mod;
101 6 : OK(LAGr_PartitionQuality(&cov, NULL, c, G, msg));
102 6 : OK(LAGr_PartitionQuality(NULL, &perf, c, G, msg));
103 6 : OK(LAGr_Modularity(&mod, (double)1, c, G, msg));
104 6 : bool ok_cov = false, ok_perf = false, ok_mod = false;
105 6 : printf("coverage: %g %g\n", cov, coverage[k]);
106 6 : printf("perf: %g %g\n", perf, performance[k]);
107 6 : printf("modularity: %g %g\n", mod, modularity[k]);
108 6 : ok_cov = (fabs(cov - coverage[k]) < 1e-4) ? true : ok_cov;
109 6 : ok_perf = (fabs(perf - performance[k]) < 1e-4) ? true : ok_perf;
110 6 : ok_mod = (fabs(mod - modularity[k]) < 1e-4) ? true : ok_mod;
111 :
112 6 : TEST_CHECK(ok_cov);
113 6 : TEST_CHECK(ok_perf);
114 6 : TEST_CHECK(ok_mod);
115 :
116 6 : OK(GrB_free(&c));
117 :
118 6 : OK(LAGraph_Delete(&G, msg));
119 : }
120 :
121 1 : LAGraph_Finalize(msg);
122 : #endif
123 1 : }
124 :
125 : //------------------------------------------------------------------------------
126 : // test_errors
127 : //------------------------------------------------------------------------------
128 :
129 1 : void test_partition_quality_errors(void)
130 : {
131 : #if LAGRAPH_SUITESPARSE
132 1 : LAGraph_Init(msg);
133 :
134 1 : snprintf(filename, LEN, LG_DATA_DIR "%s", "west0067.mtx");
135 1 : FILE *f1 = fopen(filename, "r");
136 1 : TEST_CHECK(f1 != NULL);
137 1 : OK(LAGraph_MMRead(&A, f1, msg));
138 1 : TEST_MSG("Loading of adjacency matrix failed");
139 1 : fclose (f1) ;
140 :
141 1 : snprintf(cluster_filename, LEN, LG_DATA_DIR "%s", "west0067_cluster.mtx");
142 1 : FILE *f2 = fopen(cluster_filename, "r");
143 1 : TEST_CHECK(f2 != NULL);
144 1 : OK(LAGraph_MMRead((GrB_Matrix *)&c, f2, msg));
145 1 : TEST_MSG("Loading of cluster vector failed");
146 1 : fclose (f2) ;
147 :
148 : // construct an undirected graph G with adjacency matrix A
149 1 : OK(LAGraph_New(&G, &A, LAGraph_ADJACENCY_UNDIRECTED, msg));
150 1 : TEST_CHECK(A == NULL);
151 :
152 : double cov, perf;
153 :
154 : // both cov and perf are null
155 1 : GrB_Info result = LAGr_PartitionQuality(NULL, NULL, c, G, msg);
156 1 : printf("\nresult: %d %s\n", result, msg);
157 1 : TEST_CHECK(result == GrB_NULL_POINTER);
158 :
159 : // G->is_symmetric_structure is not cached
160 1 : G->is_symmetric_structure = LAGRAPH_UNKNOWN;
161 1 : result = LAGr_PartitionQuality(&cov, &perf, c, G, msg);
162 1 : printf("\nresult: %d %s\n", result, msg);
163 1 : TEST_CHECK(result == LAGRAPH_NOT_CACHED);
164 :
165 1 : OK(LAGraph_Delete(&G, msg));
166 1 : TEST_CHECK(G == NULL);
167 :
168 : // bad graph, G->A is null
169 1 : OK(LAGraph_New(&G, NULL, LAGraph_ADJACENCY_UNDIRECTED, msg));
170 1 : result = LAGr_PartitionQuality(&cov, &perf, c, G, msg);
171 1 : printf("\nresult: %d %s\n", result, msg);
172 1 : TEST_CHECK(result == LAGRAPH_INVALID_GRAPH);
173 :
174 1 : GrB_free (&c) ;
175 1 : OK(LAGraph_Delete(&G, msg));
176 1 : TEST_CHECK(G == NULL);
177 :
178 1 : LAGraph_Finalize(msg);
179 : #endif
180 1 : }
181 :
182 1 : void test_modularity_errors(void)
183 : {
184 : #if LAGRAPH_SUITESPARSE
185 1 : LAGraph_Init(msg);
186 :
187 1 : snprintf(filename, LEN, LG_DATA_DIR "%s", "west0067.mtx");
188 1 : FILE *f1 = fopen(filename, "r");
189 1 : TEST_CHECK(f1 != NULL);
190 1 : OK(LAGraph_MMRead(&A, f1, msg));
191 1 : TEST_MSG("Loading of adjacency matrix failed");
192 1 : fclose (f1) ;
193 :
194 1 : snprintf(cluster_filename, LEN, LG_DATA_DIR "%s", "west0067_cluster.mtx");
195 1 : FILE *f2 = fopen(cluster_filename, "r");
196 1 : TEST_CHECK(f2 != NULL);
197 1 : OK(LAGraph_MMRead((GrB_Matrix *)&c, f2, msg));
198 1 : TEST_MSG("Loading of cluster vector failed");
199 1 : fclose (f2) ;
200 :
201 : // construct an undirected graph G with adjacency matrix A
202 1 : OK(LAGraph_New(&G, &A, LAGraph_ADJACENCY_UNDIRECTED, msg));
203 1 : TEST_CHECK(A == NULL);
204 :
205 : double mod;
206 1 : double resolution = 1;
207 :
208 : // mod is NULL
209 1 : GrB_Info result = LAGr_Modularity(NULL, resolution, c, G, msg);
210 1 : printf("\nresult: %d %s\n", result, msg);
211 1 : TEST_CHECK(result == GrB_NULL_POINTER);
212 :
213 : // resolution parameter is negative
214 1 : resolution = -1;
215 1 : result = LAGr_Modularity(&mod, resolution, c, G, msg);
216 1 : printf("\nresult: %d %s\n", result, msg);
217 1 : TEST_CHECK(result == GrB_INVALID_VALUE);
218 1 : resolution = 1;
219 :
220 1 : OK(LAGraph_Delete(&G, msg));
221 1 : TEST_CHECK(G == NULL);
222 :
223 : // bad graph, G->A is null
224 1 : OK(LAGraph_New(&G, NULL, LAGraph_ADJACENCY_UNDIRECTED, msg));
225 1 : result = LAGr_Modularity(&mod, resolution, c, G, msg);
226 1 : printf("\nresult: %d %s\n", result, msg);
227 1 : TEST_CHECK(result == LAGRAPH_INVALID_GRAPH);
228 :
229 1 : GrB_free (&c) ;
230 1 : OK(LAGraph_Delete(&G, msg));
231 1 : TEST_CHECK(G == NULL);
232 :
233 1 : LAGraph_Finalize(msg);
234 : #endif
235 1 : }
236 :
237 : //****************************************************************************
238 :
239 : TEST_LIST = {{"quality_metrics", test_quality_metrics},
240 : {"partition_quality_errors", test_partition_quality_errors},
241 : {"modularity_errors", test_modularity_errors},
242 : {NULL, NULL}};
|
