15 * purpose. |
15 * purpose. |
16 * |
16 * |
17 */ |
17 */ |
18 |
18 |
19 #include <iostream> |
19 #include <iostream> |
|
20 #include <fstream> |
|
21 |
|
22 #include <lemon/list_graph.h> |
|
23 #include <lemon/smart_graph.h> |
|
24 #include <lemon/graph_reader.h> |
|
25 #include <lemon/dimacs.h> |
|
26 #include <lemon/time_measure.h> |
|
27 |
|
28 #include <lemon/cycle_canceling.h> |
|
29 #include <lemon/capacity_scaling.h> |
|
30 #include <lemon/cost_scaling.h> |
|
31 #include <lemon/network_simplex.h> |
|
32 |
|
33 #include <lemon/min_cost_flow.h> |
|
34 #include <lemon/min_cost_max_flow.h> |
|
35 |
20 #include "test_tools.h" |
36 #include "test_tools.h" |
21 #include <lemon/list_graph.h> |
|
22 #include <lemon/ssp_min_cost_flow.h> |
|
23 //#include <path.h> |
|
24 //#include <maps.h> |
|
25 |
37 |
26 using namespace lemon; |
38 using namespace lemon; |
27 |
39 |
28 |
40 // Checks the feasibility of a flow |
29 bool passed = true; |
41 template < typename Graph, typename LowerMap, typename CapacityMap, |
30 /* |
42 typename SupplyMap, typename FlowMap > |
31 void check(bool rc, char *msg="") { |
43 bool checkFlow( const Graph& gr, |
32 passed = passed && rc; |
44 const LowerMap& lower, const CapacityMap& upper, |
33 if(!rc) { |
45 const SupplyMap& supply, const FlowMap& flow ) |
34 std::cerr << "Test failed! ("<< msg << ")" << std::endl; \ |
46 { |
35 |
47 GRAPH_TYPEDEFS(typename Graph); |
36 |
48 for (EdgeIt e(gr); e != INVALID; ++e) |
37 } |
49 if (flow[e] < lower[e] || flow[e] > upper[e]) return false; |
|
50 |
|
51 for (NodeIt n(gr); n != INVALID; ++n) { |
|
52 typename SupplyMap::Value sum = 0; |
|
53 for (OutEdgeIt e(gr, n); e != INVALID; ++e) |
|
54 sum += flow[e]; |
|
55 for (InEdgeIt e(gr, n); e != INVALID; ++e) |
|
56 sum -= flow[e]; |
|
57 if (sum != supply[n]) return false; |
|
58 } |
|
59 |
|
60 return true; |
38 } |
61 } |
39 */ |
62 |
40 |
63 // Checks the optimalitiy of a flow |
|
64 template < typename Graph, typename LowerMap, typename CapacityMap, |
|
65 typename CostMap, typename FlowMap, typename PotentialMap > |
|
66 bool checkOptimality( const Graph& gr, const LowerMap& lower, |
|
67 const CapacityMap& upper, const CostMap& cost, |
|
68 const FlowMap& flow, const PotentialMap& pi ) |
|
69 { |
|
70 GRAPH_TYPEDEFS(typename Graph); |
|
71 // Checking the Complementary Slackness optimality condition |
|
72 bool opt = true; |
|
73 for (EdgeIt e(gr); e != INVALID; ++e) { |
|
74 typename CostMap::Value red_cost = |
|
75 cost[e] + pi[gr.source(e)] - pi[gr.target(e)]; |
|
76 opt = red_cost == 0 || |
|
77 (red_cost > 0 && flow[e] == lower[e]) || |
|
78 (red_cost < 0 && flow[e] == upper[e]); |
|
79 if (!opt) break; |
|
80 } |
|
81 return opt; |
|
82 } |
|
83 |
|
84 // Runs a minimum cost flow algorithm and checks the results |
|
85 template < typename MinCostFlowImpl, typename Graph, |
|
86 typename LowerMap, typename CapacityMap, |
|
87 typename CostMap, typename SupplyMap > |
|
88 void checkMcf( std::string test_id, |
|
89 const MinCostFlowImpl& mcf, const Graph& gr, |
|
90 const LowerMap& lower, const CapacityMap& upper, |
|
91 const CostMap& cost, const SupplyMap& supply, |
|
92 bool mcf_result, bool result, |
|
93 typename CostMap::Value total ) |
|
94 { |
|
95 check(mcf_result == result, "Wrong result " + test_id); |
|
96 if (result) { |
|
97 check(checkFlow(gr, lower, upper, supply, mcf.flowMap()), |
|
98 "The flow is not feasible " + test_id); |
|
99 check(mcf.totalCost() == total, "The flow is not optimal " + test_id); |
|
100 check(checkOptimality(gr, lower, upper, cost, mcf.flowMap(), mcf.potentialMap()), |
|
101 "Wrong potentials " + test_id); |
|
102 } |
|
103 } |
41 |
104 |
42 int main() |
105 int main() |
43 { |
106 { |
44 typedef ListGraph Graph; |
107 // Various tests on a small graph |
45 typedef Graph::Node Node; |
108 { |
46 typedef Graph::Edge Edge; |
109 typedef ListGraph Graph; |
47 |
110 GRAPH_TYPEDEFS(ListGraph); |
48 Graph graph; |
111 |
49 |
112 // Reading the test graph |
50 //Ahuja könyv példája |
113 Graph gr; |
51 |
114 Graph::EdgeMap<int> c(gr), l1(gr), l2(gr), u(gr); |
52 Node s=graph.addNode(); |
115 Graph::NodeMap<int> s1(gr), s2(gr), s3(gr); |
53 Node v1=graph.addNode(); |
116 Node v, w; |
54 Node v2=graph.addNode(); |
117 |
55 Node v3=graph.addNode(); |
118 std::string fname; |
56 Node v4=graph.addNode(); |
119 if(getenv("srcdir")) |
57 Node v5=graph.addNode(); |
120 fname = std::string(getenv("srcdir")); |
58 Node t=graph.addNode(); |
121 else fname = "."; |
59 |
122 fname += "/test/min_cost_flow_test.lgf"; |
60 Edge s_v1=graph.addEdge(s, v1); |
123 |
61 Edge v1_v2=graph.addEdge(v1, v2); |
124 std::ifstream input(fname.c_str()); |
62 Edge s_v3=graph.addEdge(s, v3); |
125 check(input, "Input file '" << fname << "' not found"); |
63 Edge v2_v4=graph.addEdge(v2, v4); |
126 GraphReader<Graph>(input, gr). |
64 Edge v2_v5=graph.addEdge(v2, v5); |
127 readEdgeMap("cost", c). |
65 Edge v3_v5=graph.addEdge(v3, v5); |
128 readEdgeMap("capacity", u). |
66 Edge v4_t=graph.addEdge(v4, t); |
129 readEdgeMap("lower1", l1). |
67 Edge v5_t=graph.addEdge(v5, t); |
130 readEdgeMap("lower2", l2). |
68 |
131 readNodeMap("supply1", s1). |
69 |
132 readNodeMap("supply2", s2). |
70 Graph::EdgeMap<int> length(graph); |
133 readNodeMap("supply3", s3). |
71 |
134 readNode("source", v). |
72 length.set(s_v1, 6); |
135 readNode("target", w). |
73 length.set(v1_v2, 4); |
136 run(); |
74 length.set(s_v3, 10); |
137 input.close(); |
75 length.set(v2_v4, 5); |
138 |
76 length.set(v2_v5, 1); |
139 // Testing CapacityScaling (scaling enabled) |
77 length.set(v3_v5, 4); |
140 { |
78 length.set(v4_t, 8); |
141 CapacityScaling<Graph> mcf1(gr,u,c,s1); checkMcf("#A1",mcf1,gr,l1,u,c,s1,mcf1.run(),true, 0); |
79 length.set(v5_t, 8); |
142 CapacityScaling<Graph> mcf2(gr,u,c,s2); checkMcf("#A2",mcf2,gr,l1,u,c,s2,mcf2.run(),true, 5240); |
80 |
143 CapacityScaling<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#A3",mcf3,gr,l1,u,c,s3,mcf3.run(),true, 7620); |
81 Graph::EdgeMap<int> capacity(graph); |
144 CapacityScaling<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#A4",mcf4,gr,l2,u,c,s1,mcf4.run(),false, 0); |
82 |
145 CapacityScaling<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#A5",mcf5,gr,l2,u,c,s2,mcf5.run(),true, 5970); |
83 capacity.set(s_v1, 2); |
146 CapacityScaling<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#A6",mcf6,gr,l2,u,c,s3,mcf6.run(),true, 8010); |
84 capacity.set(v1_v2, 2); |
147 } |
85 capacity.set(s_v3, 1); |
148 // Testing CapacityScaling (scaling disabled) |
86 capacity.set(v2_v4, 1); |
149 { |
87 capacity.set(v2_v5, 1); |
150 CapacityScaling<Graph> mcf1(gr,u,c,s1); checkMcf("#B1",mcf1,gr,l1,u,c,s1,mcf1.run(false),true, 0); |
88 capacity.set(v3_v5, 1); |
151 CapacityScaling<Graph> mcf2(gr,u,c,s2); checkMcf("#B2",mcf2,gr,l1,u,c,s2,mcf2.run(false),true, 5240); |
89 capacity.set(v4_t, 1); |
152 CapacityScaling<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#B3",mcf3,gr,l1,u,c,s3,mcf3.run(false),true, 7620); |
90 capacity.set(v5_t, 2); |
153 CapacityScaling<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#B4",mcf4,gr,l2,u,c,s1,mcf4.run(false),false, 0); |
91 |
154 CapacityScaling<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#B5",mcf5,gr,l2,u,c,s2,mcf5.run(false),true, 5970); |
92 // ConstMap<Edge, int> const1map(1); |
155 CapacityScaling<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#B6",mcf6,gr,l2,u,c,s3,mcf6.run(false),true, 8010); |
93 std::cout << "Mincostflows algorithm test..." << std::endl; |
156 } |
94 |
157 |
95 SspMinCostFlow< Graph, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
158 // Testing CostScaling |
96 surb_test(graph, length, capacity, s, t); |
159 { |
97 |
160 CostScaling<Graph> mcf1(gr,u,c,s1); checkMcf("#C1",mcf1,gr,l1,u,c,s1,mcf1.run(),true, 0); |
98 int k=1; |
161 CostScaling<Graph> mcf2(gr,u,c,s2); checkMcf("#C2",mcf2,gr,l1,u,c,s2,mcf2.run(),true, 5240); |
99 |
162 CostScaling<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#C3",mcf3,gr,l1,u,c,s3,mcf3.run(),true, 7620); |
100 surb_test.augment(); |
163 CostScaling<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#C4",mcf4,gr,l2,u,c,s1,mcf4.run(),false, 0); |
101 check( surb_test.flowValue() == 1 && surb_test.totalLength() == 19,"One path, total length should be 19"); |
164 CostScaling<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#C5",mcf5,gr,l2,u,c,s2,mcf5.run(),true, 5970); |
102 |
165 CostScaling<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#C6",mcf6,gr,l2,u,c,s3,mcf6.run(),true, 8010); |
103 check( surb_test.run(k) == 1 && surb_test.totalLength() == 19,"One path, total length should be 19"); |
166 } |
104 |
167 |
105 check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?"); |
168 // Testing NetworkSimplex (with the default pivot rule) |
106 |
169 { |
107 k=2; |
170 NetworkSimplex<Graph> mcf1(gr,u,c,s1); checkMcf("#D1",mcf1,gr,l1,u,c,s1,mcf1.run(),true, 0); |
108 |
171 NetworkSimplex<Graph> mcf2(gr,u,c,s2); checkMcf("#D2",mcf2,gr,l1,u,c,s2,mcf2.run(),true, 5240); |
109 check( surb_test.run(k) == 2 && surb_test.totalLength() == 41,"Two paths, total length should be 41"); |
172 NetworkSimplex<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#D3",mcf3,gr,l1,u,c,s3,mcf3.run(),true, 7620); |
110 |
173 NetworkSimplex<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#D4",mcf4,gr,l2,u,c,s1,mcf4.run(),false, 0); |
111 check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?"); |
174 NetworkSimplex<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#D5",mcf5,gr,l2,u,c,s2,mcf5.run(),true, 5970); |
112 |
175 NetworkSimplex<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#D6",mcf6,gr,l2,u,c,s3,mcf6.run(),true, 8010); |
113 surb_test.augment(); |
176 } |
114 surb_test.augment(); |
177 // Testing NetworkSimplex (with FIRST_ELIGIBLE_PIVOT) |
115 surb_test.augment(); |
178 { |
116 k=4; |
179 NetworkSimplex<Graph>::PivotRuleEnum pr = NetworkSimplex<Graph>::FIRST_ELIGIBLE_PIVOT; |
117 |
180 NetworkSimplex<Graph> mcf1(gr,u,c,s1); checkMcf("#E1",mcf1,gr,l1,u,c,s1,mcf1.run(pr),true, 0); |
118 check( surb_test.run(k) == 3 && surb_test.totalLength() == 64,"Three paths, total length should be 64"); |
181 NetworkSimplex<Graph> mcf2(gr,u,c,s2); checkMcf("#E2",mcf2,gr,l1,u,c,s2,mcf2.run(pr),true, 5240); |
119 |
182 NetworkSimplex<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#E3",mcf3,gr,l1,u,c,s3,mcf3.run(pr),true, 7620); |
120 check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?"); |
183 NetworkSimplex<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#E4",mcf4,gr,l2,u,c,s1,mcf4.run(pr),false, 0); |
121 |
184 NetworkSimplex<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#E5",mcf5,gr,l2,u,c,s2,mcf5.run(pr),true, 5970); |
122 |
185 NetworkSimplex<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#E6",mcf6,gr,l2,u,c,s3,mcf6.run(pr),true, 8010); |
123 std::cout << (passed ? "All tests passed." : "Some of the tests failed!!!") |
186 } |
124 << std::endl; |
187 // Testing NetworkSimplex (with BEST_ELIGIBLE_PIVOT) |
125 |
188 { |
126 return passed ? 0 : 1; |
189 NetworkSimplex<Graph>::PivotRuleEnum pr = NetworkSimplex<Graph>::BEST_ELIGIBLE_PIVOT; |
127 |
190 NetworkSimplex<Graph> mcf1(gr,u,c,s1); checkMcf("#F1",mcf1,gr,l1,u,c,s1,mcf1.run(pr),true, 0); |
|
191 NetworkSimplex<Graph> mcf2(gr,u,c,s2); checkMcf("#F2",mcf2,gr,l1,u,c,s2,mcf2.run(pr),true, 5240); |
|
192 NetworkSimplex<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#F3",mcf3,gr,l1,u,c,s3,mcf3.run(pr),true, 7620); |
|
193 NetworkSimplex<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#F4",mcf4,gr,l2,u,c,s1,mcf4.run(pr),false, 0); |
|
194 NetworkSimplex<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#F5",mcf5,gr,l2,u,c,s2,mcf5.run(pr),true, 5970); |
|
195 NetworkSimplex<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#F6",mcf6,gr,l2,u,c,s3,mcf6.run(pr),true, 8010); |
|
196 } |
|
197 // Testing NetworkSimplex (with BLOCK_SEARCH_PIVOT) |
|
198 { |
|
199 NetworkSimplex<Graph>::PivotRuleEnum pr = NetworkSimplex<Graph>::BLOCK_SEARCH_PIVOT; |
|
200 NetworkSimplex<Graph> mcf1(gr,u,c,s1); checkMcf("#G1",mcf1,gr,l1,u,c,s1,mcf1.run(pr),true, 0); |
|
201 NetworkSimplex<Graph> mcf2(gr,u,c,s2); checkMcf("#G2",mcf2,gr,l1,u,c,s2,mcf2.run(pr),true, 5240); |
|
202 NetworkSimplex<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#G3",mcf3,gr,l1,u,c,s3,mcf3.run(pr),true, 7620); |
|
203 NetworkSimplex<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#G4",mcf4,gr,l2,u,c,s1,mcf4.run(pr),false, 0); |
|
204 NetworkSimplex<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#G5",mcf5,gr,l2,u,c,s2,mcf5.run(pr),true, 5970); |
|
205 NetworkSimplex<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#G6",mcf6,gr,l2,u,c,s3,mcf6.run(pr),true, 8010); |
|
206 } |
|
207 // Testing NetworkSimplex (with LIMITED_SEARCH_PIVOT) |
|
208 { |
|
209 NetworkSimplex<Graph>::PivotRuleEnum pr = NetworkSimplex<Graph>::LIMITED_SEARCH_PIVOT; |
|
210 NetworkSimplex<Graph> mcf1(gr,u,c,s1); checkMcf("#H1",mcf1,gr,l1,u,c,s1,mcf1.run(pr),true, 0); |
|
211 NetworkSimplex<Graph> mcf2(gr,u,c,s2); checkMcf("#H2",mcf2,gr,l1,u,c,s2,mcf2.run(pr),true, 5240); |
|
212 NetworkSimplex<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#H3",mcf3,gr,l1,u,c,s3,mcf3.run(pr),true, 7620); |
|
213 NetworkSimplex<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#H4",mcf4,gr,l2,u,c,s1,mcf4.run(pr),false, 0); |
|
214 NetworkSimplex<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#H5",mcf5,gr,l2,u,c,s2,mcf5.run(pr),true, 5970); |
|
215 NetworkSimplex<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#H6",mcf6,gr,l2,u,c,s3,mcf6.run(pr),true, 8010); |
|
216 } |
|
217 // Testing NetworkSimplex (with CANDIDATE_LIST_PIVOT) |
|
218 { |
|
219 NetworkSimplex<Graph>::PivotRuleEnum pr = NetworkSimplex<Graph>::CANDIDATE_LIST_PIVOT; |
|
220 NetworkSimplex<Graph> mcf1(gr,u,c,s1); checkMcf("#I1",mcf1,gr,l1,u,c,s1,mcf1.run(pr),true, 0); |
|
221 NetworkSimplex<Graph> mcf2(gr,u,c,s2); checkMcf("#I2",mcf2,gr,l1,u,c,s2,mcf2.run(pr),true, 5240); |
|
222 NetworkSimplex<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#I3",mcf3,gr,l1,u,c,s3,mcf3.run(pr),true, 7620); |
|
223 NetworkSimplex<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#I4",mcf4,gr,l2,u,c,s1,mcf4.run(pr),false, 0); |
|
224 NetworkSimplex<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#I5",mcf5,gr,l2,u,c,s2,mcf5.run(pr),true, 5970); |
|
225 NetworkSimplex<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#I6",mcf6,gr,l2,u,c,s3,mcf6.run(pr),true, 8010); |
|
226 } |
|
227 |
|
228 // Testing CycleCanceling (with BellmanFord) |
|
229 { |
|
230 CycleCanceling<Graph> mcf1(gr,u,c,s1); checkMcf("#J1",mcf1,gr,l1,u,c,s1,mcf1.run(),true, 0); |
|
231 CycleCanceling<Graph> mcf2(gr,u,c,s2); checkMcf("#J2",mcf2,gr,l1,u,c,s2,mcf2.run(),true, 5240); |
|
232 CycleCanceling<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#J3",mcf3,gr,l1,u,c,s3,mcf3.run(),true, 7620); |
|
233 CycleCanceling<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#J4",mcf4,gr,l2,u,c,s1,mcf4.run(),false, 0); |
|
234 CycleCanceling<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#J5",mcf5,gr,l2,u,c,s2,mcf5.run(),true, 5970); |
|
235 CycleCanceling<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#J6",mcf6,gr,l2,u,c,s3,mcf6.run(),true, 8010); |
|
236 } |
|
237 // Testing CycleCanceling (with MinMeanCycle) |
|
238 { |
|
239 CycleCanceling<Graph> mcf1(gr,u,c,s1); checkMcf("#K1",mcf1,gr,l1,u,c,s1,mcf1.run(true),true, 0); |
|
240 CycleCanceling<Graph> mcf2(gr,u,c,s2); checkMcf("#K2",mcf2,gr,l1,u,c,s2,mcf2.run(true),true, 5240); |
|
241 CycleCanceling<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#K3",mcf3,gr,l1,u,c,s3,mcf3.run(true),true, 7620); |
|
242 CycleCanceling<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#K4",mcf4,gr,l2,u,c,s1,mcf4.run(true),false, 0); |
|
243 CycleCanceling<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#K5",mcf5,gr,l2,u,c,s2,mcf5.run(true),true, 5970); |
|
244 CycleCanceling<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#K6",mcf6,gr,l2,u,c,s3,mcf6.run(true),true, 8010); |
|
245 } |
|
246 |
|
247 // Testing MinCostFlow |
|
248 { |
|
249 MinCostFlow<Graph> mcf1(gr,u,c,s1); checkMcf("#L1",mcf1,gr,l1,u,c,s1,mcf1.run(),true, 0); |
|
250 MinCostFlow<Graph> mcf2(gr,u,c,s2); checkMcf("#L2",mcf2,gr,l1,u,c,s2,mcf2.run(),true, 5240); |
|
251 MinCostFlow<Graph> mcf3(gr,u,c,v,w,27); checkMcf("#L3",mcf3,gr,l1,u,c,s3,mcf3.run(),true, 7620); |
|
252 MinCostFlow<Graph> mcf4(gr,l2,u,c,s1); checkMcf("#L4",mcf4,gr,l2,u,c,s1,mcf4.run(),false, 0); |
|
253 MinCostFlow<Graph> mcf5(gr,l2,u,c,s2); checkMcf("#L5",mcf5,gr,l2,u,c,s2,mcf5.run(),true, 5970); |
|
254 MinCostFlow<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#L6",mcf6,gr,l2,u,c,s3,mcf6.run(),true, 8010); |
|
255 } |
|
256 |
|
257 // Testing MinCostMaxFlow |
|
258 { |
|
259 MinCostMaxFlow<Graph> mcmf(gr,u,c,v,w); |
|
260 mcmf.run(); |
|
261 checkMcf("#M1",mcmf,gr,l1,u,c,s3,true,true,7620); |
|
262 } |
|
263 } |
|
264 |
|
265 // Benchmark test on a DIMACS network |
|
266 { |
|
267 typedef SmartGraph Graph; |
|
268 GRAPH_TYPEDEFS(SmartGraph); |
|
269 |
|
270 // Reading the test graph |
|
271 Graph graph; |
|
272 Graph::EdgeMap<int> lower(graph), capacity(graph), cost(graph); |
|
273 Graph::NodeMap<int> supply(graph); |
|
274 |
|
275 std::string fname; |
|
276 if(getenv("srcdir")) |
|
277 fname = std::string(getenv("srcdir")); |
|
278 else fname = "."; |
|
279 fname += "/test/min_cost_flow_test.net"; |
|
280 |
|
281 std::ifstream input(fname.c_str()); |
|
282 check(input, "Input file '" << fname << "' not found"); |
|
283 readDimacs(input, graph, lower, capacity, cost, supply); |
|
284 input.close(); |
|
285 |
|
286 // NetworkSimplex |
|
287 { |
|
288 Timer t; |
|
289 NetworkSimplex<Graph> mcf(graph, lower, capacity, cost, supply); |
|
290 bool res = mcf.run(); |
|
291 t.stop(); |
|
292 checkMcf("#T3", mcf, graph, lower, capacity, cost, supply, res, true, 196587626); |
|
293 std::cout << "NetworkSimplex"; |
|
294 std::cout << std::endl << t << std::endl; |
|
295 } |
|
296 // CapacityScaling |
|
297 { |
|
298 Timer t; |
|
299 CapacityScaling<Graph> mcf(graph, lower, capacity, cost, supply); |
|
300 bool res = mcf.run(); |
|
301 t.stop(); |
|
302 checkMcf("#T1", mcf, graph, lower, capacity, cost, supply, res, true, 196587626); |
|
303 std::cout << "CapacityScaling"; |
|
304 std::cout << std::endl << t << std::endl; |
|
305 } |
|
306 // CostScaling |
|
307 { |
|
308 Timer t; |
|
309 CostScaling<Graph> mcf(graph, lower, capacity, cost, supply); |
|
310 bool res = mcf.run(); |
|
311 t.stop(); |
|
312 checkMcf("#T2", mcf, graph, lower, capacity, cost, supply, res, true, 196587626); |
|
313 std::cout << "CostScaling"; |
|
314 std::cout << std::endl << t << std::endl; |
|
315 } |
|
316 // CycleCanceling |
|
317 { |
|
318 Timer t; |
|
319 CycleCanceling<Graph> mcf(graph, lower, capacity, cost, supply); |
|
320 bool res = mcf.run(); |
|
321 t.stop(); |
|
322 checkMcf("#T4", mcf, graph, lower, capacity, cost, supply, res, true, 196587626); |
|
323 std::cout << "CycleCanceling"; |
|
324 std::cout << std::endl << t << std::endl; |
|
325 } |
|
326 } |
|
327 |
|
328 return 0; |
128 } |
329 } |