Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LAGraph/experimental/test/test_scc.c: tests for Strongly Connected Components
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 scc method, as LG_check_scc, and compare its results
19 : // with LAGraph_scc
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 : const char *name ;
36 : }
37 : matrix_info ;
38 :
39 : int scc_cover [7] = { 0, 0, 2, 0, 4, 2, 0 } ;
40 :
41 : const matrix_info files [ ] =
42 : {
43 : { "A2.mtx" },
44 : { "A.mtx" },
45 : { "bcsstk13.mtx" },
46 : { "cover.mtx" },
47 : { "cover_structure.mtx" },
48 : { "cryg2500.mtx" },
49 : { "full.mtx" },
50 : { "full_noheader.mtx" },
51 : { "full_symmetric.mtx" },
52 : { "jagmesh7.mtx" },
53 : { "karate.mtx" },
54 : { "ldbc-cdlp-directed-example.mtx" },
55 : { "ldbc-cdlp-undirected-example.mtx" },
56 : { "ldbc-directed-example-bool.mtx" },
57 : { "ldbc-directed-example.mtx" },
58 : { "ldbc-directed-example-unweighted.mtx" },
59 : { "ldbc-undirected-example-bool.mtx" },
60 : { "ldbc-undirected-example.mtx" },
61 : { "ldbc-undirected-example-unweighted.mtx" },
62 : { "ldbc-wcc-example.mtx" },
63 : { "LFAT5.mtx" },
64 : { "LFAT5_two.mtx" },
65 : { "matrix_bool.mtx" },
66 : { "matrix_fp32.mtx" },
67 : { "matrix_fp32_structure.mtx" },
68 : { "matrix_fp64.mtx" },
69 : { "matrix_int16.mtx" },
70 : { "matrix_int32.mtx" },
71 : { "matrix_int64.mtx" },
72 : { "matrix_int8.mtx" },
73 : { "matrix_uint16.mtx" },
74 : { "matrix_uint32.mtx" },
75 : { "matrix_uint64.mtx" },
76 : { "matrix_uint8.mtx" },
77 : { "msf1.mtx" },
78 : { "msf2.mtx" },
79 : { "msf3.mtx" },
80 : { "olm1000.mtx" },
81 : { "pushpull.mtx" },
82 : { "sample2.mtx" },
83 : { "sample.mtx" },
84 : { "structure.mtx" },
85 : { "test_BF.mtx" },
86 : { "test_FW_1000.mtx" },
87 : { "test_FW_2003.mtx" },
88 : { "test_FW_2500.mtx" },
89 : { "tree-example.mtx" },
90 : { "west0067_jumbled.mtx" },
91 : { "west0067.mtx" },
92 : { "west0067_noheader.mtx" },
93 : { "zenios.mtx" },
94 : { "" },
95 : } ;
96 :
97 : //****************************************************************************
98 1 : void test_scc (void)
99 : {
100 : #if LAGRAPH_SUITESPARSE
101 1 : LAGraph_Init (msg) ;
102 :
103 1 : for (int k = 0 ; ; k++)
104 51 : {
105 :
106 : // load the matrix as A
107 52 : const char *aname = files [k].name ;
108 52 : if (strlen (aname) == 0) break;
109 51 : printf ("\n================================== %s:\n", aname) ;
110 51 : TEST_CASE (aname) ;
111 51 : snprintf (filename, LEN, LG_DATA_DIR "%s", aname) ;
112 51 : FILE *f = fopen (filename, "r") ;
113 51 : TEST_CHECK (f != NULL) ;
114 51 : OK (LAGraph_MMRead (&A, f, msg)) ;
115 51 : fclose (f) ;
116 :
117 : // construct a directed graph G with adjacency matrix A
118 51 : OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_DIRECTED, msg)) ;
119 51 : TEST_CHECK (A == NULL) ;
120 :
121 51 : GrB_Vector c = NULL ;
122 :
123 : // find the strongly connected components with LAGraph_scc
124 51 : OK (LAGraph_scc (&c, G->A, msg)) ;
125 :
126 : GrB_Index n ;
127 51 : OK (GrB_Vector_size (&n, c)) ;
128 51 : LAGraph_PrintLevel pr = (n <= 100) ? LAGraph_COMPLETE : LAGraph_SHORT ;
129 :
130 : // check result c for cover
131 51 : if (strcmp (aname, "cover.mtx") == 0)
132 : {
133 1 : GrB_Vector cgood = NULL ;
134 1 : OK (GrB_Vector_new (&cgood, GrB_UINT64, n)) ;
135 8 : for (int k = 0 ; k < n ; k++)
136 : {
137 7 : OK (GrB_Vector_setElement (cgood, scc_cover [k], k)) ;
138 : }
139 1 : OK (GrB_wait (cgood, GrB_MATERIALIZE)) ;
140 1 : printf ("\nscc (known result):\n") ;
141 1 : OK (LAGraph_Vector_Print (cgood, pr, stdout, msg)) ;
142 1 : bool ok = false ;
143 1 : OK (LAGraph_Vector_IsEqual (&ok, c, cgood, msg)) ;
144 1 : TEST_CHECK (ok) ;
145 1 : OK (GrB_free (&cgood)) ;
146 : }
147 :
148 51 : printf ("\nscc:\n") ;
149 51 : OK (LAGraph_Vector_Print (c, pr, stdout, msg)) ;
150 51 : OK (GrB_free (&c)) ;
151 51 : OK (LAGraph_Delete (&G, msg)) ;
152 : }
153 :
154 1 : LAGraph_Finalize (msg) ;
155 : #endif
156 1 : }
157 :
158 : //------------------------------------------------------------------------------
159 : // test_errors
160 : //------------------------------------------------------------------------------
161 :
162 1 : void test_errors (void)
163 : {
164 : #if LAGRAPH_SUITESPARSE
165 1 : LAGraph_Init (msg) ;
166 :
167 1 : GrB_Vector c = NULL ;
168 1 : GrB_Matrix A = NULL ;
169 :
170 : // c and A are NULL
171 1 : int result = LAGraph_scc (NULL, A, msg) ;
172 1 : printf ("\nresult: %d\n", result) ;
173 1 : TEST_CHECK (result == GrB_NULL_POINTER) ;
174 :
175 : // A is rectangular
176 1 : OK (GrB_Matrix_new (&A, GrB_BOOL, 3, 4)) ;
177 1 : result = LAGraph_scc (&c, A, msg) ;
178 1 : TEST_CHECK (result == GrB_DIMENSION_MISMATCH) ;
179 :
180 1 : OK (GrB_free (&c)) ;
181 1 : OK (GrB_free (&A)) ;
182 1 : LAGraph_Finalize (msg) ;
183 : #endif
184 1 : }
185 :
186 : //****************************************************************************
187 :
188 : TEST_LIST = {
189 : {"scc", test_scc},
190 : {"scc_errors", test_errors},
191 : {NULL, NULL}
192 : };
|
