Line data Source code
1 : //------------------------------------------------------------------------------
2 : // experimental/test/test_MaxFlow: tests for LAGr_MaxFlow
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 Darin Peries and Tim Davis, Texas A&M University
15 :
16 : //------------------------------------------------------------------------------
17 :
18 : #include <acutest.h>
19 : #include <LAGraphX.h>
20 : #include <LAGraph_test.h>
21 : #include <stdio.h>
22 : #include <LG_Xtest.h>
23 : #include "LG_internal.h"
24 :
25 :
26 : char msg[LAGRAPH_MSG_LEN];
27 : LAGraph_Graph G = NULL;
28 : GrB_Matrix A = NULL;
29 : #define LEN 512
30 : #define NTESTS 7
31 : char filename[LEN + 1];
32 :
33 : typedef struct{
34 : char* filename;
35 : GrB_Index S;
36 : GrB_Index T;
37 : double F;
38 : LAGraph_Kind kind ;
39 : }test_info;
40 :
41 : test_info tests[] = {
42 : {"wiki.mtx", 0, 5, 4, LAGraph_ADJACENCY_DIRECTED},
43 : {"matrix_random_flow.mtx", 0,9, 22, LAGraph_ADJACENCY_DIRECTED},
44 : {"rand.mtx", 0, 19, 37, LAGraph_ADJACENCY_DIRECTED},
45 : {"mcl.mtx", 0, 9, 0, LAGraph_ADJACENCY_DIRECTED},
46 : {"cycle_flow.mtx", 0, 89, 1, LAGraph_ADJACENCY_DIRECTED},
47 : {"random_weighted_general2.mtx", 0, 299, 11098623877, LAGraph_ADJACENCY_UNDIRECTED},
48 : {"random_weighted_general1.mtx", 0, 499, 6264009335, LAGraph_ADJACENCY_UNDIRECTED}
49 : };
50 :
51 : //399 11098623877 alt sink and src for test 6
52 :
53 1 : void test_MaxFlow(void) {
54 : #if LG_SUITESPARSE_GRAPHBLAS_V10
55 1 : LAGraph_Init(msg);
56 : //OK(LG_SET_BURBLE(1));
57 1 : OK(LG_SET_BURBLE(0));
58 8 : for(uint8_t test = 0; test < NTESTS; test++){
59 7 : GrB_Matrix A=NULL;
60 7 : printf ("\nMatrix: %s\n", tests[test].filename);
61 7 : TEST_CASE(tests[test].filename);
62 7 : snprintf(filename, LEN, LG_DATA_DIR "%s", tests[test].filename);
63 7 : FILE* f = fopen(filename, "r");
64 7 : TEST_CHECK(f != NULL);
65 7 : OK(LAGraph_MMRead(&A, f, msg));
66 7 : OK(fclose(f));
67 7 : LAGraph_Kind kind = tests [test].kind ;
68 7 : OK(LAGraph_New(&G, &A, kind, msg));
69 7 : if (kind == LAGraph_ADJACENCY_DIRECTED)
70 : {
71 5 : OK(LAGraph_Cached_AT(G, msg));
72 : }
73 :
74 7 : OK(LAGraph_Cached_EMin(G, msg));
75 :
76 : // test with JIT
77 7 : OK(GxB_Global_Option_set(GxB_JIT_C_CONTROL, GxB_JIT_ON));
78 7 : double flow = 0;
79 7 : OK(LAGr_MaxFlow(&flow, NULL, G, tests[test].S, tests[test].T, msg));
80 7 : printf("%s\n", msg);
81 7 : printf("flow is: %lf\n", flow);
82 7 : TEST_CHECK(flow == tests[test].F);
83 :
84 : // test without JIT
85 7 : OK(GxB_Global_Option_set(GxB_JIT_C_CONTROL, GxB_JIT_OFF));
86 7 : OK(LAGr_MaxFlow(&flow, NULL, G, tests[test].S, tests[test].T, msg));
87 7 : TEST_CHECK(flow == tests[test].F);
88 7 : OK(GxB_Global_Option_set(GxB_JIT_C_CONTROL, GxB_JIT_ON));
89 :
90 : // test all source/destination pairs for small problems
91 : GrB_Index n ;
92 7 : OK (GrB_Matrix_nrows (&n, G->A)) ;
93 7 : printf ("n: %d\n", (int) n) ;
94 7 : if (n < 100)
95 : {
96 141 : for (GrB_Index src = 0 ; src < n ; src++)
97 : {
98 8872 : for (GrB_Index dest = 0 ; dest < n ; dest++)
99 : {
100 8736 : printf("src: %d, dest: %d\n", (int) src, (int) dest);
101 8736 : if (src == dest) continue ;
102 8600 : OK(LAGr_MaxFlow(&flow, NULL, G, src, dest, msg));
103 : }
104 : }
105 : }
106 :
107 : //free work
108 7 : OK(LAGraph_Delete(&G, msg));
109 : }
110 1 : LAGraph_Finalize(msg);
111 : #endif
112 1 : }
113 :
114 1 : void test_MaxFlowMtx(void) {
115 1 : LAGraph_Init(msg);
116 : #if LG_SUITESPARSE_GRAPHBLAS_V10
117 : //OK(LG_SET_BURBLE(1));
118 1 : OK(LG_SET_BURBLE(0));
119 8 : for(uint8_t test = 0; test < NTESTS; test++){
120 7 : GrB_Matrix A=NULL;
121 7 : printf ("\nMatrix: %s\n", tests[test].filename);
122 7 : TEST_CASE(tests[test].filename);
123 7 : snprintf(filename, LEN, LG_DATA_DIR "%s", tests[test].filename);
124 7 : FILE* f = fopen(filename, "r");
125 7 : TEST_CHECK(f != NULL);
126 7 : OK(LAGraph_MMRead(&A, f, msg));
127 :
128 : //create flow mtx
129 7 : GrB_Matrix flow_mtx=NULL;
130 : GrB_Index n;
131 7 : OK(GrB_Matrix_nrows(&n, A));
132 :
133 7 : OK(fclose(f));
134 : // treat all matrices as directed graphs
135 7 : LAGraph_Kind kind = LAGraph_ADJACENCY_DIRECTED ;
136 : // LAGraph_Kind kind = tests [test].kind ;
137 7 : OK(LAGraph_New(&G, &A, kind, msg));
138 7 : if (kind == LAGraph_ADJACENCY_DIRECTED)
139 : {
140 7 : OK(LAGraph_Cached_AT(G, msg));
141 : }
142 7 : OK(LAGraph_Cached_EMin(G, msg));
143 :
144 : // test with JIT
145 7 : OK(GxB_Global_Option_set(GxB_JIT_C_CONTROL, GxB_JIT_ON));
146 7 : double flow = 0;
147 7 : OK(LAGr_MaxFlow(&flow, &flow_mtx, G, tests[test].S, tests[test].T, msg));
148 7 : TEST_CHECK (flow_mtx != NULL) ;
149 7 : GxB_print (flow_mtx, 2) ;
150 7 : int status = LG_check_flow(flow_mtx, msg);
151 7 : printf("status: %d ", status);
152 7 : printf("%s\n", msg);
153 7 : printf("flow is: %lf\n", flow);
154 7 : TEST_CHECK (status == GrB_SUCCESS) ;
155 7 : TEST_CHECK(flow == tests[test].F);
156 7 : GrB_free(&flow_mtx);
157 :
158 : // test without JIT
159 7 : OK(GxB_Global_Option_set(GxB_JIT_C_CONTROL, GxB_JIT_OFF));
160 7 : OK(LAGr_MaxFlow(&flow, &flow_mtx, G, tests[test].S, tests[test].T, msg));
161 7 : TEST_CHECK (flow_mtx != NULL) ;
162 7 : status = LG_check_flow(flow_mtx, msg);
163 7 : TEST_CHECK (status == GrB_SUCCESS) ;
164 7 : TEST_CHECK(flow == tests[test].F);
165 7 : OK(GxB_Global_Option_set(GxB_JIT_C_CONTROL, GxB_JIT_ON));
166 :
167 : //free work
168 7 : GrB_free(&flow_mtx);
169 7 : OK(LAGraph_Delete(&G, msg));
170 : }
171 : #endif
172 1 : LAGraph_Finalize(msg);
173 1 : }
174 :
175 :
176 : TEST_LIST = {{"MaxFlow", test_MaxFlow}, {"MaxFlowMtx", test_MaxFlowMtx}, {NULL, NULL}};
|
