COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

source: lemon-main/test/min_cost_flow_test.cc @ 602:a79ef774fae1

Last change on this file since 602:a79ef774fae1 was 601:e8349c6f12ca, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Port NetworkSimplex? from SVN -r3520 (#234)
File size: 15.8 KB
Line 
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
38using namespace lemon;
39
40char 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
86template <typename GR, typename Value>
87class McfClassConcept
88{
89public:
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 &sup;
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)
151template < typename GR, typename LM, typename UM,
152           typename SM, typename FM >
153bool 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
176template < typename GR, typename LM, typename UM,
177           typename CM, typename FM, typename PM >
178bool 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
195template < typename MCF, typename GR,
196           typename LM, typename UM,
197           typename CM, typename SM >
198void 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
215int 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}
Note: See TracBrowser for help on using the repository browser.