Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LAGraph/experimental/test/test_diameter.c: test diameter
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: vector results (peripheral, eccentricity, level, and parent) are not
19 : // checked with exact values
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 : GrB_Matrix C = NULL ;
31 : GrB_Vector peripheral = NULL ;
32 : GrB_Matrix level = NULL ;
33 : GrB_Matrix parent = NULL ;
34 : GrB_Vector sources = NULL ;
35 : GrB_Vector est_peripheral = NULL ;
36 : GrB_Vector eccentricity = NULL ;
37 : GrB_Index n ;
38 : #define LEN 512
39 : char filename [LEN+1] ;
40 :
41 : typedef struct
42 : {
43 : int diameter ;
44 : bool symmetric ;
45 : const char *name ;
46 : }
47 : matrix_info ;
48 :
49 : const matrix_info files [ ] =
50 : {
51 : { 2, 1, "A.mtx" },
52 : { 60, 1, "jagmesh7.mtx" },
53 : { 6, 0, "west0067.mtx" }, // unsymmetric
54 : { 11, 1, "bcsstk13.mtx" },
55 : { 5, 1, "karate.mtx" },
56 : { 4, 1, "ldbc-cdlp-undirected-example.mtx" },
57 : { 4, 1, "ldbc-undirected-example-bool.mtx" },
58 : { 4, 1, "ldbc-undirected-example-unweighted.mtx" },
59 : { 4, 1, "ldbc-undirected-example.mtx" },
60 : { 3, 1, "ldbc-wcc-example.mtx" },
61 : { 0, 0, "" },
62 : } ;
63 :
64 : #undef OK
65 : #define OK(method) \
66 : { \
67 : GrB_Info info = method ; \
68 : if (info != GrB_SUCCESS) \
69 : { \
70 : printf ("info: %d, msg: %s\n", info, msg) ; \
71 : TEST_CHECK (false) ; \
72 : } \
73 : }
74 :
75 : //------------------------------------------------------------------------------
76 : // test_diameter
77 : //------------------------------------------------------------------------------
78 :
79 1 : void test_diameter (void)
80 : {
81 : #if LAGRAPH_SUITESPARSE
82 1 : OK (LAGraph_Init (msg)) ;
83 :
84 1 : for (int k = 0 ; ; k++)
85 10 : {
86 :
87 : // load the matrix as A
88 11 : const char *aname = files [k].name ;
89 11 : bool symmetric = files [k].symmetric ;
90 11 : if (strlen (aname) == 0) break;
91 10 : printf ("\n================================== %s:\n", aname) ;
92 10 : TEST_CASE (aname) ;
93 10 : snprintf (filename, LEN, LG_DATA_DIR "%s", aname) ;
94 10 : FILE *f = fopen (filename, "r") ;
95 10 : TEST_CHECK (f != NULL) ;
96 10 : OK (LAGraph_MMRead (&A, f, msg)) ;
97 10 : fclose (f) ;
98 10 : OK (GrB_Matrix_nrows (&n, A)) ;
99 10 : LAGraph_PrintLevel pr = (n <= 100) ? LAGraph_COMPLETE : LAGraph_SHORT ;
100 10 : OK (LAGraph_Matrix_Print (A, pr, stdout, msg)) ;
101 :
102 : // construct a directed graph G with adjacency matrix S
103 10 : int kind = symmetric ?
104 10 : LAGraph_ADJACENCY_UNDIRECTED :
105 : LAGraph_ADJACENCY_DIRECTED ;
106 10 : OK (LAGraph_New (&G, &A, kind, msg)) ;
107 10 : TEST_CHECK (A == NULL) ;
108 :
109 : // compute the exact diameter
110 10 : GrB_Index diameter = 0 ;
111 10 : OK (LAGraph_ExactDiameter (&diameter, &peripheral, &eccentricity,
112 : G, 8, msg)) ;
113 :
114 10 : printf ("\n%s exact diameter: %" PRIu64 "\n", aname, diameter) ;
115 10 : TEST_CHECK (diameter == files [k].diameter) ;
116 :
117 10 : printf ("\nperipheral:\n") ;
118 10 : OK (LAGraph_Vector_Print (peripheral, pr, stdout, msg)) ;
119 10 : printf ("\neccentricity:\n") ;
120 10 : OK (LAGraph_Vector_Print (eccentricity, pr, stdout, msg)) ;
121 :
122 30 : for (int jit = 0 ; jit <= 1 ; jit++)
123 : {
124 20 : OK (LG_SET_JIT (jit ? GxB_JIT_ON : GxB_JIT_OFF)) ;
125 : // compute the estimated diameter
126 20 : GrB_Index estimated_diameter = 0 ;
127 20 : OK (LAGraph_EstimateDiameter (&estimated_diameter, &est_peripheral,
128 : G, 8, 4, 42, msg)) ;
129 20 : printf ("\nest diameter: %" PRIu64 "\n", estimated_diameter) ;
130 20 : TEST_CHECK (estimated_diameter <= diameter) ;
131 20 : printf ("\nest_peripheral:\n") ;
132 20 : OK (LAGraph_Vector_Print (est_peripheral, pr, stdout, msg)) ;
133 20 : OK (GrB_free (&est_peripheral)) ;
134 : }
135 :
136 : // try the multisource BFS directly
137 10 : OK (GrB_Vector_new (&sources, GrB_INT64, 4)) ;
138 50 : for (int i = 0 ; i < 4 ; i++)
139 : {
140 40 : OK (GrB_Vector_setElement (sources, i, i)) ;
141 : }
142 10 : OK (GrB_wait (sources, GrB_MATERIALIZE)) ;
143 10 : printf ("\nsource nodes for multiBFS:\n") ;
144 10 : OK (LAGraph_Vector_Print (sources, 5, stdout, msg)) ;
145 10 : OK (LAGraph_MultiSourceBFS (&level, &parent, G, sources, msg)) ;
146 10 : printf ("\nlevel:\n") ;
147 10 : OK (LAGraph_Matrix_Print (level, pr, stdout, msg)) ;
148 10 : printf ("\nparent:\n") ;
149 10 : OK (LAGraph_Matrix_Print (parent, pr, stdout, msg)) ;
150 :
151 10 : OK (GrB_free (&sources)) ;
152 10 : OK (GrB_free (&level)) ;
153 10 : OK (GrB_free (&parent)) ;
154 10 : OK (GrB_free (&peripheral)) ;
155 10 : OK (GrB_free (&eccentricity)) ;
156 10 : OK (LAGraph_Delete (&G, msg)) ;
157 : }
158 :
159 1 : OK (LAGraph_Finalize (msg)) ;
160 : #endif
161 1 : }
162 :
163 : //------------------------------------------------------------------------------
164 : // test_diameter_huge
165 : //------------------------------------------------------------------------------
166 :
167 1 : void test_diameter_huge (void)
168 : {
169 : #if LAGRAPH_SUITESPARSE
170 1 : OK (LAGraph_Init (msg)) ;
171 1 : OK (LG_SET_JIT (LG_JIT_OFF)) ;
172 :
173 1 : snprintf (filename, LEN, LG_DATA_DIR "%s", "karate.mtx") ;
174 1 : FILE *f = fopen (filename, "r") ;
175 1 : TEST_CHECK (f != NULL) ;
176 1 : OK (LAGraph_MMRead (&C, f, msg)) ;
177 1 : fclose (f) ;
178 1 : OK (GrB_Matrix_nrows (&n, C)) ;
179 1 : OK (LAGraph_Matrix_Print (C, 5, stdout, msg)) ;
180 :
181 1 : GrB_Index *I = NULL ;
182 1 : OK (LAGraph_Malloc ((void **) &I, n, sizeof (uint64_t), msg)) ;
183 35 : for (int k = 0 ; k < n ; k++)
184 : {
185 34 : I [k] = k ;
186 : }
187 :
188 : // A (0:n-1, 0:n-1) = C, where C is n-by-n
189 1 : OK (GrB_Matrix_new (&A, GrB_BOOL, UINT32_MAX, UINT32_MAX)) ;
190 1 : OK (GrB_assign (A, NULL, NULL, C, I, n, I, n, NULL)) ;
191 :
192 : // construct the graph
193 1 : OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_UNDIRECTED, msg)) ;
194 1 : TEST_CHECK (A == NULL) ;
195 :
196 : // compute the estimated diameter
197 1 : GrB_Index estimated_diameter = 0 ;
198 1 : OK (LAGraph_EstimateDiameter (&estimated_diameter, &est_peripheral,
199 : G, 8, 4, 42, msg)) ;
200 1 : printf ("\nest diameter: %" PRIu64 "\n", estimated_diameter) ;
201 1 : printf ("\nest_peripheral:\n") ;
202 1 : OK (LAGraph_Vector_Print (est_peripheral, 2, stdout, msg)) ;
203 1 : OK (GrB_free (&est_peripheral)) ;
204 :
205 : // try the multisource BFS directly
206 1 : OK (GrB_Vector_new (&sources, GrB_INT64, 4)) ;
207 5 : for (int i = 0 ; i < 4 ; i++)
208 : {
209 4 : OK (GrB_Vector_setElement (sources, i, i)) ;
210 : }
211 1 : OK (GrB_wait (sources, GrB_MATERIALIZE)) ;
212 1 : printf ("\nsource nodes for multiBFS:\n") ;
213 1 : OK (LAGraph_Vector_Print (sources, 5, stdout, msg)) ;
214 1 : OK (LAGraph_MultiSourceBFS (&level, &parent, G, sources, msg)) ;
215 1 : printf ("\nlevel:\n") ;
216 1 : OK (LAGraph_Matrix_Print (level, 2, stdout, msg)) ;
217 1 : printf ("\nparent:\n") ;
218 1 : OK (LAGraph_Matrix_Print (parent, 2, stdout, msg)) ;
219 :
220 1 : OK (GrB_free (&sources)) ;
221 1 : OK (GrB_free (&level)) ;
222 1 : OK (GrB_free (&parent)) ;
223 1 : OK (GrB_free (&C)) ;
224 1 : OK (LAGraph_Free ((void **) &I, msg)) ;
225 1 : OK (LAGraph_Delete (&G, msg)) ;
226 :
227 1 : OK (LAGraph_Finalize (msg)) ;
228 : #endif
229 1 : }
230 :
231 : //------------------------------------------------------------------------------
232 : // test_errors
233 : //------------------------------------------------------------------------------
234 :
235 1 : void test_errors (void)
236 : {
237 : #if LAGRAPH_SUITESPARSE
238 1 : LAGraph_Init (msg) ;
239 : // TODO: add error tests here
240 1 : LAGraph_Finalize (msg) ;
241 : #endif
242 1 : }
243 :
244 : //****************************************************************************
245 :
246 : TEST_LIST = {
247 : {"diameter", test_diameter},
248 : {"diameter_huge", test_diameter_huge},
249 : {"diameter_errors", test_errors},
250 : {NULL, NULL}
251 : } ;
252 :
|
