Line data Source code
1 : //----------------------------------------------------------------------------
2 : // LAGraph/expirimental/test/test_KCoreDecompose.c: test cases for k-core
3 : // decomposition
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 Pranav Konduri, 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 : #include "LG_Xtest.h"
25 :
26 : char msg [LAGRAPH_MSG_LEN] ;
27 : LAGraph_Graph G = NULL ;
28 : GrB_Matrix A = NULL, D1 = NULL, D2 = NULL;
29 : GrB_Vector c = NULL;
30 : #define LEN 512
31 : char filename [LEN+1] ;
32 :
33 : typedef struct
34 : {
35 : uint64_t kval ;
36 : const char *name ;
37 : }
38 : matrix_info ;
39 :
40 : const matrix_info files [ ] =
41 : {
42 : { 4, "karate.mtx" },
43 : { 6, "west0067.mtx" },
44 : // { 10, "amazon0601.mtx" },
45 : // { 64, "cit-Patents.mtx"},
46 : // { 2208, "hollywood-2009.mtx"},
47 : // { 111, "as-Skitter.mtx"},
48 : { 0, "" },
49 : } ;
50 :
51 :
52 1 : void test_KCoreDecompose (void)
53 : {
54 : #if LAGRAPH_SUITESPARSE
55 1 : LAGraph_Init (msg) ;
56 :
57 1 : for (int k = 0 ; ; k++)
58 2 : {
59 : // load the matrix as A
60 3 : const char *aname = files [k].name ;
61 3 : uint64_t kval = files [k].kval ;
62 3 : if (strlen (aname) == 0) break;
63 2 : TEST_CASE (aname) ;
64 2 : snprintf (filename, LEN, LG_DATA_DIR "%s", aname) ;
65 2 : FILE *f = fopen (filename, "r") ;
66 2 : TEST_CHECK (f != NULL) ;
67 2 : OK (LAGraph_MMRead (&A, f, msg)) ;
68 2 : TEST_MSG ("Loading of adjacency matrix failed") ;
69 2 : fclose (f) ;
70 :
71 : // construct an undirected graph G with adjacency matrix A
72 2 : OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_DIRECTED, msg)) ;
73 2 : TEST_CHECK (A == NULL) ;
74 :
75 : // check if the pattern is symmetric - if it isn't make it.
76 2 : OK (LAGraph_Cached_IsSymmetricStructure (G, msg)) ;
77 :
78 2 : if (G->is_symmetric_structure == LAGraph_FALSE)
79 : {
80 1 : printf("This matrix is not symmetric. \n");
81 : // make the adjacency matrix symmetric
82 1 : OK (LAGraph_Cached_AT (G, msg)) ;
83 1 : OK (GrB_eWiseAdd (G->A, NULL, NULL, GrB_LOR, G->A, G->AT, NULL)) ;
84 1 : G->is_symmetric_structure = true ;
85 : // consider the graph as directed
86 1 : G->kind = LAGraph_ADJACENCY_DIRECTED ;
87 : }
88 : else
89 : {
90 1 : G->kind = LAGraph_ADJACENCY_UNDIRECTED ;
91 : }
92 :
93 : // check for self-edges, and remove them.
94 2 : OK (LAGraph_Cached_NSelfEdges (G, msg)) ;
95 2 : if (G->nself_edges != 0)
96 : {
97 : // remove self-edges
98 1 : printf ("graph has %g self edges\n", (double) G->nself_edges) ;
99 1 : OK (LAGraph_DeleteSelfEdges (G, msg)) ;
100 1 : printf ("now has %g self edges\n", (double) G->nself_edges) ;
101 1 : TEST_CHECK (G->nself_edges == 0) ;
102 : }
103 :
104 : bool ok;
105 : //get the kcore at the designated k-value
106 2 : LAGraph_KCore(&c, G, kval, msg) ;
107 :
108 : //decompose the k-core from vector c into D1
109 2 : LAGraph_KCore_Decompose(&D1, G, c, kval, msg);
110 :
111 : //decompose the k-core from vector c into D2
112 2 : LG_check_kcore_decompose(&D2, G, c, kval, msg);
113 :
114 : //check equality
115 2 : OK (LAGraph_Matrix_IsEqual (&ok, D1, D2, msg)) ;
116 2 : TEST_CHECK(ok);
117 :
118 2 : GrB_free (&c) ;
119 2 : GrB_free (&D1) ;
120 2 : GrB_free (&D2) ;
121 2 : OK (LAGraph_Delete (&G, msg)) ;
122 : }
123 :
124 1 : LAGraph_Finalize (msg) ;
125 : #endif
126 1 : }
127 :
128 : //------------------------------------------------------------------------------
129 : // test_errors
130 : //------------------------------------------------------------------------------
131 :
132 1 : void test_errors (void)
133 : {
134 : #if LAGRAPH_SUITESPARSE
135 1 : LAGraph_Init (msg) ;
136 :
137 1 : snprintf (filename, LEN, LG_DATA_DIR "%s", "karate.mtx") ;
138 1 : FILE *f = fopen (filename, "r") ;
139 1 : TEST_CHECK (f != NULL) ;
140 1 : OK (LAGraph_MMRead (&A, f, msg)) ;
141 1 : TEST_MSG ("Loading of adjacency matrix failed") ;
142 1 : fclose (f) ;
143 :
144 : // construct an undirected graph G with adjacency matrix A
145 1 : OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_UNDIRECTED, msg)) ;
146 1 : TEST_CHECK (A == NULL) ;
147 :
148 1 : OK (LAGraph_Cached_NSelfEdges (G, msg)) ;
149 :
150 1 : uint64_t kval = 2 ;
151 1 : GrB_Vector c = NULL ;
152 :
153 : // c is NULL
154 1 : int result = LAGraph_KCore_Decompose (&D1, G, NULL, kval, msg) ;
155 1 : printf ("\nresult: %d %s\n", result, msg) ;
156 1 : TEST_CHECK (result == GrB_NULL_POINTER) ;
157 :
158 : // G is invalid
159 1 : result = LAGraph_KCore_Decompose (&D1, NULL, c, kval, msg) ;
160 1 : printf ("\nresult: %d %s\n", result, msg) ;
161 1 : TEST_CHECK (result == GrB_NULL_POINTER) ;
162 1 : TEST_CHECK (c == NULL) ;
163 :
164 : // G may have self edges
165 1 : G->nself_edges = LAGRAPH_UNKNOWN ;
166 1 : result = LAGraph_KCore_Decompose(&D1, G, c, kval, msg);
167 1 : printf ("\nresult: %d %s\n", result, msg) ;
168 1 : TEST_CHECK (result == -1004) ;
169 1 : TEST_CHECK (c == NULL) ;
170 :
171 : // G is directed
172 1 : G->nself_edges = 0 ;
173 1 : G->kind = LAGraph_ADJACENCY_DIRECTED ;
174 1 : G->is_symmetric_structure = LAGraph_FALSE ;
175 1 : result = LAGraph_KCore_Decompose(&D1, G, c, kval, msg);
176 1 : printf ("\nresult: %d %s\n", result, msg) ;
177 1 : TEST_CHECK (result == -1005) ;
178 1 : TEST_CHECK (c == NULL) ;
179 :
180 1 : result = LG_check_kcore_decompose(&D1, G, c, kval, msg);
181 1 : printf ("\nresult: %d %s\n", result, msg) ;
182 1 : TEST_CHECK (result == -1005) ;
183 1 : TEST_CHECK (c == NULL) ;
184 :
185 1 : OK (LAGraph_Delete (&G, msg)) ;
186 1 : LAGraph_Finalize (msg) ;
187 : #endif
188 1 : }
189 :
190 : TEST_LIST = {
191 : {"KCoreDecompose", test_KCoreDecompose},
192 : {"KCoreDecompose_errors", test_errors},
193 : {NULL, NULL}
194 : };
|
