test/min_cost_flow_test.cc
changeset 956 141f9c0db4a3
parent 898 75c97c3786d6
child 1270 dceba191c00d
child 1317 b40c2bbb8da5
     1.1 --- a/test/min_cost_flow_test.cc	Wed Mar 17 12:35:52 2010 +0100
     1.2 +++ b/test/min_cost_flow_test.cc	Sat Mar 06 14:35:12 2010 +0000
     1.3 @@ -2,7 +2,7 @@
     1.4   *
     1.5   * This file is a part of LEMON, a generic C++ optimization library.
     1.6   *
     1.7 - * Copyright (C) 2003-2009
     1.8 + * Copyright (C) 2003-2010
     1.9   * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    1.10   * (Egervary Research Group on Combinatorial Optimization, EGRES).
    1.11   *
    1.12 @@ -52,7 +52,7 @@
    1.13    "   10    -2    0    0    0   -7   -2\n"
    1.14    "   11     0    0    0    0  -10    0\n"
    1.15    "   12   -20  -27    0  -30  -30  -20\n"
    1.16 -  "\n"                
    1.17 +  "\n"
    1.18    "@arcs\n"
    1.19    "       cost  cap low1 low2 low3\n"
    1.20    " 1  2    70   11    0    8    8\n"
    1.21 @@ -102,7 +102,7 @@
    1.22    "5 6     80      0   1000\n"
    1.23    "6 7     30      0  -1000\n"
    1.24    "7 5   -120      0      0\n";
    1.25 -  
    1.26 +
    1.27  char test_neg2_lgf[] =
    1.28    "@nodes\n"
    1.29    "label   sup\n"
    1.30 @@ -151,7 +151,7 @@
    1.31    struct Constraints {
    1.32      void constraints() {
    1.33        checkConcept<concepts::Digraph, GR>();
    1.34 -      
    1.35 +
    1.36        const Constraints& me = *this;
    1.37  
    1.38        MCF mcf(me.g);
    1.39 @@ -180,7 +180,7 @@
    1.40      typedef concepts::ReadMap<Arc, Cost> CAM;
    1.41      typedef concepts::WriteMap<Arc, Value> FlowMap;
    1.42      typedef concepts::WriteMap<Node, Cost> PotMap;
    1.43 -  
    1.44 +
    1.45      GR g;
    1.46      VAM lower;
    1.47      VAM upper;
    1.48 @@ -234,7 +234,7 @@
    1.49  template < typename GR, typename LM, typename UM,
    1.50             typename CM, typename SM, typename FM, typename PM >
    1.51  bool checkPotential( const GR& gr, const LM& lower, const UM& upper,
    1.52 -                     const CM& cost, const SM& supply, const FM& flow, 
    1.53 +                     const CM& cost, const SM& supply, const FM& flow,
    1.54                       const PM& pi, SupplyType type )
    1.55  {
    1.56    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
    1.57 @@ -247,7 +247,7 @@
    1.58            (red_cost > 0 && flow[e] == lower[e]) ||
    1.59            (red_cost < 0 && flow[e] == upper[e]);
    1.60    }
    1.61 -  
    1.62 +
    1.63    for (NodeIt n(gr); opt && n != INVALID; ++n) {
    1.64      typename SM::Value sum = 0;
    1.65      for (OutArcIt e(gr, n); e != INVALID; ++e)
    1.66 @@ -260,7 +260,7 @@
    1.67        opt = (pi[n] >= 0) && (sum == supply[n] || pi[n] == 0);
    1.68      }
    1.69    }
    1.70 -  
    1.71 +
    1.72    return opt;
    1.73  }
    1.74  
    1.75 @@ -285,7 +285,7 @@
    1.76        red_supply[gr.target(a)] += lower[a];
    1.77      }
    1.78    }
    1.79 -  
    1.80 +
    1.81    for (NodeIt n(gr); n != INVALID; ++n) {
    1.82      dual_cost -= red_supply[n] * pi[n];
    1.83    }
    1.84 @@ -294,7 +294,7 @@
    1.85        cost[a] + pi[gr.source(a)] - pi[gr.target(a)];
    1.86      dual_cost -= (upper[a] - lower[a]) * std::max(-red_cost, 0);
    1.87    }
    1.88 -  
    1.89 +
    1.90    return dual_cost == total;
    1.91  }
    1.92  
    1.93 @@ -332,7 +332,7 @@
    1.94                       bool full_neg_cost_support = false )
    1.95  {
    1.96    MCF mcf1(gr), mcf2(neg1_gr), mcf3(neg2_gr);
    1.97 -  
    1.98 +
    1.99    // Basic tests
   1.100    mcf1.upperMap(u).costMap(c).supplyMap(s1);
   1.101    checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s1,
   1.102 @@ -435,7 +435,7 @@
   1.103      .node("source", v)
   1.104      .node("target", w)
   1.105      .run();
   1.106 -  
   1.107 +
   1.108    std::istringstream neg_inp1(test_neg1_lgf);
   1.109    DigraphReader<Digraph>(neg1_gr, neg_inp1)
   1.110      .arcMap("cost", neg1_c)
   1.111 @@ -443,13 +443,13 @@
   1.112      .arcMap("low2", neg1_l2)
   1.113      .nodeMap("sup", neg1_s)
   1.114      .run();
   1.115 -  
   1.116 +
   1.117    std::istringstream neg_inp2(test_neg2_lgf);
   1.118    DigraphReader<Digraph>(neg2_gr, neg_inp2)
   1.119      .arcMap("cost", neg2_c)
   1.120      .nodeMap("sup", neg2_s)
   1.121      .run();
   1.122 -  
   1.123 +
   1.124    // Check the interface of NetworkSimplex
   1.125    {
   1.126      typedef concepts::Digraph GR;
   1.127 @@ -501,7 +501,7 @@
   1.128    }
   1.129  
   1.130    // Test NetworkSimplex
   1.131 -  { 
   1.132 +  {
   1.133      typedef NetworkSimplex<Digraph> MCF;
   1.134      runMcfGeqTests<MCF>(MCF::FIRST_ELIGIBLE, "NS-FE", true);
   1.135      runMcfLeqTests<MCF>(MCF::FIRST_ELIGIBLE, "NS-FE");
   1.136 @@ -514,7 +514,7 @@
   1.137      runMcfGeqTests<MCF>(MCF::ALTERING_LIST,  "NS-AL", true);
   1.138      runMcfLeqTests<MCF>(MCF::ALTERING_LIST,  "NS-AL");
   1.139    }
   1.140 -  
   1.141 +
   1.142    // Test CapacityScaling
   1.143    {
   1.144      typedef CapacityScaling<Digraph> MCF;