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 :
67 : // construct an undirected graph G with adjacency matrix A
68 2 : OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_DIRECTED, msg)) ;
69 2 : TEST_CHECK (A == NULL) ;
70 :
71 : // check if the pattern is symmetric - if it isn't make it.
72 2 : OK (LAGraph_Cached_IsSymmetricStructure (G, msg)) ;
73 :
74 2 : if (G->is_symmetric_structure == LAGraph_FALSE)
75 : {
76 1 : printf("This matrix is not symmetric. \n");
77 : // make the adjacency matrix symmetric
78 1 : OK (LAGraph_Cached_AT (G, msg)) ;
79 1 : OK (GrB_eWiseAdd (G->A, NULL, NULL, GrB_LOR, G->A, G->AT, NULL)) ;
80 1 : G->is_symmetric_structure = true ;
81 : // consider the graph as directed
82 1 : G->kind = LAGraph_ADJACENCY_DIRECTED ;
83 : }
84 : else
85 : {
86 1 : G->kind = LAGraph_ADJACENCY_UNDIRECTED ;
87 : }
88 :
89 : // check for self-edges, and remove them.
90 2 : OK (LAGraph_Cached_NSelfEdges (G, msg)) ;
91 2 : if (G->nself_edges != 0)
92 : {
93 : // remove self-edges
94 1 : printf ("graph has %g self edges\n", (double) G->nself_edges) ;
95 1 : OK (LAGraph_DeleteSelfEdges (G, msg)) ;
96 1 : printf ("now has %g self edges\n", (double) G->nself_edges) ;
97 1 : TEST_CHECK (G->nself_edges == 0) ;
98 : }
99 :
100 : uint64_t kmax;
101 : bool ok;
102 : //test the k-core
103 2 : OK(LAGraph_KCore(&c1, G, 2, msg)) ;
104 2 : OK(LG_check_kcore(&c2, &kmax, G, 2, msg)) ;
105 :
106 2 : OK (LAGraph_Vector_IsEqual (&ok, c1, c2, msg)) ;
107 2 : TEST_CHECK (ok) ;
108 :
109 2 : OK (LAGraph_Delete (&G, msg)) ;
110 : }
111 :
112 1 : LAGraph_Finalize (msg) ;
113 1 : }
114 :
115 : //------------------------------------------------------------------------------
116 : // test_errors
117 : //------------------------------------------------------------------------------
118 :
119 1 : void test_errors (void)
120 : {
121 1 : LAGraph_Init (msg) ;
122 :
123 1 : snprintf (filename, LEN, LG_DATA_DIR "%s", "karate.mtx") ;
124 1 : FILE *f = fopen (filename, "r") ;
125 1 : TEST_CHECK (f != NULL) ;
126 1 : OK (LAGraph_MMRead (&A, f, msg)) ;
127 1 : TEST_MSG ("Loading of adjacency matrix failed") ;
128 :
129 : // construct an undirected graph G with adjacency matrix A
130 1 : OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_UNDIRECTED, msg)) ;
131 1 : TEST_CHECK (A == NULL) ;
132 :
133 1 : OK (LAGraph_Cached_NSelfEdges (G, msg)) ;
134 :
135 1 : uint64_t k = 1; //some test k
136 1 : GrB_Vector c = NULL ;
137 :
138 : // c is NULL
139 1 : int result = LAGraph_KCore (NULL, G, k, msg) ;
140 1 : printf ("\nresult: %d %s\n", result, msg) ;
141 1 : TEST_CHECK (result == GrB_NULL_POINTER) ;
142 :
143 : // G is invalid
144 1 : result = LAGraph_KCore (&c, NULL, k, msg) ;
145 1 : printf ("\nresult: %d %s\n", result, msg) ;
146 1 : TEST_CHECK (result == GrB_NULL_POINTER) ;
147 1 : TEST_CHECK (c == NULL) ;
148 :
149 : // G may have self edges
150 1 : G->nself_edges = LAGRAPH_UNKNOWN ;
151 1 : result = LAGraph_KCore (&c, G, k, msg) ;
152 1 : printf ("\nresult: %d %s\n", result, msg) ;
153 1 : TEST_CHECK (result == -1004) ;
154 1 : TEST_CHECK (c == NULL) ;
155 :
156 : // G is undirected
157 1 : G->nself_edges = 0 ;
158 1 : G->kind = LAGraph_ADJACENCY_DIRECTED ;
159 1 : G->is_symmetric_structure = LAGraph_FALSE ;
160 1 : result = LAGraph_KCore (&c, G, k, msg) ;
161 1 : printf ("\nresult: %d %s\n", result, msg) ;
162 1 : TEST_CHECK (result == -1005) ;
163 1 : TEST_CHECK (c == NULL) ;
164 :
165 1 : OK (LAGraph_Delete (&G, msg)) ;
166 1 : LAGraph_Finalize (msg) ;
167 1 : }
168 :
169 : TEST_LIST = {
170 : {"KCore", test_KCore},
171 : {"KCore_errors", test_errors},
172 : {NULL, NULL}
173 : };
|
