|
1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
|
2 * |
|
3 * This file is a part of LEMON, a generic C++ optimization library. |
|
4 * |
|
5 * Copyright (C) 2003-2009 |
|
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
8 * |
|
9 * Permission to use, modify and distribute this software is granted |
|
10 * provided that this copyright notice appears in all copies. For |
|
11 * precise terms see the accompanying LICENSE file. |
|
12 * |
|
13 * This software is provided "AS IS" with no warranty of any kind, |
|
14 * express or implied, and with no claim as to its suitability for any |
|
15 * purpose. |
|
16 * |
|
17 */ |
|
18 |
|
19 #include <iostream> |
|
20 #include <fstream> |
|
21 |
|
22 #include <lemon/list_graph.h> |
|
23 #include <lemon/smart_graph.h> |
|
24 #include <lemon/lgf_reader.h> |
|
25 |
|
26 //#include <lemon/cycle_canceling.h> |
|
27 //#include <lemon/capacity_scaling.h> |
|
28 //#include <lemon/cost_scaling.h> |
|
29 #include <lemon/network_simplex.h> |
|
30 //#include <lemon/min_cost_flow.h> |
|
31 //#include <lemon/min_cost_max_flow.h> |
|
32 |
|
33 #include <lemon/concepts/digraph.h> |
|
34 #include <lemon/concept_check.h> |
|
35 |
|
36 #include "test_tools.h" |
|
37 |
|
38 using namespace lemon; |
|
39 |
|
40 char test_lgf[] = |
|
41 "@nodes\n" |
|
42 "label sup1 sup2 sup3\n" |
|
43 " 1 20 27 0\n" |
|
44 " 2 -4 0 0\n" |
|
45 " 3 0 0 0\n" |
|
46 " 4 0 0 0\n" |
|
47 " 5 9 0 0\n" |
|
48 " 6 -6 0 0\n" |
|
49 " 7 0 0 0\n" |
|
50 " 8 0 0 0\n" |
|
51 " 9 3 0 0\n" |
|
52 " 10 -2 0 0\n" |
|
53 " 11 0 0 0\n" |
|
54 " 12 -20 -27 0\n" |
|
55 "\n" |
|
56 "@arcs\n" |
|
57 " cost cap low1 low2\n" |
|
58 " 1 2 70 11 0 8\n" |
|
59 " 1 3 150 3 0 1\n" |
|
60 " 1 4 80 15 0 2\n" |
|
61 " 2 8 80 12 0 0\n" |
|
62 " 3 5 140 5 0 3\n" |
|
63 " 4 6 60 10 0 1\n" |
|
64 " 4 7 80 2 0 0\n" |
|
65 " 4 8 110 3 0 0\n" |
|
66 " 5 7 60 14 0 0\n" |
|
67 " 5 11 120 12 0 0\n" |
|
68 " 6 3 0 3 0 0\n" |
|
69 " 6 9 140 4 0 0\n" |
|
70 " 6 10 90 8 0 0\n" |
|
71 " 7 1 30 5 0 0\n" |
|
72 " 8 12 60 16 0 4\n" |
|
73 " 9 12 50 6 0 0\n" |
|
74 "10 12 70 13 0 5\n" |
|
75 "10 2 100 7 0 0\n" |
|
76 "10 7 60 10 0 0\n" |
|
77 "11 10 20 14 0 6\n" |
|
78 "12 11 30 10 0 0\n" |
|
79 "\n" |
|
80 "@attributes\n" |
|
81 "source 1\n" |
|
82 "target 12\n"; |
|
83 |
|
84 |
|
85 // Check the interface of an MCF algorithm |
|
86 template <typename GR, typename Value> |
|
87 class McfClassConcept |
|
88 { |
|
89 public: |
|
90 |
|
91 template <typename MCF> |
|
92 struct Constraints { |
|
93 void constraints() { |
|
94 checkConcept<concepts::Digraph, GR>(); |
|
95 |
|
96 MCF mcf_test1(g, lower, upper, cost, sup); |
|
97 MCF mcf_test2(g, upper, cost, sup); |
|
98 MCF mcf_test3(g, lower, upper, cost, n, n, k); |
|
99 MCF mcf_test4(g, upper, cost, n, n, k); |
|
100 |
|
101 // TODO: This part should be enabled and the next part |
|
102 // should be removed if map copying is supported |
|
103 /* |
|
104 flow = mcf_test1.flowMap(); |
|
105 mcf_test1.flowMap(flow); |
|
106 |
|
107 pot = mcf_test1.potentialMap(); |
|
108 mcf_test1.potentialMap(pot); |
|
109 */ |
|
110 /**/ |
|
111 const typename MCF::FlowMap &fm = |
|
112 mcf_test1.flowMap(); |
|
113 mcf_test1.flowMap(flow); |
|
114 const typename MCF::PotentialMap &pm = |
|
115 mcf_test1.potentialMap(); |
|
116 mcf_test1.potentialMap(pot); |
|
117 ignore_unused_variable_warning(fm); |
|
118 ignore_unused_variable_warning(pm); |
|
119 /**/ |
|
120 |
|
121 mcf_test1.run(); |
|
122 |
|
123 v = mcf_test1.totalCost(); |
|
124 v = mcf_test1.flow(a); |
|
125 v = mcf_test1.potential(n); |
|
126 } |
|
127 |
|
128 typedef typename GR::Node Node; |
|
129 typedef typename GR::Arc Arc; |
|
130 typedef concepts::ReadMap<Node, Value> NM; |
|
131 typedef concepts::ReadMap<Arc, Value> AM; |
|
132 |
|
133 const GR &g; |
|
134 const AM &lower; |
|
135 const AM &upper; |
|
136 const AM &cost; |
|
137 const NM ⊃ |
|
138 const Node &n; |
|
139 const Arc &a; |
|
140 const Value &k; |
|
141 Value v; |
|
142 |
|
143 typename MCF::FlowMap &flow; |
|
144 typename MCF::PotentialMap &pot; |
|
145 }; |
|
146 |
|
147 }; |
|
148 |
|
149 |
|
150 // Check the feasibility of the given flow (primal soluiton) |
|
151 template < typename GR, typename LM, typename UM, |
|
152 typename SM, typename FM > |
|
153 bool checkFlow( const GR& gr, const LM& lower, const UM& upper, |
|
154 const SM& supply, const FM& flow ) |
|
155 { |
|
156 TEMPLATE_DIGRAPH_TYPEDEFS(GR); |
|
157 |
|
158 for (ArcIt e(gr); e != INVALID; ++e) { |
|
159 if (flow[e] < lower[e] || flow[e] > upper[e]) return false; |
|
160 } |
|
161 |
|
162 for (NodeIt n(gr); n != INVALID; ++n) { |
|
163 typename SM::Value sum = 0; |
|
164 for (OutArcIt e(gr, n); e != INVALID; ++e) |
|
165 sum += flow[e]; |
|
166 for (InArcIt e(gr, n); e != INVALID; ++e) |
|
167 sum -= flow[e]; |
|
168 if (sum != supply[n]) return false; |
|
169 } |
|
170 |
|
171 return true; |
|
172 } |
|
173 |
|
174 // Check the feasibility of the given potentials (dual soluiton) |
|
175 // using the Complementary Slackness optimality condition |
|
176 template < typename GR, typename LM, typename UM, |
|
177 typename CM, typename FM, typename PM > |
|
178 bool checkPotential( const GR& gr, const LM& lower, const UM& upper, |
|
179 const CM& cost, const FM& flow, const PM& pi ) |
|
180 { |
|
181 TEMPLATE_DIGRAPH_TYPEDEFS(GR); |
|
182 |
|
183 bool opt = true; |
|
184 for (ArcIt e(gr); opt && e != INVALID; ++e) { |
|
185 typename CM::Value red_cost = |
|
186 cost[e] + pi[gr.source(e)] - pi[gr.target(e)]; |
|
187 opt = red_cost == 0 || |
|
188 (red_cost > 0 && flow[e] == lower[e]) || |
|
189 (red_cost < 0 && flow[e] == upper[e]); |
|
190 } |
|
191 return opt; |
|
192 } |
|
193 |
|
194 // Run a minimum cost flow algorithm and check the results |
|
195 template < typename MCF, typename GR, |
|
196 typename LM, typename UM, |
|
197 typename CM, typename SM > |
|
198 void checkMcf( const MCF& mcf, bool mcf_result, |
|
199 const GR& gr, const LM& lower, const UM& upper, |
|
200 const CM& cost, const SM& supply, |
|
201 bool result, typename CM::Value total, |
|
202 const std::string &test_id = "" ) |
|
203 { |
|
204 check(mcf_result == result, "Wrong result " + test_id); |
|
205 if (result) { |
|
206 check(checkFlow(gr, lower, upper, supply, mcf.flowMap()), |
|
207 "The flow is not feasible " + test_id); |
|
208 check(mcf.totalCost() == total, "The flow is not optimal " + test_id); |
|
209 check(checkPotential(gr, lower, upper, cost, mcf.flowMap(), |
|
210 mcf.potentialMap()), |
|
211 "Wrong potentials " + test_id); |
|
212 } |
|
213 } |
|
214 |
|
215 int main() |
|
216 { |
|
217 // Check the interfaces |
|
218 { |
|
219 typedef int Value; |
|
220 // This typedef should be enabled if the standard maps are |
|
221 // reference maps in the graph concepts |
|
222 //typedef concepts::Digraph GR; |
|
223 typedef ListDigraph GR; |
|
224 typedef concepts::ReadMap<GR::Node, Value> NM; |
|
225 typedef concepts::ReadMap<GR::Arc, Value> AM; |
|
226 |
|
227 //checkConcept< McfClassConcept<GR, Value>, |
|
228 // CycleCanceling<GR, AM, AM, AM, NM> >(); |
|
229 //checkConcept< McfClassConcept<GR, Value>, |
|
230 // CapacityScaling<GR, AM, AM, AM, NM> >(); |
|
231 //checkConcept< McfClassConcept<GR, Value>, |
|
232 // CostScaling<GR, AM, AM, AM, NM> >(); |
|
233 checkConcept< McfClassConcept<GR, Value>, |
|
234 NetworkSimplex<GR, AM, AM, AM, NM> >(); |
|
235 //checkConcept< MinCostFlow<GR, Value>, |
|
236 // NetworkSimplex<GR, AM, AM, AM, NM> >(); |
|
237 } |
|
238 |
|
239 // Run various MCF tests |
|
240 typedef ListDigraph Digraph; |
|
241 DIGRAPH_TYPEDEFS(ListDigraph); |
|
242 |
|
243 // Read the test digraph |
|
244 Digraph gr; |
|
245 Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), u(gr); |
|
246 Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr); |
|
247 Node v, w; |
|
248 |
|
249 std::istringstream input(test_lgf); |
|
250 DigraphReader<Digraph>(gr, input) |
|
251 .arcMap("cost", c) |
|
252 .arcMap("cap", u) |
|
253 .arcMap("low1", l1) |
|
254 .arcMap("low2", l2) |
|
255 .nodeMap("sup1", s1) |
|
256 .nodeMap("sup2", s2) |
|
257 .nodeMap("sup3", s3) |
|
258 .node("source", v) |
|
259 .node("target", w) |
|
260 .run(); |
|
261 |
|
262 /* |
|
263 // A. Test CapacityScaling with scaling |
|
264 { |
|
265 CapacityScaling<Digraph> mcf1(gr, u, c, s1); |
|
266 CapacityScaling<Digraph> mcf2(gr, u, c, v, w, 27); |
|
267 CapacityScaling<Digraph> mcf3(gr, u, c, s3); |
|
268 CapacityScaling<Digraph> mcf4(gr, l2, u, c, s1); |
|
269 CapacityScaling<Digraph> mcf5(gr, l2, u, c, v, w, 27); |
|
270 CapacityScaling<Digraph> mcf6(gr, l2, u, c, s3); |
|
271 |
|
272 checkMcf(mcf1, mcf1.run(), gr, l1, u, c, s1, true, 5240, "#A1"); |
|
273 checkMcf(mcf2, mcf2.run(), gr, l1, u, c, s2, true, 7620, "#A2"); |
|
274 checkMcf(mcf3, mcf3.run(), gr, l1, u, c, s3, true, 0, "#A3"); |
|
275 checkMcf(mcf4, mcf4.run(), gr, l2, u, c, s1, true, 5970, "#A4"); |
|
276 checkMcf(mcf5, mcf5.run(), gr, l2, u, c, s2, true, 8010, "#A5"); |
|
277 checkMcf(mcf6, mcf6.run(), gr, l2, u, c, s3, false, 0, "#A6"); |
|
278 } |
|
279 |
|
280 // B. Test CapacityScaling without scaling |
|
281 { |
|
282 CapacityScaling<Digraph> mcf1(gr, u, c, s1); |
|
283 CapacityScaling<Digraph> mcf2(gr, u, c, v, w, 27); |
|
284 CapacityScaling<Digraph> mcf3(gr, u, c, s3); |
|
285 CapacityScaling<Digraph> mcf4(gr, l2, u, c, s1); |
|
286 CapacityScaling<Digraph> mcf5(gr, l2, u, c, v, w, 27); |
|
287 CapacityScaling<Digraph> mcf6(gr, l2, u, c, s3); |
|
288 |
|
289 checkMcf(mcf1, mcf1.run(false), gr, l1, u, c, s1, true, 5240, "#B1"); |
|
290 checkMcf(mcf2, mcf2.run(false), gr, l1, u, c, s2, true, 7620, "#B2"); |
|
291 checkMcf(mcf3, mcf3.run(false), gr, l1, u, c, s3, true, 0, "#B3"); |
|
292 checkMcf(mcf4, mcf4.run(false), gr, l2, u, c, s1, true, 5970, "#B4"); |
|
293 checkMcf(mcf5, mcf5.run(false), gr, l2, u, c, s2, true, 8010, "#B5"); |
|
294 checkMcf(mcf6, mcf6.run(false), gr, l2, u, c, s3, false, 0, "#B6"); |
|
295 } |
|
296 |
|
297 // C. Test CostScaling using partial augment-relabel method |
|
298 { |
|
299 CostScaling<Digraph> mcf1(gr, u, c, s1); |
|
300 CostScaling<Digraph> mcf2(gr, u, c, v, w, 27); |
|
301 CostScaling<Digraph> mcf3(gr, u, c, s3); |
|
302 CostScaling<Digraph> mcf4(gr, l2, u, c, s1); |
|
303 CostScaling<Digraph> mcf5(gr, l2, u, c, v, w, 27); |
|
304 CostScaling<Digraph> mcf6(gr, l2, u, c, s3); |
|
305 |
|
306 checkMcf(mcf1, mcf1.run(), gr, l1, u, c, s1, true, 5240, "#C1"); |
|
307 checkMcf(mcf2, mcf2.run(), gr, l1, u, c, s2, true, 7620, "#C2"); |
|
308 checkMcf(mcf3, mcf3.run(), gr, l1, u, c, s3, true, 0, "#C3"); |
|
309 checkMcf(mcf4, mcf4.run(), gr, l2, u, c, s1, true, 5970, "#C4"); |
|
310 checkMcf(mcf5, mcf5.run(), gr, l2, u, c, s2, true, 8010, "#C5"); |
|
311 checkMcf(mcf6, mcf6.run(), gr, l2, u, c, s3, false, 0, "#C6"); |
|
312 } |
|
313 |
|
314 // D. Test CostScaling using push-relabel method |
|
315 { |
|
316 CostScaling<Digraph> mcf1(gr, u, c, s1); |
|
317 CostScaling<Digraph> mcf2(gr, u, c, v, w, 27); |
|
318 CostScaling<Digraph> mcf3(gr, u, c, s3); |
|
319 CostScaling<Digraph> mcf4(gr, l2, u, c, s1); |
|
320 CostScaling<Digraph> mcf5(gr, l2, u, c, v, w, 27); |
|
321 CostScaling<Digraph> mcf6(gr, l2, u, c, s3); |
|
322 |
|
323 checkMcf(mcf1, mcf1.run(false), gr, l1, u, c, s1, true, 5240, "#D1"); |
|
324 checkMcf(mcf2, mcf2.run(false), gr, l1, u, c, s2, true, 7620, "#D2"); |
|
325 checkMcf(mcf3, mcf3.run(false), gr, l1, u, c, s3, true, 0, "#D3"); |
|
326 checkMcf(mcf4, mcf4.run(false), gr, l2, u, c, s1, true, 5970, "#D4"); |
|
327 checkMcf(mcf5, mcf5.run(false), gr, l2, u, c, s2, true, 8010, "#D5"); |
|
328 checkMcf(mcf6, mcf6.run(false), gr, l2, u, c, s3, false, 0, "#D6"); |
|
329 } |
|
330 */ |
|
331 |
|
332 // E. Test NetworkSimplex with FIRST_ELIGIBLE_PIVOT |
|
333 { |
|
334 NetworkSimplex<Digraph>::PivotRuleEnum pr = |
|
335 NetworkSimplex<Digraph>::FIRST_ELIGIBLE_PIVOT; |
|
336 NetworkSimplex<Digraph> mcf1(gr, u, c, s1); |
|
337 NetworkSimplex<Digraph> mcf2(gr, u, c, v, w, 27); |
|
338 NetworkSimplex<Digraph> mcf3(gr, u, c, s3); |
|
339 NetworkSimplex<Digraph> mcf4(gr, l2, u, c, s1); |
|
340 NetworkSimplex<Digraph> mcf5(gr, l2, u, c, v, w, 27); |
|
341 NetworkSimplex<Digraph> mcf6(gr, l2, u, c, s3); |
|
342 |
|
343 checkMcf(mcf1, mcf1.run(pr), gr, l1, u, c, s1, true, 5240, "#E1"); |
|
344 checkMcf(mcf2, mcf2.run(pr), gr, l1, u, c, s2, true, 7620, "#E2"); |
|
345 checkMcf(mcf3, mcf3.run(pr), gr, l1, u, c, s3, true, 0, "#E3"); |
|
346 checkMcf(mcf4, mcf4.run(pr), gr, l2, u, c, s1, true, 5970, "#E4"); |
|
347 checkMcf(mcf5, mcf5.run(pr), gr, l2, u, c, s2, true, 8010, "#E5"); |
|
348 checkMcf(mcf6, mcf6.run(pr), gr, l2, u, c, s3, false, 0, "#E6"); |
|
349 } |
|
350 |
|
351 // F. Test NetworkSimplex with BEST_ELIGIBLE_PIVOT |
|
352 { |
|
353 NetworkSimplex<Digraph>::PivotRuleEnum pr = |
|
354 NetworkSimplex<Digraph>::BEST_ELIGIBLE_PIVOT; |
|
355 NetworkSimplex<Digraph> mcf1(gr, u, c, s1); |
|
356 NetworkSimplex<Digraph> mcf2(gr, u, c, v, w, 27); |
|
357 NetworkSimplex<Digraph> mcf3(gr, u, c, s3); |
|
358 NetworkSimplex<Digraph> mcf4(gr, l2, u, c, s1); |
|
359 NetworkSimplex<Digraph> mcf5(gr, l2, u, c, v, w, 27); |
|
360 NetworkSimplex<Digraph> mcf6(gr, l2, u, c, s3); |
|
361 |
|
362 checkMcf(mcf1, mcf1.run(pr), gr, l1, u, c, s1, true, 5240, "#F1"); |
|
363 checkMcf(mcf2, mcf2.run(pr), gr, l1, u, c, s2, true, 7620, "#F2"); |
|
364 checkMcf(mcf3, mcf3.run(pr), gr, l1, u, c, s3, true, 0, "#F3"); |
|
365 checkMcf(mcf4, mcf4.run(pr), gr, l2, u, c, s1, true, 5970, "#F4"); |
|
366 checkMcf(mcf5, mcf5.run(pr), gr, l2, u, c, s2, true, 8010, "#F5"); |
|
367 checkMcf(mcf6, mcf6.run(pr), gr, l2, u, c, s3, false, 0, "#F6"); |
|
368 } |
|
369 |
|
370 // G. Test NetworkSimplex with BLOCK_SEARCH_PIVOT |
|
371 { |
|
372 NetworkSimplex<Digraph>::PivotRuleEnum pr = |
|
373 NetworkSimplex<Digraph>::BLOCK_SEARCH_PIVOT; |
|
374 NetworkSimplex<Digraph> mcf1(gr, u, c, s1); |
|
375 NetworkSimplex<Digraph> mcf2(gr, u, c, v, w, 27); |
|
376 NetworkSimplex<Digraph> mcf3(gr, u, c, s3); |
|
377 NetworkSimplex<Digraph> mcf4(gr, l2, u, c, s1); |
|
378 NetworkSimplex<Digraph> mcf5(gr, l2, u, c, v, w, 27); |
|
379 NetworkSimplex<Digraph> mcf6(gr, l2, u, c, s3); |
|
380 |
|
381 checkMcf(mcf1, mcf1.run(pr), gr, l1, u, c, s1, true, 5240, "#G1"); |
|
382 checkMcf(mcf2, mcf2.run(pr), gr, l1, u, c, s2, true, 7620, "#G2"); |
|
383 checkMcf(mcf3, mcf3.run(pr), gr, l1, u, c, s3, true, 0, "#G3"); |
|
384 checkMcf(mcf4, mcf4.run(pr), gr, l2, u, c, s1, true, 5970, "#G4"); |
|
385 checkMcf(mcf5, mcf5.run(pr), gr, l2, u, c, s2, true, 8010, "#G5"); |
|
386 checkMcf(mcf6, mcf6.run(pr), gr, l2, u, c, s3, false, 0, "#G6"); |
|
387 } |
|
388 |
|
389 // H. Test NetworkSimplex with CANDIDATE_LIST_PIVOT |
|
390 { |
|
391 NetworkSimplex<Digraph>::PivotRuleEnum pr = |
|
392 NetworkSimplex<Digraph>::CANDIDATE_LIST_PIVOT; |
|
393 NetworkSimplex<Digraph> mcf1(gr, u, c, s1); |
|
394 NetworkSimplex<Digraph> mcf2(gr, u, c, v, w, 27); |
|
395 NetworkSimplex<Digraph> mcf3(gr, u, c, s3); |
|
396 NetworkSimplex<Digraph> mcf4(gr, l2, u, c, s1); |
|
397 NetworkSimplex<Digraph> mcf5(gr, l2, u, c, v, w, 27); |
|
398 NetworkSimplex<Digraph> mcf6(gr, l2, u, c, s3); |
|
399 |
|
400 checkMcf(mcf1, mcf1.run(pr), gr, l1, u, c, s1, true, 5240, "#H1"); |
|
401 checkMcf(mcf2, mcf2.run(pr), gr, l1, u, c, s2, true, 7620, "#H2"); |
|
402 checkMcf(mcf3, mcf3.run(pr), gr, l1, u, c, s3, true, 0, "#H3"); |
|
403 checkMcf(mcf4, mcf4.run(pr), gr, l2, u, c, s1, true, 5970, "#H4"); |
|
404 checkMcf(mcf5, mcf5.run(pr), gr, l2, u, c, s2, true, 8010, "#H5"); |
|
405 checkMcf(mcf6, mcf6.run(pr), gr, l2, u, c, s3, false, 0, "#H6"); |
|
406 } |
|
407 |
|
408 // I. Test NetworkSimplex with ALTERING_LIST_PIVOT |
|
409 { |
|
410 NetworkSimplex<Digraph>::PivotRuleEnum pr = |
|
411 NetworkSimplex<Digraph>::ALTERING_LIST_PIVOT; |
|
412 NetworkSimplex<Digraph> mcf1(gr, u, c, s1); |
|
413 NetworkSimplex<Digraph> mcf2(gr, u, c, v, w, 27); |
|
414 NetworkSimplex<Digraph> mcf3(gr, u, c, s3); |
|
415 NetworkSimplex<Digraph> mcf4(gr, l2, u, c, s1); |
|
416 NetworkSimplex<Digraph> mcf5(gr, l2, u, c, v, w, 27); |
|
417 NetworkSimplex<Digraph> mcf6(gr, l2, u, c, s3); |
|
418 |
|
419 checkMcf(mcf1, mcf1.run(pr), gr, l1, u, c, s1, true, 5240, "#I1"); |
|
420 checkMcf(mcf2, mcf2.run(pr), gr, l1, u, c, s2, true, 7620, "#I2"); |
|
421 checkMcf(mcf3, mcf3.run(pr), gr, l1, u, c, s3, true, 0, "#I3"); |
|
422 checkMcf(mcf4, mcf4.run(pr), gr, l2, u, c, s1, true, 5970, "#I4"); |
|
423 checkMcf(mcf5, mcf5.run(pr), gr, l2, u, c, s2, true, 8010, "#I5"); |
|
424 checkMcf(mcf6, mcf6.run(pr), gr, l2, u, c, s3, false, 0, "#I6"); |
|
425 } |
|
426 |
|
427 /* |
|
428 // J. Test MinCostFlow |
|
429 { |
|
430 MinCostFlow<Digraph> mcf1(gr, u, c, s1); |
|
431 MinCostFlow<Digraph> mcf2(gr, u, c, v, w, 27); |
|
432 MinCostFlow<Digraph> mcf3(gr, u, c, s3); |
|
433 MinCostFlow<Digraph> mcf4(gr, l2, u, c, s1); |
|
434 MinCostFlow<Digraph> mcf5(gr, l2, u, c, v, w, 27); |
|
435 MinCostFlow<Digraph> mcf6(gr, l2, u, c, s3); |
|
436 |
|
437 checkMcf(mcf1, mcf1.run(), gr, l1, u, c, s1, true, 5240, "#J1"); |
|
438 checkMcf(mcf2, mcf2.run(), gr, l1, u, c, s2, true, 7620, "#J2"); |
|
439 checkMcf(mcf3, mcf3.run(), gr, l1, u, c, s3, true, 0, "#J3"); |
|
440 checkMcf(mcf4, mcf4.run(), gr, l2, u, c, s1, true, 5970, "#J4"); |
|
441 checkMcf(mcf5, mcf5.run(), gr, l2, u, c, s2, true, 8010, "#J5"); |
|
442 checkMcf(mcf6, mcf6.run(), gr, l2, u, c, s3, false, 0, "#J6"); |
|
443 } |
|
444 */ |
|
445 /* |
|
446 // K. Test MinCostMaxFlow |
|
447 { |
|
448 MinCostMaxFlow<Digraph> mcmf(gr, u, c, v, w); |
|
449 mcmf.run(); |
|
450 checkMcf(mcmf, true, gr, l1, u, c, s3, true, 7620, "#K1"); |
|
451 } |
|
452 */ |
|
453 |
|
454 return 0; |
|
455 } |