Line data Source code
1 : //----------------------------------------------------------------------------
2 : // LAGraph/src/test/test_cdlp.c: test cases for CDLP
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 cdlp method, as LG_check_cdlp, and compare its results
19 : // with LAGraph_cdlp
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 : double cdlp_jagmesh7 [1138] = {
41 : 0, 0, 0, 2, 2, 2, 2, 2, 8, 8, 8, 8, 8, 8, 14, 14, 0, 0, 0, 2, 2, 2, 14,
42 : 2, 8, 14, 8, 8, 0, 0, 29, 29, 29, 29, 29, 35, 35, 35, 2, 0, 29, 29, 29,
43 : 2, 2, 35, 2, 35, 2, 0, 50, 50, 50, 50, 50, 50, 56, 56, 56, 29, 0, 50, 50,
44 : 50, 29, 29, 56, 29, 56, 29, 50, 71, 71, 71, 71, 71, 71, 77, 77, 77, 29,
45 : 56, 71, 71, 71, 56, 56, 77, 56, 77, 56, 50, 92, 92, 92, 92, 96, 92, 98,
46 : 98, 98, 71, 50, 92, 92, 92, 71, 71, 98, 71, 98, 71, 96, 113, 113, 113,
47 : 113, 113, 113, 119, 119, 119, 74, 98, 113, 113, 113, 98, 98, 119, 98, 119,
48 : 98, 96, 96, 134, 134, 134, 134, 134, 140, 140, 140, 113, 96, 134, 134, 134,
49 : 113, 113, 140, 113, 140, 113, 96, 155, 155, 155, 155, 155, 155, 161, 161,
50 : 161, 134, 96, 155, 155, 155, 134, 134, 161, 134, 161, 134, 155, 176, 176,
51 : 176, 176, 176, 176, 182, 182, 182, 134, 161, 176, 176, 176, 161, 161, 182,
52 : 161, 182, 161, 155, 197, 197, 197, 197, 197, 197, 203, 203, 203, 176, 155,
53 : 197, 197, 197, 176, 176, 203, 176, 203, 176, 197, 218, 218, 218, 218, 222,
54 : 218, 224, 224, 224, 176, 203, 218, 218, 218, 203, 203, 224, 203, 224, 203,
55 : 222, 239, 239, 239, 239, 239, 239, 245, 245, 180, 180, 224, 239, 239, 239,
56 : 224, 224, 245, 224, 245, 180, 222, 222, 260, 260, 260, 260, 260, 266, 266,
57 : 266, 239, 222, 260, 260, 260, 239, 239, 266, 239, 266, 239, 222, 281, 281,
58 : 281, 281, 281, 281, 287, 287, 287, 260, 222, 281, 281, 281, 260, 260, 287,
59 : 260, 287, 260, 281, 302, 302, 302, 302, 302, 302, 308, 308, 308, 260, 287,
60 : 302, 302, 302, 287, 287, 308, 287, 308, 287, 302, 323, 323, 323, 323, 323,
61 : 323, 329, 329, 260, 260, 260, 308, 308, 308, 329, 308, 323, 329, 323, 323,
62 : 302, 344, 344, 344, 344, 344, 344, 350, 350, 350, 323, 302, 344, 344, 344,
63 : 323, 323, 350, 323, 350, 323, 239, 365, 365, 365, 365, 365, 365, 371, 371,
64 : 180, 180, 180, 245, 245, 245, 371, 245, 365, 371, 365, 365, 260, 386, 386,
65 : 386, 386, 386, 386, 392, 392, 392, 239, 266, 386, 386, 386, 266, 266, 392,
66 : 266, 392, 266, 239, 407, 407, 407, 407, 407, 407, 413, 413, 413, 365, 239,
67 : 407, 407, 407, 365, 365, 413, 365, 413, 365, 386, 428, 428, 428, 407, 239,
68 : 392, 392, 392, 407, 392, 428, 407, 428, 407, 344, 443, 443, 443, 443, 443,
69 : 443, 449, 449, 449, 323, 350, 350, 350, 350, 449, 350, 443, 449, 443, 443,
70 : 344, 464, 464, 464, 464, 464, 464, 470, 470, 470, 443, 344, 464, 464, 464,
71 : 443, 443, 470, 443, 470, 443, 464, 485, 485, 485, 485, 485, 485, 491, 491,
72 : 491, 443, 470, 470, 470, 470, 491, 470, 485, 491, 485, 485, 464, 506, 506,
73 : 506, 506, 506, 506, 512, 512, 512, 485, 485, 485, 485, 464, 512, 485, 506,
74 : 512, 506, 506, 506, 527, 527, 527, 527, 531, 527, 533, 533, 533, 485, 512,
75 : 512, 512, 512, 533, 512, 527, 533, 527, 527, 547, 547, 547, 533, 533, 485,
76 : 531, 554, 554, 547, 547, 547, 533, 533, 533, 554, 533, 533, 554, 533, 533,
77 : 386, 569, 569, 547, 547, 547, 574, 574, 574, 407, 386, 569, 569, 547, 428,
78 : 428, 574, 428, 574, 428, 531, 531, 589, 411, 411, 411, 574, 574, 547, 589,
79 : 554, 554, 589, 554, 531, 531, 531, 604, 604, 604, 604, 604, 610, 610, 411,
80 : 411, 411, 589, 589, 531, 610, 589, 604, 610, 604, 604, 531, 625, 625, 625,
81 : 625, 625, 625, 631, 631, 631, 604, 604, 604, 604, 531, 631, 604, 625, 631,
82 : 625, 625, 625, 646, 646, 646, 646, 646, 646, 652, 652, 652, 604, 631, 631,
83 : 631, 631, 652, 631, 646, 652, 646, 646, 666, 666, 666, 652, 652, 604, 646,
84 : 673, 673, 666, 666, 666, 652, 652, 652, 673, 652, 652, 673, 652, 652, 646,
85 : 688, 688, 688, 688, 692, 688, 694, 694, 666, 666, 666, 673, 673, 646, 694,
86 : 673, 688, 694, 688, 688, 708, 708, 708, 694, 666, 666, 692, 715, 715, 708,
87 : 708, 708, 694, 694, 666, 715, 694, 694, 715, 694, 694, 729, 729, 729, 715,
88 : 708, 708, 692, 692, 736, 729, 729, 729, 715, 715, 708, 736, 715, 715, 736,
89 : 715, 692, 729, 729, 751, 751, 751, 751, 751, 757, 757, 708, 708, 729, 751,
90 : 751, 751, 731, 731, 757, 731, 757, 708, 771, 771, 771, 773, 773, 751, 729,
91 : 729, 778, 771, 771, 771, 751, 751, 751, 778, 751, 751, 778, 751, 729, 771,
92 : 771, 793, 793, 793, 793, 793, 799, 799, 799, 751, 771, 793, 793, 793, 773,
93 : 773, 799, 773, 799, 773, 113, 814, 814, 814, 793, 771, 819, 819, 113, 113,
94 : 113, 814, 793, 793, 819, 793, 793, 819, 793, 771, 134, 834, 834, 834, 793,
95 : 140, 140, 140, 140, 814, 140, 834, 814, 834, 814, 113, 849, 849, 849, 849,
96 : 849, 849, 855, 855, 855, 74, 74, 119, 119, 119, 855, 119, 849, 855, 849,
97 : 849, 849, 870, 870, 29, 29, 29, 77, 77, 77, 870, 77, 855, 870, 855, 855, 2,
98 : 885, 885, 885, 885, 889, 885, 891, 891, 891, 8, 8, 8, 8, 8, 891, 8, 885,
99 : 891, 885, 885, 889, 906, 906, 906, 906, 906, 906, 912, 912, 912, 8, 891,
100 : 891, 891, 891, 912, 891, 906, 912, 906, 906, 889, 889, 927, 927, 927, 927,
101 : 927, 933, 933, 933, 906, 889, 927, 927, 927, 906, 906, 933, 906, 933, 906,
102 : 889, 948, 948, 948, 948, 948, 948, 954, 954, 954, 927, 889, 948, 948, 948,
103 : 927, 927, 954, 927, 954, 927, 927, 969, 969, 969, 969, 969, 969, 975, 975,
104 : 975, 906, 933, 933, 933, 933, 975, 933, 969, 975, 969, 969, 948, 990, 990,
105 : 990, 990, 994, 990, 996, 996, 996, 927, 954, 990, 990, 990, 954, 954, 996,
106 : 954, 996, 954, 927, 1011, 1011, 1011, 1011, 1011, 1011, 1017, 1017, 1017,
107 : 969, 927, 1011, 1011, 1011, 969, 969, 1017, 969, 1017, 969, 994, 1032,
108 : 1032, 1032, 1011, 927, 996, 996, 996, 1011, 996, 1032, 1011, 1032, 1011,
109 : 994, 994, 1047, 1047, 1047, 1047, 1047, 1053, 1053, 1053, 1011, 1032, 1032,
110 : 1032, 994, 1053, 1032, 1047, 1053, 1047, 1047, 994, 1068, 1068, 1068, 1068,
111 : 1068, 1068, 1074, 1074, 1074, 1047, 994, 1068, 1068, 1068, 1047, 1047,
112 : 1074, 1047, 1074, 1047, 1068, 1089, 1089, 729, 729, 729, 1094, 1094, 1094,
113 : 1047, 1074, 1089, 1089, 729, 1074, 1074, 1094, 1074, 1094, 1074, 1068,
114 : 1109, 1109, 771, 771, 1068, 1109, 1109, 771, 1089, 778, 778, 1089, 778,
115 : 729, 692, 1124, 1124, 1047, 1047, 729, 736, 736, 692, 1094, 736, 1124,
116 : 1094, 1124, 1047 } ;
117 :
118 : const matrix_info files [ ] =
119 : {
120 : { 1, "A.mtx" },
121 : { 1, "jagmesh7.mtx" },
122 : { 0, "west0067.mtx" }, // unsymmetric
123 : { 1, "bcsstk13.mtx" },
124 : { 1, "karate.mtx" },
125 : { 1, "ldbc-cdlp-undirected-example.mtx" },
126 : { 1, "ldbc-undirected-example-bool.mtx" },
127 : { 1, "ldbc-undirected-example-unweighted.mtx" },
128 : { 1, "ldbc-undirected-example.mtx" },
129 : { 1, "ldbc-wcc-example.mtx" },
130 : { 0, "" },
131 : } ;
132 :
133 : //****************************************************************************
134 1 : void test_cdlp (void)
135 : {
136 1 : LAGraph_Init (msg) ;
137 :
138 1 : for (int k = 0 ; ; k++)
139 10 : {
140 :
141 : // load the matrix as A
142 11 : const char *aname = files [k].name ;
143 11 : bool symmetric = files [k].symmetric ;
144 11 : if (strlen (aname) == 0) break;
145 10 : printf ("\n================================== %s:\n", aname) ;
146 10 : TEST_CASE (aname) ;
147 10 : snprintf (filename, LEN, LG_DATA_DIR "%s", aname) ;
148 10 : FILE *f = fopen (filename, "r") ;
149 10 : TEST_CHECK (f != NULL) ;
150 10 : OK (LAGraph_MMRead (&A, f, msg)) ;
151 :
152 : // construct a directed graph G with adjacency matrix A
153 10 : OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_DIRECTED, msg)) ;
154 10 : TEST_CHECK (A == NULL) ;
155 :
156 : // check for self-edges
157 10 : OK (LAGraph_Cached_NSelfEdges (G, msg)) ;
158 10 : bool sanitize = (G->nself_edges != 0) ;
159 :
160 10 : GrB_Vector c = NULL ;
161 : double t [2] ;
162 :
163 : // compute the communities with LAGraph_cdlp
164 10 : OK (LAGraph_cdlp (&c, G->A, symmetric, sanitize, 100, t, msg)) ;
165 :
166 : GrB_Index n ;
167 10 : OK (GrB_Vector_size (&n, c)) ;
168 10 : LAGraph_PrintLevel pr = (n <= 100) ? LAGraph_COMPLETE : LAGraph_SHORT ;
169 :
170 : // check result c for jagmesh7
171 10 : if (strcmp (aname, "jagmesh7.mtx") == 0)
172 : {
173 1 : GrB_Vector cgood = NULL ;
174 1 : OK (GrB_Vector_new (&cgood, GrB_UINT64, n)) ;
175 1139 : for (int k = 0 ; k < n ; k++)
176 : {
177 1138 : OK (GrB_Vector_setElement (cgood, cdlp_jagmesh7 [k], k)) ;
178 : }
179 1 : OK (GrB_wait (cgood, GrB_MATERIALIZE)) ;
180 1 : printf ("\ncdlp (known result):\n") ;
181 1 : OK (LAGraph_Vector_Print (cgood, pr, stdout, msg)) ;
182 1 : bool ok = false ;
183 1 : OK (LAGraph_Vector_IsEqual (&ok, c, cgood, msg)) ;
184 1 : TEST_CHECK (ok) ;
185 1 : OK (GrB_free (&cgood)) ;
186 : }
187 :
188 10 : printf ("\ncdlp:\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 1 : LAGraph_Finalize (msg) ;
196 1 : }
197 :
198 : //------------------------------------------------------------------------------
199 : // test_errors
200 : //------------------------------------------------------------------------------
201 :
202 1 : void test_errors (void)
203 : {
204 1 : LAGraph_Init (msg) ;
205 :
206 1 : snprintf (filename, LEN, LG_DATA_DIR "%s", "karate.mtx") ;
207 1 : FILE *f = fopen (filename, "r") ;
208 1 : TEST_CHECK (f != NULL) ;
209 1 : OK (LAGraph_MMRead (&A, f, msg)) ;
210 1 : TEST_MSG ("Loading of adjacency matrix failed") ;
211 :
212 : // construct an undirected graph G with adjacency matrix A
213 1 : OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_UNDIRECTED, msg)) ;
214 1 : TEST_CHECK (A == NULL) ;
215 :
216 1 : OK (LAGraph_Cached_NSelfEdges (G, msg)) ;
217 :
218 1 : GrB_Vector c = NULL ;
219 : double t [2] ;
220 :
221 : // c is NULL
222 1 : int result = LAGraph_cdlp (NULL, G->A, true, false, 100, t, msg) ;
223 1 : printf ("\nresult: %d\n", result) ;
224 1 : TEST_CHECK (result == GrB_NULL_POINTER) ;
225 :
226 : #if LAGRAPH_SUITESPARSE
227 : // G->A is held by column
228 1 : OK (GxB_set (G->A, GxB_FORMAT, GxB_BY_COL)) ;
229 1 : result = LAGraph_cdlp (&c, G->A, true, true, 100, t, msg) ;
230 1 : printf ("\nresult: %d\n", result) ;
231 1 : TEST_CHECK (result == GrB_INVALID_VALUE) ;
232 1 : TEST_CHECK (c == NULL) ;
233 : #endif
234 :
235 1 : OK (LAGraph_Delete (&G, msg)) ;
236 1 : LAGraph_Finalize (msg) ;
237 1 : }
238 :
239 : //****************************************************************************
240 :
241 : TEST_LIST = {
242 : {"cdlp", test_cdlp},
243 : {"cdlp_errors", test_errors},
244 : {NULL, NULL}
245 : };
|
