Line data Source code
1 : //----------------------------------------------------------------------------
2 : // LAGraph/src/test/test_TriangleCount.cpp: test cases for triangle
3 :
4 : // LAGraph, (c) 2019-2022 by The LAGraph Contributors, All Rights Reserved.
5 : // SPDX-License-Identifier: BSD-2-Clause
6 : //
7 : // For additional details (including references to third party source code and
8 : // other files) see the LICENSE file or contact permission@sei.cmu.edu. See
9 : // Contributors.txt for a full list of contributors. Created, in part, with
10 : // funding and support from the U.S. Government (see Acknowledgments.txt file).
11 : // DM22-0790
12 :
13 : //-----------------------------------------------------------------------------
14 :
15 : #include <stdio.h>
16 : #include <acutest.h>
17 : #include <LAGraphX.h>
18 : #include <LAGraph_test.h>
19 : #include <LG_Xtest.h>
20 : #include <LG_test.h>
21 :
22 : #include <graph_zachary_karate.h>
23 :
24 : char msg[LAGRAPH_MSG_LEN];
25 : LAGraph_Graph G = NULL;
26 :
27 : #define LEN 512
28 : char filename [LEN+1] ;
29 :
30 : int64_t karate_graphlet_counts [ ] =
31 : {
32 : 1,16,17,102,18,81,197,13,352,6,34,171,10,2,30,7,
33 : 1,9,19,24,12,73,56,33,32,8,80,27,6,2,18,7,
34 : 1,10,34,34,11,72,179,84,54,17,75,51,20,6,8,7,
35 : 1,6,20,5,10,49,11,56,1,5,81,5,0,4,7,7,
36 : 1,3,16,1,2,17,1,64,0,15,25,0,1,2,1,0,
37 : 1,4,15,3,3,15,14,64,0,14,25,2,1,2,2,0,
38 : 1,4,15,3,3,15,14,64,0,14,25,2,1,2,2,0,
39 : 1,4,25,0,6,37,0,87,0,5,53,0,0,11,0,4,
40 : 1,5,44,5,5,31,74,208,0,23,58,6,10,12,3,1,
41 : 1,2,25,1,0,40,15,130,0,26,0,0,5,0,0,0,
42 : 1,3,16,1,2,17,1,64,0,15,25,0,1,2,1,0,
43 : 1,1,15,0,0,17,0,87,0,18,0,0,0,0,0,0,
44 : 1,2,18,0,1,27,0,79,0,18,10,0,0,4,0,0,
45 : 1,5,41,4,6,27,69,192,0,20,53,6,10,11,0,4,
46 : 1,2,25,0,1,34,0,142,0,8,7,0,0,9,0,0,
47 : 1,2,25,0,1,34,0,142,0,8,7,0,0,9,0,0,
48 : 1,2,4,0,1,28,0,0,0,2,2,0,0,1,0,0,
49 : 1,2,21,0,1,27,0,96,0,16,9,0,0,6,0,0,
50 : 1,2,25,0,1,34,0,142,0,8,7,0,0,9,0,0,
51 : 1,3,37,2,1,31,43,201,0,31,9,1,5,6,0,0,
52 : 1,2,25,0,1,34,0,142,0,8,7,0,0,9,0,0,
53 : 1,2,21,0,1,27,0,96,0,16,9,0,0,6,0,0,
54 : 1,2,25,0,1,34,0,142,0,8,7,0,0,9,0,0,
55 : 1,5,27,6,4,36,39,111,2,5,43,5,4,9,2,1,
56 : 1,3,8,2,1,67,7,6,0,3,5,1,2,0,0,0,
57 : 1,3,9,2,1,62,7,6,0,6,5,1,3,0,0,0,
58 : 1,2,17,0,1,29,0,93,0,13,13,0,0,2,0,0,
59 : 1,4,29,5,1,47,53,120,2,25,14,2,8,2,0,0,
60 : 1,3,28,2,1,59,23,122,0,25,17,1,7,1,0,0,
61 : 1,4,24,2,4,34,11,111,0,4,43,1,0,9,2,1,
62 : 1,4,33,3,3,56,39,138,0,18,32,3,5,9,0,1,
63 : 1,6,42,12,3,34,149,216,9,25,23,10,10,9,1,0,
64 : 1,12,23,53,13,56,150,40,139,10,75,34,10,4,45,2,
65 : 1,17,18,121,15,81,210,3,507,9,26,123,25,1,48,2
66 : };
67 :
68 : int64_t A_graphlet_counts [ ] =
69 : {
70 : 1,3,8,1,2,1,0,2,0,5,2,0,3,4,1,0,
71 : 1,5,5,5,5,0,0,0,1,0,0,4,5,5,4,1,
72 : 1,5,3,3,7,0,1,0,0,0,5,1,1,2,7,2,
73 : 1,5,3,3,7,0,1,0,0,0,5,1,1,2,7,2,
74 : 1,3,8,1,2,1,0,2,0,5,2,0,3,4,1,0,
75 : 1,4,6,1,5,0,0,2,0,0,6,0,2,4,2,2,
76 : 1,5,5,5,5,0,0,0,1,0,0,4,5,5,4,1
77 : };
78 :
79 1 : void test_FastGraphletTransform(void)
80 : {
81 : #if LAGRAPH_SUITESPARSE
82 1 : LAGraph_Init (msg) ;
83 : // OK (LG_SET_BURBLE (true)) ;
84 :
85 1 : GrB_Matrix A = NULL, F_net = NULL ;
86 : GrB_Index n ;
87 1 : bool ok = 1 ;
88 :
89 : //--------------------------------------------------------------------------
90 : // karate
91 : //--------------------------------------------------------------------------
92 :
93 : {
94 : // create the karate graph
95 1 : snprintf (filename, LEN, LG_DATA_DIR "%s", "karate.mtx") ;
96 1 : FILE *f = fopen (filename, "r") ;
97 1 : TEST_CHECK (f != NULL) ;
98 1 : OK (LAGraph_MMRead (&A, f, msg)) ;
99 1 : OK (fclose (f)) ;
100 1 : OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_UNDIRECTED, msg)) ;
101 1 : TEST_CHECK (A == NULL) ; // A has been moved into G->A
102 :
103 1 : OK (LAGraph_DeleteSelfEdges (G, msg)) ;
104 :
105 : // get the net frequency matrix
106 1 : OK (LAGraph_FastGraphletTransform (&F_net, G, true, msg)) ;
107 1 : printf ("# Matrix: %s\n", "karate.mtx") ;
108 :
109 1 : OK (GrB_Matrix_nrows (&n, G->A)) ;
110 :
111 : // check that each element matches fglt result
112 35 : for (int i = 0 ; i < n ; i++) {
113 578 : for (int j = 0 ; j < 16 ; j++) {
114 : int64_t x;
115 544 : if (GrB_Matrix_extractElement (&x, F_net, j, i) == GrB_NO_VALUE)
116 2 : x = 0 ;
117 544 : ok &= (x == karate_graphlet_counts [16 * i + j]) ;
118 : }
119 : }
120 :
121 1 : TEST_CHECK (ok) ;
122 :
123 1 : OK (GrB_free (&F_net)) ;
124 1 : OK (LAGraph_Delete (&G, msg)) ;
125 : }
126 :
127 : //--------------------------------------------------------------------------
128 : // A
129 : //--------------------------------------------------------------------------
130 :
131 : {
132 : // create the A graph
133 1 : snprintf (filename, LEN, LG_DATA_DIR "%s", "A.mtx") ;
134 1 : FILE *f = fopen (filename, "r") ;
135 1 : TEST_CHECK (f != NULL) ;
136 1 : OK (LAGraph_MMRead (&A, f, msg)) ;
137 1 : OK (fclose (f)) ;
138 1 : OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_UNDIRECTED, msg)) ;
139 1 : TEST_CHECK (A == NULL) ; // A has been moved into G->A
140 :
141 1 : OK (LAGraph_DeleteSelfEdges (G, msg)) ;
142 :
143 : // get the net frequency matrix
144 1 : OK (LAGraph_FastGraphletTransform (&F_net, G, true, msg)) ;
145 1 : printf ("# Matrix: %s\n", "A.mtx") ;
146 :
147 1 : OK (GrB_Matrix_nrows (&n, G->A)) ;
148 :
149 : // check that each element matches fglt result
150 8 : for (int i = 0 ; i < n ; i++) {
151 119 : for (int j = 0 ; j < 16 ; j++) {
152 112 : int64_t x = 0 ;
153 112 : OK (GrB_Matrix_extractElement (&x, F_net, j, i)) ;
154 112 : ok &= (x == A_graphlet_counts [16 * i + j]) ;
155 : }
156 : }
157 :
158 1 : TEST_CHECK (ok) ;
159 :
160 1 : OK (GrB_free (&F_net)) ;
161 1 : OK (LAGraph_Delete (&G, msg)) ;
162 : }
163 :
164 : //--------------------------------------------------------------------------
165 :
166 1 : LAGraph_Finalize (msg) ;
167 : #endif
168 1 : }
169 :
170 :
171 : //****************************************************************************
172 : //****************************************************************************
173 : TEST_LIST = {
174 : {"FastGraphletTransform", test_FastGraphletTransform},
175 : {NULL, NULL}
176 : };
|