Line data Source code
1 : //----------------------------------------------------------------------------
2 : // LAGraph/expirimental/test/test_KCore.c: test cases for single k-core
3 : // ----------------------------------------------------------------------------
4 :
5 : // LAGraph, (c) 2019-2022 by The LAGraph Contributors, All Rights Reserved.
6 : // SPDX-License-Identifier: BSD-2-Clause
7 : //
8 : // For additional details (including references to third party source code and
9 : // other files) see the LICENSE file or contact permission@sei.cmu.edu. See
10 : // Contributors.txt for a full list of contributors. Created, in part, with
11 : // funding and support from the U.S. Government (see Acknowledgments.txt file).
12 : // DM22-0790
13 :
14 : // Contributed by Pranav Konduri, Texas A&M University
15 :
16 : //-----------------------------------------------------------------------------
17 :
18 : #include <stdio.h>
19 : #include <acutest.h>
20 :
21 : #include <LAGraphX.h>
22 : #include <LAGraph_test.h>
23 : #include "LG_Xtest.h"
24 :
25 : char msg [LAGRAPH_MSG_LEN] ;
26 : LAGraph_Graph G = NULL ;
27 : GrB_Matrix A = NULL ;
28 : GrB_Vector c1 = NULL, c2 = NULL;
29 : #define LEN 512
30 : char filename [LEN+1] ;
31 :
32 : typedef struct
33 : {
34 : const char *name ;
35 : }
36 : matrix_info ;
37 :
38 : const matrix_info files [ ] =
39 : {
40 : {"karate.mtx" },
41 : {"west0067.mtx" },
42 : // {"amazon0601.mtx" },
43 : // {"cit-Patents.mtx"},
44 : // {"hollywood-2009.mtx"},
45 : // {"as-Skitter.mtx"},
46 : {""},
47 : } ;
48 :
49 :
50 1 : void test_KCore (void)
51 : {
52 1 : LAGraph_Init (msg) ;
53 :
54 1 : for (int k = 0 ; ; k++)
55 2 : {
56 : // load the matrix as A
57 3 : const char *aname = files [k].name ;
58 3 : if (strlen (aname) == 0) break;
59 2 : printf ("\n================================== %s: ==================================\n", aname) ;
60 2 : TEST_CASE (aname) ;
61 2 : snprintf (filename, LEN, LG_DATA_DIR "%s", aname) ;
62 2 : FILE *f = fopen (filename, "r") ;
63 2 : TEST_CHECK (f != NULL) ;
64 2 : OK (LAGraph_MMRead (&A, f, msg)) ;
65 2 : TEST_MSG ("Loading of adjacency matrix failed") ;
66 2 : fclose (f) ;
67 :
68 : // construct an undirected graph G with adjacency matrix A
69 2 : OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_DIRECTED, msg)) ;
70 2 : TEST_CHECK (A == NULL) ;
71 :
72 : // check if the pattern is symmetric - if it isn't make it.
73 2 : OK (LAGraph_Cached_IsSymmetricStructure (G, msg)) ;
74 :
75 2 : if (G->is_symmetric_structure == LAGraph_FALSE)
76 : {
77 1 : printf("This matrix is not symmetric. \n");
78 : // make the adjacency matrix symmetric
79 1 : OK (LAGraph_Cached_AT (G, msg)) ;
80 1 : OK (GrB_eWiseAdd (G->A, NULL, NULL, GrB_LOR, G->A, G->AT, NULL)) ;
81 1 : G->is_symmetric_structure = true ;
82 : // consider the graph as directed
83 1 : G->kind = LAGraph_ADJACENCY_DIRECTED ;
84 : }
85 : else
86 : {
87 1 : G->kind = LAGraph_ADJACENCY_UNDIRECTED ;
88 : }
89 :
90 : // check for self-edges, and remove them.
91 2 : OK (LAGraph_Cached_NSelfEdges (G, msg)) ;
92 2 : if (G->nself_edges != 0)
93 : {
94 : // remove self-edges
95 1 : printf ("graph has %g self edges\n", (double) G->nself_edges) ;
96 1 : OK (LAGraph_DeleteSelfEdges (G, msg)) ;
97 1 : printf ("now has %g self edges\n", (double) G->nself_edges) ;
98 1 : TEST_CHECK (G->nself_edges == 0) ;
99 : }
100 :
101 : uint64_t kmax;
102 : bool ok;
103 : //test the k-core
104 2 : OK(LAGraph_KCore(&c1, G, 2, msg)) ;
105 2 : OK(LG_check_kcore(&c2, &kmax, G, 2, msg)) ;
106 :
107 2 : OK (LAGraph_Vector_IsEqual (&ok, c1, c2, msg)) ;
108 2 : TEST_CHECK (ok) ;
109 :
110 2 : GrB_free (&c1) ;
111 2 : GrB_free (&c2) ;
112 2 : OK (LAGraph_Delete (&G, msg)) ;
113 : }
114 :
115 1 : LAGraph_Finalize (msg) ;
116 1 : }
117 :
118 : //------------------------------------------------------------------------------
119 : // test_errors
120 : //------------------------------------------------------------------------------
121 :
122 1 : void test_errors (void)
123 : {
124 1 : LAGraph_Init (msg) ;
125 :
126 1 : snprintf (filename, LEN, LG_DATA_DIR "%s", "karate.mtx") ;
127 1 : FILE *f = fopen (filename, "r") ;
128 1 : TEST_CHECK (f != NULL) ;
129 1 : OK (LAGraph_MMRead (&A, f, msg)) ;
130 1 : TEST_MSG ("Loading of adjacency matrix failed") ;
131 1 : fclose (f) ;
132 :
133 : // construct an undirected graph G with adjacency matrix A
134 1 : OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_UNDIRECTED, msg)) ;
135 1 : TEST_CHECK (A == NULL) ;
136 :
137 1 : OK (LAGraph_Cached_NSelfEdges (G, msg)) ;
138 :
139 1 : uint64_t k = 1; //some test k
140 1 : GrB_Vector c = NULL ;
141 :
142 : // c is NULL
143 1 : int result = LAGraph_KCore (NULL, G, k, msg) ;
144 1 : printf ("\nresult: %d %s\n", result, msg) ;
145 1 : TEST_CHECK (result == GrB_NULL_POINTER) ;
146 :
147 : // G is invalid
148 1 : result = LAGraph_KCore (&c, NULL, k, msg) ;
149 1 : printf ("\nresult: %d %s\n", result, msg) ;
150 1 : TEST_CHECK (result == GrB_NULL_POINTER) ;
151 1 : TEST_CHECK (c == NULL) ;
152 :
153 : // G may have self edges
154 1 : G->nself_edges = LAGRAPH_UNKNOWN ;
155 1 : result = LAGraph_KCore (&c, G, k, msg) ;
156 1 : printf ("\nresult: %d %s\n", result, msg) ;
157 1 : TEST_CHECK (result == -1004) ;
158 1 : TEST_CHECK (c == NULL) ;
159 :
160 : // G is undirected
161 1 : G->nself_edges = 0 ;
162 1 : G->kind = LAGraph_ADJACENCY_DIRECTED ;
163 1 : G->is_symmetric_structure = LAGraph_FALSE ;
164 1 : result = LAGraph_KCore (&c, G, k, msg) ;
165 1 : printf ("\nresult: %d %s\n", result, msg) ;
166 1 : TEST_CHECK (result == -1005) ;
167 1 : TEST_CHECK (c == NULL) ;
168 :
169 1 : OK (LAGraph_Delete (&G, msg)) ;
170 1 : LAGraph_Finalize (msg) ;
171 1 : }
172 :
173 : TEST_LIST = {
174 : {"KCore", test_KCore},
175 : {"KCore_errors", test_errors},
176 : {NULL, NULL}
177 : };
|
