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 : //free work
91 7 : OK(LAGraph_Delete(&G, msg));
92 : }
93 1 : LAGraph_Finalize(msg);
94 : #endif
95 1 : }
96 :
97 1 : void test_MaxFlowMtx(void) {
98 1 : LAGraph_Init(msg);
99 : #if LG_SUITESPARSE_GRAPHBLAS_V10
100 : //OK(LG_SET_BURBLE(1));
101 1 : OK(LG_SET_BURBLE(0));
102 8 : for(uint8_t test = 0; test < NTESTS; test++){
103 7 : GrB_Matrix A=NULL;
104 7 : printf ("\nMatrix: %s\n", tests[test].filename);
105 7 : TEST_CASE(tests[test].filename);
106 7 : snprintf(filename, LEN, LG_DATA_DIR "%s", tests[test].filename);
107 7 : FILE* f = fopen(filename, "r");
108 7 : TEST_CHECK(f != NULL);
109 7 : OK(LAGraph_MMRead(&A, f, msg));
110 :
111 : //create flow mtx
112 7 : GrB_Matrix flow_mtx=NULL;
113 : GrB_Index n;
114 7 : OK(GrB_Matrix_nrows(&n, A));
115 :
116 7 : OK(fclose(f));
117 : // treat all matrices as directed graphs
118 7 : LAGraph_Kind kind = LAGraph_ADJACENCY_DIRECTED ;
119 : // LAGraph_Kind kind = tests [test].kind ;
120 7 : OK(LAGraph_New(&G, &A, kind, msg));
121 7 : if (kind == LAGraph_ADJACENCY_DIRECTED)
122 : {
123 7 : OK(LAGraph_Cached_AT(G, msg));
124 : }
125 7 : OK(LAGraph_Cached_EMin(G, msg));
126 :
127 : // test with JIT
128 7 : OK(GxB_Global_Option_set(GxB_JIT_C_CONTROL, GxB_JIT_ON));
129 7 : double flow = 0;
130 7 : OK(LAGr_MaxFlow(&flow, &flow_mtx, G, tests[test].S, tests[test].T, msg));
131 7 : TEST_CHECK (flow_mtx != NULL) ;
132 7 : GxB_print (flow_mtx, 2) ;
133 7 : int status = LG_check_flow(flow_mtx, msg);
134 7 : printf("status: %d ", status);
135 7 : printf("%s\n", msg);
136 7 : printf("flow is: %lf\n", flow);
137 7 : TEST_CHECK (status == GrB_SUCCESS) ;
138 7 : TEST_CHECK(flow == tests[test].F);
139 7 : GrB_free(&flow_mtx);
140 :
141 : // test without JIT
142 7 : OK(GxB_Global_Option_set(GxB_JIT_C_CONTROL, GxB_JIT_OFF));
143 7 : OK(LAGr_MaxFlow(&flow, &flow_mtx, G, tests[test].S, tests[test].T, msg));
144 7 : TEST_CHECK (flow_mtx != NULL) ;
145 7 : status = LG_check_flow(flow_mtx, msg);
146 7 : TEST_CHECK (status == GrB_SUCCESS) ;
147 7 : TEST_CHECK(flow == tests[test].F);
148 7 : OK(GxB_Global_Option_set(GxB_JIT_C_CONTROL, GxB_JIT_ON));
149 :
150 : //free work
151 7 : GrB_free(&flow_mtx);
152 7 : OK(LAGraph_Delete(&G, msg));
153 : }
154 : #endif
155 1 : LAGraph_Finalize(msg);
156 1 : }
157 :
158 :
159 : TEST_LIST = {{"MaxFlow", test_MaxFlow}, {"MaxFlowMtx", test_MaxFlowMtx}, {NULL, NULL}};
|
