COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 605:5232721b3f14 in lemon-main for test


Ignore:
Timestamp:
03/25/09 15:58:44 (16 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Rework the interface of NetworkSimplex? (#234)

The parameters of the problem can be set with separate functions
instead of different constructors.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • test/min_cost_flow_test.cc

    r601 r605  
    2121
    2222#include <lemon/list_graph.h>
    23 #include <lemon/smart_graph.h>
    2423#include <lemon/lgf_reader.h>
    2524
    26 //#include <lemon/cycle_canceling.h>
    27 //#include <lemon/capacity_scaling.h>
    28 //#include <lemon/cost_scaling.h>
    2925#include <lemon/network_simplex.h>
    30 //#include <lemon/min_cost_flow.h>
    31 //#include <lemon/min_cost_max_flow.h>
    3226
    3327#include <lemon/concepts/digraph.h>
    … …  
    9488      checkConcept<concepts::Digraph, GR>();
    9589
    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);
     90      MCF mcf(g);
     91
     92      b = mcf.lowerMap(lower)
     93             .upperMap(upper)
     94             .capacityMap(upper)
     95             .boundMaps(lower, upper)
     96             .costMap(cost)
     97             .supplyMap(sup)
     98             .stSupply(n, n, k)
     99             .run();
     100
     101      const typename MCF::FlowMap &fm = mcf.flowMap();
     102      const typename MCF::PotentialMap &pm = mcf.potentialMap();
     103
     104      v = mcf.totalCost();
     105      double x = mcf.template totalCost<double>();
     106      v = mcf.flow(a);
     107      v = mcf.potential(n);
     108      mcf.flowMap(flow);
     109      mcf.potentialMap(pot);
     110
    117111      ignore_unused_variable_warning(fm);
    118112      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);
     113      ignore_unused_variable_warning(x);
    126114    }
    127115
    … …  
    140128    const Value &k;
    141129    Value v;
     130    bool b;
    142131
    143132    typename MCF::FlowMap &flow;
    … …  
    173162
    174163// Check the feasibility of the given potentials (dual soluiton)
    175 // using the Complementary Slackness optimality condition
     164// using the "Complementary Slackness" optimality condition
    176165template < typename GR, typename LM, typename UM,
    177166           typename CM, typename FM, typename PM >
    … …  
    218207  {
    219208    typedef int Value;
    220     // This typedef should be enabled if the standard maps are
    221     // reference maps in the graph concepts
     209    // TODO: This typedef should be enabled if the standard maps are
     210    // reference maps in the graph concepts (See #190).
     211/**/
    222212    //typedef concepts::Digraph GR;
    223213    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> >();
     214/**/
    233215    checkConcept< McfClassConcept<GR, Value>,
    234                   NetworkSimplex<GR, AM, AM, AM, NM> >();
    235     //checkConcept< MinCostFlow<GR, Value>,
    236     //              NetworkSimplex<GR, AM, AM, AM, NM> >();
     216                  NetworkSimplex<GR, Value> >();
    237217  }
    238218
    … …  
    245225  Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), u(gr);
    246226  Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr);
     227  ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max());
    247228  Node v, w;
    248229
    … …  
    260241    .run();
    261242
    262 /*
    263   // A. Test CapacityScaling with scaling
     243  // A. Test NetworkSimplex with the default pivot rule
    264244  {
    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
     245    NetworkSimplex<Digraph> mcf1(gr), mcf2(gr), mcf3(gr), mcf4(gr),
     246                            mcf5(gr), mcf6(gr), mcf7(gr), mcf8(gr);
     247
     248    checkMcf(mcf1, mcf1.upperMap(u).costMap(c).supplyMap(s1).run(),
     249             gr, l1, u, c, s1, true,  5240, "#A1");
     250    checkMcf(mcf2, mcf2.upperMap(u).costMap(c).stSupply(v, w, 27).run(),
     251             gr, l1, u, c, s2, true,  7620, "#A2");
     252    checkMcf(mcf3, mcf3.boundMaps(l2, u).costMap(c).supplyMap(s1).run(),
     253             gr, l2, u, c, s1, true,  5970, "#A3");
     254    checkMcf(mcf4, mcf4.boundMaps(l2, u).costMap(c).stSupply(v, w, 27).run(),
     255             gr, l2, u, c, s2, true,  8010, "#A4");
     256    checkMcf(mcf5, mcf5.supplyMap(s1).run(),
     257             gr, l1, cu, cc, s1, true,  74, "#A5");
     258    checkMcf(mcf6, mcf6.stSupply(v, w, 27).lowerMap(l2).run(),
     259             gr, l2, cu, cc, s2, true,  94, "#A6");
     260    checkMcf(mcf7, mcf7.run(),
     261             gr, l1, cu, cc, s3, true,   0, "#A7");
     262    checkMcf(mcf8, mcf8.boundMaps(l2, u).run(),
     263             gr, l2, u, cc, s3, false,   0, "#A8");
     264  }
     265
     266  // B. Test NetworkSimplex with each pivot rule
    281267  {
    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 */
     268    NetworkSimplex<Digraph> mcf1(gr), mcf2(gr), mcf3(gr), mcf4(gr), mcf5(gr);
     269    NetworkSimplex<Digraph>::PivotRule pr;
     270
     271    pr = NetworkSimplex<Digraph>::FIRST_ELIGIBLE;
     272    checkMcf(mcf1, mcf1.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
     273             gr, l2, u, c, s1, true,  5970, "#B1");
     274    pr = NetworkSimplex<Digraph>::BEST_ELIGIBLE;
     275    checkMcf(mcf2, mcf2.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
     276             gr, l2, u, c, s1, true,  5970, "#B2");
     277    pr = NetworkSimplex<Digraph>::BLOCK_SEARCH;
     278    checkMcf(mcf3, mcf3.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
     279             gr, l2, u, c, s1, true,  5970, "#B3");
     280    pr = NetworkSimplex<Digraph>::CANDIDATE_LIST;
     281    checkMcf(mcf4, mcf4.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
     282             gr, l2, u, c, s1, true,  5970, "#B4");
     283    pr = NetworkSimplex<Digraph>::ALTERING_LIST;
     284    checkMcf(mcf5, mcf5.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
     285             gr, l2, u, c, s1, true,  5970, "#B5");
     286  }
    453287
    454288  return 0;
Note: See TracChangeset for help on using the changeset viewer.