Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LAGraph/src/test/LG_check_cc: stand-alone test for CC
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 : #define LG_FREE_WORK \
19 : { \
20 : LAGraph_Free ((void **) &queue, NULL) ; \
21 : LAGraph_Free ((void **) &component_in, NULL) ; \
22 : LAGraph_Free ((void **) &visited, NULL) ; \
23 : LAGraph_Free ((void **) &neighbors, NULL) ; \
24 : GrB_free (&Row) ; \
25 : }
26 :
27 : #define LG_FREE_ALL \
28 : { \
29 : LG_FREE_WORK ; \
30 : LAGraph_Free ((void **) &Ap, NULL) ; \
31 : LAGraph_Free ((void **) &Aj, NULL) ; \
32 : LAGraph_Free ((void **) &Ax, NULL) ; \
33 : }
34 :
35 : #include "LG_internal.h"
36 : #include "LG_test.h"
37 :
38 : // The output of LAGr_ConnectedComponents is a vector Component, where
39 : // Component(i)=s if node i is in the connected compononent whose
40 : // representative node is node s. If s is a representative, then
41 : // Component(s)=s. The number of connected components in the graph G is the
42 : // number of representatives.
43 :
44 : //------------------------------------------------------------------------------
45 : // test the results from LAGr_ConnectedComponents
46 : //------------------------------------------------------------------------------
47 :
48 : // Because this method does on GxB_unpack on G->A, it should not be used in a
49 : // brutal memory test, unless the caller is prepared to reconstruct G->A
50 : // when the brutal test causes this method to return early.
51 :
52 97 : int LG_check_cc
53 : (
54 : // input
55 : GrB_Vector Component, // Component(i)=s if node is in Component s
56 : LAGraph_Graph G,
57 : char *msg
58 : )
59 : {
60 :
61 : //--------------------------------------------------------------------------
62 : // check inputs
63 : //--------------------------------------------------------------------------
64 :
65 97 : double tt = LAGraph_WallClockTime ( ) ;
66 97 : GrB_Vector Row = NULL ;
67 97 : GrB_Index *Ap = NULL, *Aj = NULL, *neighbors = NULL ;
68 97 : void *Ax = NULL ;
69 : GrB_Index Ap_size, Aj_size, Ax_size, n, ncols ;
70 97 : int64_t *queue = NULL, *component_in = NULL ;
71 97 : bool *visited = NULL ;
72 97 : LG_TRY (LAGraph_CheckGraph (G, msg)) ;
73 97 : GRB_TRY (GrB_Matrix_nrows (&n, G->A)) ;
74 97 : GRB_TRY (GrB_Matrix_ncols (&ncols, G->A)) ;
75 97 : LG_ASSERT (Component != NULL, GrB_NULL_POINTER) ;
76 :
77 97 : LG_ASSERT_MSG ((G->kind == LAGraph_ADJACENCY_UNDIRECTED ||
78 : (G->kind == LAGraph_ADJACENCY_DIRECTED &&
79 : G->is_symmetric_structure == LAGraph_TRUE)),
80 : LAGRAPH_SYMMETRIC_STRUCTURE_REQUIRED,
81 : "G->A must be known to be symmetric") ;
82 :
83 : //--------------------------------------------------------------------------
84 : // allocate workspace
85 : //--------------------------------------------------------------------------
86 :
87 97 : LG_TRY (LAGraph_Calloc ((void **) &queue, n, sizeof (int64_t), msg)) ;
88 :
89 : //--------------------------------------------------------------------------
90 : // get the contents of the Component vector
91 : //--------------------------------------------------------------------------
92 :
93 97 : LG_TRY (LAGraph_Malloc ((void **) &component_in, n, sizeof (int64_t), msg)) ;
94 97 : LG_TRY (LG_check_vector (component_in, Component, n, -1)) ;
95 :
96 : //--------------------------------------------------------------------------
97 : // find the # of connected components, according to Component vector
98 : //--------------------------------------------------------------------------
99 :
100 97 : int64_t *count = queue ; // use queue as workspace
101 97 : int64_t ncomp_in = 0 ;
102 65165 : for (int64_t i = 0 ; i < n ; i++)
103 : {
104 65068 : int64_t comp = component_in [i] ;
105 65068 : LG_ASSERT (comp >= 0 && comp < n, -2000) ;
106 65068 : count [comp]++ ;
107 65068 : if (comp == i)
108 : {
109 : // this is the representative of its component
110 27182 : ncomp_in++ ;
111 : }
112 : }
113 97 : printf ("# of components: %g\n", (double) ncomp_in) ;
114 :
115 97 : if (n < 1000)
116 : {
117 1021 : for (int64_t i = 0 ; i < n ; i++)
118 : {
119 956 : if (component_in [i] == i)
120 : {
121 126 : printf ("Component %g, size %g\n", (double) i,
122 126 : (double) count [i]) ;
123 : }
124 : }
125 : }
126 :
127 : //--------------------------------------------------------------------------
128 : // unpack the matrix in CSR form for SuiteSparse:GraphBLAS
129 : //--------------------------------------------------------------------------
130 :
131 : #if LAGRAPH_SUITESPARSE
132 : bool iso, jumbled ;
133 97 : GRB_TRY (GxB_Matrix_unpack_CSR (G->A,
134 : &Ap, &Aj, &Ax, &Ap_size, &Aj_size, &Ax_size, &iso, &jumbled, NULL)) ;
135 : #endif
136 :
137 : //--------------------------------------------------------------------------
138 : // find the connected components via repeated BFS
139 : //--------------------------------------------------------------------------
140 :
141 97 : tt = LAGraph_WallClockTime ( ) - tt ;
142 97 : printf ("LG_check_cc init time: %g sec\n", tt) ;
143 97 : tt = LAGraph_WallClockTime ( ) ;
144 :
145 97 : LG_TRY (LAGraph_Calloc ((void **) &visited, n, sizeof (bool), msg)) ;
146 :
147 : #if !LAGRAPH_SUITESPARSE
148 : GRB_TRY (GrB_Vector_new (&Row, GrB_BOOL, n)) ;
149 : LG_TRY (LAGraph_Malloc ((void **) &neighbors, n, sizeof (GrB_Index), msg)) ;
150 : #endif
151 :
152 97 : int64_t ncomp = 0 ;
153 :
154 65165 : for (int64_t src = 0 ; src < n ; src++)
155 : {
156 : // skip this node if already visited
157 65068 : if (visited [src]) continue ;
158 :
159 : // src node is part of a new connected component, comp
160 27182 : int64_t comp = component_in [src] ;
161 27182 : ncomp++ ;
162 27182 : LG_ASSERT_MSG (ncomp <= ncomp_in, -2001, "wrong # of components") ;
163 :
164 27182 : queue [0] = src ;
165 27182 : int64_t head = 0 ;
166 27182 : int64_t tail = 1 ;
167 27182 : visited [src] = true ; // src is visited
168 :
169 92250 : while (head < tail)
170 : {
171 : // dequeue the node at the head of the queue
172 65068 : int64_t u = queue [head++] ;
173 :
174 : #if LAGRAPH_SUITESPARSE
175 : // directly access the indices of entries in A(u,:)
176 65068 : GrB_Index degree = Ap [u+1] - Ap [u] ;
177 65068 : GrB_Index *node_u_adjacency_list = Aj + Ap [u] ;
178 : #else
179 : // extract the indices of entries in A(u,:)
180 : GrB_Index degree = n ;
181 : GRB_TRY (GrB_Col_extract (Row, NULL, NULL, G->A, GrB_ALL, n, u,
182 : GrB_DESC_T0)) ;
183 : GRB_TRY (GrB_Vector_extractTuples_BOOL (neighbors, NULL, °ree,
184 : Row)) ;
185 : GrB_Index *node_u_adjacency_list = neighbors ;
186 : #endif
187 :
188 : // traverse all entries in A(u,:)
189 1017016 : for (int64_t k = 0 ; k < degree ; k++)
190 : {
191 : // consider edge (u,v)
192 951948 : int64_t v = node_u_adjacency_list [k] ;
193 : // ensure v is in the same connected component as the src node
194 951948 : LG_ASSERT (comp == component_in [u], -2002) ;
195 : // printf (" seen: %ld\n", v) ;
196 951948 : if (!visited [v])
197 : {
198 : // node v is not yet visited; set its level and add to the
199 : // end of the queue
200 37886 : visited [v] = true ;
201 37886 : queue [tail++] = v ;
202 : }
203 : }
204 : }
205 : }
206 :
207 97 : LG_ASSERT_MSG (ncomp == ncomp_in, -2001, "wrong # of components") ;
208 :
209 97 : tt = LAGraph_WallClockTime ( ) - tt ;
210 97 : printf ("LG_check_cc component time: %g sec\n", tt) ;
211 97 : tt = LAGraph_WallClockTime ( ) ;
212 :
213 : //--------------------------------------------------------------------------
214 : // repack the matrix in CSR form for SuiteSparse:GraphBLAS
215 : //--------------------------------------------------------------------------
216 :
217 : #if LAGRAPH_SUITESPARSE
218 97 : GRB_TRY (GxB_Matrix_pack_CSR (G->A,
219 : &Ap, &Aj, &Ax, Ap_size, Aj_size, Ax_size, iso, jumbled, NULL)) ;
220 : #endif
221 :
222 97 : LG_FREE_WORK ;
223 :
224 97 : tt = LAGraph_WallClockTime ( ) - tt ;
225 97 : printf ("LG_check_cc check time: %g sec\n", tt) ;
226 :
227 97 : return (GrB_SUCCESS) ;
228 : }
|
