Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LAGraph/src/test/test_TriangleCentrality.c: test cases for triangle
3 : // centrality
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 Timothy A. Davis, Texas A&M University
16 :
17 : //------------------------------------------------------------------------------
18 :
19 : #include <stdio.h>
20 : #include <acutest.h>
21 :
22 : #include <LAGraphX.h>
23 : #include <LAGraph_test.h>
24 :
25 : char msg [LAGRAPH_MSG_LEN] ;
26 : LAGraph_Graph G = NULL ;
27 : GrB_Matrix A = NULL ;
28 : GrB_Matrix C = NULL ;
29 : #define LEN 512
30 : char filename [LEN+1] ;
31 :
32 : typedef struct
33 : {
34 : uint64_t ntriangles ;
35 : const char *name ;
36 : }
37 : matrix_info ;
38 :
39 : const matrix_info files [ ] =
40 : {
41 : { 11, "A.mtx" },
42 : { 2016, "jagmesh7.mtx" },
43 : { 342300, "bcsstk13.mtx" },
44 : { 45, "karate.mtx" },
45 : { 6, "ldbc-cdlp-undirected-example.mtx" },
46 : { 4, "ldbc-undirected-example-bool.mtx" },
47 : { 4, "ldbc-undirected-example-unweighted.mtx" },
48 : { 4, "ldbc-undirected-example.mtx" },
49 : { 5, "ldbc-wcc-example.mtx" },
50 : { 0, "" },
51 : } ;
52 :
53 : //****************************************************************************
54 1 : void test_TriangleCentrality (void)
55 : {
56 1 : LAGraph_Init (msg) ;
57 :
58 1 : for (int k = 0 ; ; k++)
59 9 : {
60 :
61 : // load the matrix as A
62 10 : const char *aname = files [k].name ;
63 10 : uint64_t ntriangles = files [k].ntriangles ;
64 10 : if (strlen (aname) == 0) break;
65 9 : printf ("\n================================== %s:\n", aname) ;
66 9 : TEST_CASE (aname) ;
67 9 : snprintf (filename, LEN, LG_DATA_DIR "%s", aname) ;
68 9 : FILE *f = fopen (filename, "r") ;
69 9 : TEST_CHECK (f != NULL) ;
70 9 : OK (LAGraph_MMRead (&A, f, msg)) ;
71 :
72 : // C = spones (A), in FP64, required for methods 1 and 1.5
73 : GrB_Index n ;
74 9 : OK (GrB_Matrix_nrows (&n, A)) ;
75 9 : OK (GrB_Matrix_new (&C, GrB_FP64, n, n)) ;
76 9 : OK (GrB_assign (C, A, NULL, (double) 1, GrB_ALL, n, GrB_ALL, n,
77 : GrB_DESC_S)) ;
78 9 : OK (GrB_free (&A)) ;
79 9 : TEST_CHECK (A == NULL) ;
80 9 : OK (fclose (f)) ;
81 9 : TEST_MSG ("Loading of adjacency matrix failed") ;
82 :
83 : // construct an undirected graph G with adjacency matrix C
84 9 : OK (LAGraph_New (&G, &C, LAGraph_ADJACENCY_UNDIRECTED, msg)) ;
85 9 : TEST_CHECK (C == NULL) ;
86 :
87 : // check for self-edges
88 9 : OK (LAGraph_Cached_NSelfEdges (G, msg)) ;
89 9 : if (G->nself_edges != 0)
90 : {
91 : // remove self-edges
92 2 : printf ("graph has %g self edges\n", (double) G->nself_edges) ;
93 2 : OK (LAGraph_DeleteSelfEdges (G, msg)) ;
94 2 : printf ("now has %g self edges\n", (double) G->nself_edges) ;
95 2 : TEST_CHECK (G->nself_edges == 0) ;
96 : }
97 :
98 : uint64_t ntri ;
99 9 : GrB_Vector c = NULL ;
100 45 : for (int method = 0 ; method <= 3 ; method++)
101 : {
102 36 : printf ("\nMethod: %d\n", method) ;
103 :
104 : // compute the triangle centrality
105 36 : OK (LAGraph_VertexCentrality_Triangle (&c, &ntri, method, G, msg)) ;
106 36 : printf ("# of triangles: %g\n", (double) ntri) ;
107 36 : TEST_CHECK (ntri == ntriangles) ;
108 :
109 : LAGraph_PrintLevel
110 36 : pr = (n <= 100) ? LAGraph_COMPLETE : LAGraph_SHORT ;
111 36 : printf ("\ncentrality:\n") ;
112 36 : OK (LAGraph_Vector_Print (c, pr, stdout, msg)) ;
113 36 : OK (GrB_free (&c)) ;
114 : }
115 :
116 : // convert to directed with symmetric structure and recompute
117 9 : G->kind = LAGraph_ADJACENCY_DIRECTED ;
118 9 : OK (LAGraph_VertexCentrality_Triangle (&c, &ntri, 0, G, msg)) ;
119 9 : TEST_CHECK (ntri == ntriangles) ;
120 9 : GrB_free (&c) ;
121 :
122 9 : OK (LAGraph_Delete (&G, msg)) ;
123 : }
124 :
125 1 : LAGraph_Finalize (msg) ;
126 1 : }
127 :
128 : //------------------------------------------------------------------------------
129 : // test_errors
130 : //------------------------------------------------------------------------------
131 :
132 1 : void test_errors (void)
133 : {
134 1 : LAGraph_Init (msg) ;
135 :
136 1 : snprintf (filename, LEN, LG_DATA_DIR "%s", "karate.mtx") ;
137 1 : FILE *f = fopen (filename, "r") ;
138 1 : TEST_CHECK (f != NULL) ;
139 1 : OK (LAGraph_MMRead (&A, f, msg)) ;
140 1 : TEST_MSG ("Loading of adjacency matrix failed") ;
141 :
142 : // construct an undirected graph G with adjacency matrix A
143 1 : OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_UNDIRECTED, msg)) ;
144 1 : TEST_CHECK (A == NULL) ;
145 :
146 1 : OK (LAGraph_Cached_NSelfEdges (G, msg)) ;
147 :
148 : uint64_t ntri ;
149 1 : GrB_Vector c = NULL ;
150 :
151 : // c is NULL
152 1 : int result = LAGraph_VertexCentrality_Triangle (NULL, &ntri, 3, G, msg) ;
153 1 : printf ("\nresult: %d %s\n", result, msg) ;
154 1 : TEST_CHECK (result == GrB_NULL_POINTER) ;
155 :
156 : // G is invalid
157 1 : result = LAGraph_VertexCentrality_Triangle (&c, &ntri, 3, NULL, msg) ;
158 1 : printf ("\nresult: %d %s\n", result, msg) ;
159 1 : TEST_CHECK (result == GrB_NULL_POINTER) ;
160 1 : TEST_CHECK (c == NULL) ;
161 :
162 : // G may have self edges
163 1 : G->nself_edges = LAGRAPH_UNKNOWN ;
164 1 : result = LAGraph_VertexCentrality_Triangle (&c, &ntri, 3, G, msg) ;
165 1 : printf ("\nresult: %d %s\n", result, msg) ;
166 1 : TEST_CHECK (result == -1004) ;
167 1 : TEST_CHECK (c == NULL) ;
168 :
169 : // G is undirected
170 1 : G->nself_edges = 0 ;
171 1 : G->kind = LAGraph_ADJACENCY_DIRECTED ;
172 1 : G->is_symmetric_structure = LAGraph_FALSE ;
173 1 : result = LAGraph_VertexCentrality_Triangle (&c, &ntri, 3, G, msg) ;
174 1 : printf ("\nresult: %d %s\n", result, msg) ;
175 1 : TEST_CHECK (result == -1005) ;
176 1 : TEST_CHECK (c == NULL) ;
177 :
178 1 : OK (LAGraph_Delete (&G, msg)) ;
179 1 : LAGraph_Finalize (msg) ;
180 1 : }
181 :
182 :
183 : //****************************************************************************
184 :
185 : TEST_LIST = {
186 : {"TriangleCentrality", test_TriangleCentrality},
187 : {"TriangleCentrality_errors", test_errors},
188 : {NULL, NULL}
189 : };
|
