Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LAGraph/experimental/test/test_msf.c: test cases for Min Spanning Forest
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 Timothy A. Davis, Texas A&M University
15 :
16 : //------------------------------------------------------------------------------
17 :
18 : // todo: write a simple msf method, as LG_check_msf, and compare its results
19 : // with LAGraph_msf
20 :
21 : #include <stdio.h>
22 : #include <acutest.h>
23 :
24 : #include <LAGraphX.h>
25 : #include <LAGraph_test.h>
26 :
27 : char msg [LAGRAPH_MSG_LEN] ;
28 : LAGraph_Graph G = NULL ;
29 : GrB_Matrix A = NULL ;
30 : GrB_Matrix S = NULL ;
31 : GrB_Matrix C = NULL ;
32 : #define LEN 512
33 : char filename [LEN+1] ;
34 :
35 : typedef struct
36 : {
37 : bool symmetric ;
38 : const char *name ;
39 : }
40 : matrix_info ;
41 :
42 : const matrix_info files [ ] =
43 : {
44 : { 1, "A.mtx" },
45 : { 1, "jagmesh7.mtx" },
46 : { 0, "west0067.mtx" }, // unsymmetric
47 : { 1, "bcsstk13.mtx" },
48 : { 1, "karate.mtx" },
49 : { 1, "ldbc-cdlp-undirected-example.mtx" },
50 : { 1, "ldbc-undirected-example-bool.mtx" },
51 : { 1, "ldbc-undirected-example-unweighted.mtx" },
52 : { 1, "ldbc-undirected-example.mtx" },
53 : { 1, "ldbc-wcc-example.mtx" },
54 : { 0, "" },
55 : } ;
56 :
57 : //****************************************************************************
58 1 : void test_msf (void)
59 : {
60 1 : LAGraph_Init (msg) ;
61 : #if LAGRAPH_SUITESPARSE
62 :
63 1 : for (int k = 0 ; ; k++)
64 10 : {
65 :
66 : // load the matrix as A
67 11 : const char *aname = files [k].name ;
68 11 : bool symmetric = files [k].symmetric ;
69 11 : if (strlen (aname) == 0) break;
70 10 : printf ("\n================================== %s:\n", aname) ;
71 10 : TEST_CASE (aname) ;
72 10 : snprintf (filename, LEN, LG_DATA_DIR "%s", aname) ;
73 10 : FILE *f = fopen (filename, "r") ;
74 10 : TEST_CHECK (f != NULL) ;
75 10 : OK (LAGraph_MMRead (&A, f, msg)) ;
76 :
77 : // ensure A is uint64
78 : GrB_Index nrows, ncols ;
79 10 : OK (GrB_Matrix_nrows (&nrows, A)) ;
80 10 : OK (GrB_Matrix_ncols (&ncols, A)) ;
81 10 : OK (GrB_Matrix_new (&S, GrB_UINT64, nrows, ncols)) ;
82 10 : OK (GrB_assign (S, NULL, NULL, A, GrB_ALL, nrows, GrB_ALL, ncols,
83 : NULL)) ;
84 10 : GrB_Index n = nrows ;
85 10 : OK (GrB_free (&A)) ;
86 :
87 : // construct a directed graph G with adjacency matrix S
88 10 : OK (LAGraph_New (&G, &S, LAGraph_ADJACENCY_DIRECTED, msg)) ;
89 10 : TEST_CHECK (S == NULL) ;
90 :
91 10 : bool sanitize = (!symmetric) ;
92 :
93 : // compute the min spanning forest
94 10 : C = NULL ;
95 10 : int result = LAGraph_msf (&C, G->A, sanitize, msg) ;
96 10 : printf ("result: %d\n", result) ;
97 10 : LAGraph_PrintLevel pr = (n <= 100) ? LAGraph_COMPLETE : LAGraph_SHORT ;
98 :
99 : // check result C for A.mtx
100 10 : if (strcmp (aname, "A.mtx") == 0)
101 : {
102 1 : GrB_Matrix Cgood = NULL ;
103 1 : OK (GrB_Matrix_new (&Cgood, GrB_UINT64, n, n)) ;
104 1 : OK (GrB_Matrix_setElement (Cgood, 1, 1, 0)) ;
105 1 : OK (GrB_Matrix_setElement (Cgood, 1, 2, 0)) ;
106 1 : OK (GrB_Matrix_setElement (Cgood, 1, 3, 1)) ;
107 1 : OK (GrB_Matrix_setElement (Cgood, 1, 4, 1)) ;
108 1 : OK (GrB_Matrix_setElement (Cgood, 1, 5, 1)) ;
109 1 : OK (GrB_Matrix_setElement (Cgood, 1, 6, 0)) ;
110 1 : OK (GrB_wait (Cgood, GrB_MATERIALIZE)) ;
111 1 : printf ("\nmsf (known result):\n") ;
112 1 : OK (LAGraph_Matrix_Print (Cgood, pr, stdout, msg)) ;
113 1 : bool ok = false ;
114 1 : OK (LAGraph_Matrix_IsEqual (&ok, C, Cgood, msg)) ;
115 1 : TEST_CHECK (ok) ;
116 1 : OK (GrB_free (&Cgood)) ;
117 : }
118 :
119 10 : printf ("\nmsf:\n") ;
120 10 : OK (LAGraph_Matrix_Print (C, pr, stdout, msg)) ;
121 10 : OK (GrB_free (&C)) ;
122 10 : OK (LAGraph_Delete (&G, msg)) ;
123 : }
124 :
125 : #else
126 : printf ("test skipped\n") ;
127 : #endif
128 1 : LAGraph_Finalize (msg) ;
129 1 : }
130 :
131 : //------------------------------------------------------------------------------
132 : // test_errors
133 : //------------------------------------------------------------------------------
134 :
135 1 : void test_errors (void)
136 : {
137 1 : LAGraph_Init (msg) ;
138 : #if LAGRAPH_SUITESPARSE
139 :
140 : // C and A are NULL
141 1 : int result = LAGraph_msf (NULL, NULL, true, msg) ;
142 1 : TEST_CHECK (result == GrB_NULL_POINTER) ;
143 :
144 : // A must be square
145 1 : OK (GrB_Matrix_new (&A, GrB_UINT64, 3, 4)) ;
146 1 : result = LAGraph_msf (&C, A, true, msg) ;
147 1 : TEST_CHECK (result == GrB_DIMENSION_MISMATCH) ;
148 :
149 1 : OK (GrB_free (&A)) ;
150 : #else
151 : printf ("test skipped\n") ;
152 : #endif
153 1 : LAGraph_Finalize (msg) ;
154 1 : }
155 :
156 : //****************************************************************************
157 :
158 : TEST_LIST = {
159 : {"msf", test_msf},
160 : {"msf_errors", test_errors},
161 : {NULL, NULL}
162 : };
|
