Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LAGraph/expirimental/test/test_SquareClustering.c: test cases for
3 : // square clustering
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 Erik Welch, NVIDIA
16 :
17 : //------------------------------------------------------------------------------
18 :
19 : #include <stdio.h>
20 : #include <acutest.h>
21 :
22 : #include <LAGraphX.h>
23 : #include <LAGraph_test.h>
24 : #include "LG_Xtest.h"
25 :
26 : char msg [LAGRAPH_MSG_LEN] ;
27 :
28 : // Data from NetworkX, test_lind_square_clustering: https://github.com/networkx\
29 : // /networkx/blob/main/networkx/algorithms/tests/test_cluster.py
30 : GrB_Index rows[19] = {1, 1, 1, 1, 2, 2, 3, 3, 6, 7, 6, 7, 7, 6, 6, 2, 2, 3, 3} ;
31 : GrB_Index cols[19] = {2, 3, 6, 7, 4, 5, 4, 5, 7, 8, 8, 9, 10, 11, 12, 13, 14,
32 : 15, 16} ;
33 : int64_t vals[19] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1} ;
34 :
35 : GrB_Index soln_indices[8] = {1, 2, 3, 4, 5, 6, 7, 8} ;
36 : double soln_values[8] = {
37 : 3.0 / 43.0,
38 : 3.0 / 17.0,
39 : 3.0 / 17.0,
40 : 1.0 / 3.0,
41 : 1.0 / 3.0,
42 : 1.0 / 27.0,
43 : 1.0 / 27.0,
44 : 1.0 / 5.0
45 : };
46 :
47 : //------------------------------------------------------------------------------
48 : // is_close: check whether two floats are close
49 : //------------------------------------------------------------------------------
50 :
51 8 : bool is_close (double a, double b)
52 : {
53 8 : double abs_diff = fabs(a - b) ;
54 8 : return abs_diff < 1e-6 ;
55 : }
56 :
57 1 : void test_SquareClustering (void)
58 : {
59 1 : LAGraph_Init (msg) ;
60 : // OK (LG_SET_BURBLE (true)) ;
61 :
62 :
63 1 : GrB_Matrix A = NULL ;
64 1 : LAGraph_Graph G = NULL ;
65 :
66 1 : GrB_Index n = 17;
67 1 : OK (GrB_Matrix_new (&A, GrB_INT64, n, n)) ;
68 1 : OK (GrB_Matrix_build_INT64 (A, rows, cols, vals, 19, GrB_PLUS_INT64)) ;
69 : // Symmetrize A
70 1 : OK (GrB_Matrix_eWiseAdd_BinaryOp(A, NULL, NULL, GrB_FIRST_INT64, A, A,
71 : GrB_DESC_T1));
72 1 : OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_UNDIRECTED, msg)) ;
73 1 : TEST_CHECK (A == NULL) ;
74 :
75 : // check for self-edges
76 1 : OK (LAGraph_Cached_NSelfEdges (G, msg)) ;
77 1 : bool sanitize = (G->nself_edges != 0) ;
78 :
79 1 : OK (LAGraph_Cached_OutDegree (G, msg)) ;
80 :
81 1 : GrB_Vector c = NULL ;
82 1 : OK (LAGraph_SquareClustering (&c, G, msg)) ;
83 :
84 : GrB_Index nvals;
85 1 : OK (GrB_Vector_nvals(&nvals, c)) ;
86 1 : TEST_CHECK (nvals == 8) ;
87 :
88 : // OK (GrB_Vector_new(&soln, GrB_FP64, n)) ;
89 : // OK (GrB_Vector_build_FP64(soln, soln_indices, soln_values, 8,
90 : // GrB_PLUS_FP64)) ;
91 : double val;
92 9 : for (GrB_Index i = 0 ; i < 8 ; ++i)
93 : {
94 8 : GrB_Vector_extractElement_FP64(&val, c, soln_indices[i]) ;
95 8 : TEST_CHECK (is_close(val, soln_values[i])) ;
96 : }
97 : // OK (GrB_free (&soln)) ;
98 :
99 1 : OK (GrB_free (&c)) ;
100 1 : OK (LAGraph_Delete (&G, msg)) ;
101 :
102 1 : LAGraph_Finalize (msg) ;
103 1 : };
104 :
105 : TEST_LIST = {
106 : {"SquareClustering", test_SquareClustering},
107 : // {"SquareClustering_errors", test_errors},
108 : {NULL, NULL}
109 : };
|