Line data Source code
1 : //----------------------------------------------------------------------------
2 : // LAGraph/expirimental/test/test_AllKCore.c: test cases for full 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 ;
29 : GrB_Vector c1 = NULL, c2 = NULL;
30 : #define LEN 512
31 : char filename [LEN+1] ;
32 :
33 : typedef struct
34 : {
35 : uint64_t kmax ;
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_AllKCore (void)
53 : {
54 1 : LAGraph_Init (msg) ;
55 :
56 1 : for (int k = 0 ; ; k++)
57 2 : {
58 : // load the matrix as A
59 3 : const char *aname = files [k].name ;
60 3 : uint64_t kmax = files [k].kmax ;
61 3 : if (strlen (aname) == 0) break;
62 2 : printf ("\n %s: ==================================\n", aname) ;
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 2 : int64_t check_kmax = -1; //flag to check kmax in LG_check_kcore
105 : uint64_t km1;
106 : uint64_t km2;
107 : bool ok;
108 : //test the k-core
109 2 : OK(LAGraph_KCore_All(&c1, &km1, G, msg)) ;
110 : // printf ("kmax: %lu km1 %lu\n", kmax, km1) ;
111 2 : TEST_CHECK(kmax == km1) ;
112 :
113 2 : OK(LG_check_kcore(&c2, &km2, G, check_kmax, msg)) ;
114 : // printf ("kmax: %lu km1 %lu\n", kmax, km2) ;
115 :
116 2 : TEST_CHECK(kmax == km2) ;
117 2 : TEST_CHECK(km1 == km2) ;
118 2 : OK (LAGraph_Vector_IsEqual (&ok, c1, c2, msg)) ;
119 2 : TEST_CHECK (ok) ;
120 2 : GrB_free (&c1) ;
121 2 : GrB_free (&c2) ;
122 :
123 2 : OK (LAGraph_Delete (&G, msg)) ;
124 : }
125 :
126 1 : LAGraph_Finalize (msg) ;
127 1 : }
128 :
129 : //------------------------------------------------------------------------------
130 : // test_errors
131 : //------------------------------------------------------------------------------
132 :
133 1 : void test_errors (void)
134 : {
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 : uint64_t kmax ;
151 1 : GrB_Vector c = NULL ;
152 :
153 : // c is NULL
154 1 : int result = LAGraph_KCore_All (NULL, &kmax, G, 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_All (&c, &kmax, NULL, 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_All (&c, &kmax, G, 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 undirected
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_All (&c, &kmax, G, 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 : OK (LAGraph_Delete (&G, msg)) ;
181 1 : LAGraph_Finalize (msg) ;
182 1 : }
183 :
184 : TEST_LIST = {
185 : {"AllKCore", test_AllKCore},
186 : {"AllKCore_errors", test_errors},
187 : {NULL, NULL}
188 : };
|
