COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changes in / [803:1b89e29c9fc7:822:f903263902f6] in lemon-main


Ignore:
Files:
3 added
6 edited

Legend:

Unmodified
Added
Removed

  • doc/groups.dox

    r771 r813  
    407407 - \ref NetworkSimplex Primal Network Simplex algorithm with various
    408408   pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
    409  - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
    410    cost scaling \ref goldberg90approximation, \ref goldberg97efficient,
     409 - \ref CostScaling Cost Scaling algorithm based on push/augment and
     410   relabel operations \ref goldberg90approximation, \ref goldberg97efficient,
    411411   \ref bunnagel98efficient.
    412  - \ref CapacityScaling Successive Shortest %Path algorithm with optional
    413    capacity scaling \ref edmondskarp72theoretical.
    414  - \ref CancelAndTighten The Cancel and Tighten algorithm
    415    \ref goldberg89cyclecanceling.
    416  - \ref CycleCanceling Cycle-Canceling algorithms
    417    \ref klein67primal, \ref goldberg89cyclecanceling.
     412 - \ref CapacityScaling Capacity Scaling algorithm based on the successive
     413   shortest path method \ref edmondskarp72theoretical.
     414 - \ref CycleCanceling Cycle-Canceling algorithms, two of which are
     415   strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
    418416
    419417In general NetworkSimplex is the most efficient implementation,

  • lemon/Makefile.am

    r799 r822  
    6363        lemon/binom_heap.h \
    6464        lemon/bucket_heap.h \
     65        lemon/capacity_scaling.h \
    6566        lemon/cbc.h \
    6667        lemon/circulation.h \
    … …  
    6970        lemon/concept_check.h \
    7071        lemon/connectivity.h \
     72        lemon/core.h \
     73        lemon/cost_scaling.h \
    7174        lemon/counter.h \
    72         lemon/core.h \
    7375        lemon/cplex.h \
     76        lemon/cycle_canceling.h \
    7477        lemon/dfs.h \
    7578        lemon/dijkstra.h \

  • lemon/bellman_ford.h

    r788 r804  
    238238        _dist = Traits::createDistMap(*_gr);
    239239      }
    240       _mask = new MaskMap(*_gr, false);
     240      if(!_mask) {
     241        _mask = new MaskMap(*_gr);
     242      }
    241243    }
    242244   
    … …  
    404406          _process.push_back(it);
    405407          _mask->set(it, true);
     408        }
     409      } else {
     410        for (NodeIt it(*_gr); it != INVALID; ++it) {
     411          _mask->set(it, false);
    406412        }
    407413      }

  • lemon/concepts/heap.h

    r710 r817  
    8989      /// handle the cross references. The assigned value must be
    9090      /// \c PRE_HEAP (<tt>-1</tt>) for each item.
     91#ifdef DOXYGEN
    9192      explicit Heap(ItemIntMap &map) {}
     93#else
     94      explicit Heap(ItemIntMap&) {}
     95#endif     
    9296
    9397      /// \brief Constructor.
    … …  
    99103      /// \c PRE_HEAP (<tt>-1</tt>) for each item.
    100104      /// \param comp The function object used for comparing the priorities.
     105#ifdef DOXYGEN
    101106      explicit Heap(ItemIntMap &map, const CMP &comp) {}
     107#else
     108      explicit Heap(ItemIntMap&, const CMP&) {}
     109#endif     
    102110
    103111      /// \brief The number of items stored in the heap.
    … …  
    127135      /// \param p The priority of the item.
    128136      /// \pre \e i must not be stored in the heap.
     137#ifdef DOXYGEN
    129138      void push(const Item &i, const Prio &p) {}
     139#else
     140      void push(const Item&, const Prio&) {}
     141#endif     
    130142
    131143      /// \brief Return the item having minimum priority.
    … …  
    133145      /// This function returns the item having minimum priority.
    134146      /// \pre The heap must be non-empty.
    135       Item top() const {}
     147      Item top() const { return Item(); }
    136148
    137149      /// \brief The minimum priority.
    … …  
    139151      /// This function returns the minimum priority.
    140152      /// \pre The heap must be non-empty.
    141       Prio prio() const {}
     153      Prio prio() const { return Prio(); }
    142154
    143155      /// \brief Remove the item having minimum priority.
    … …  
    153165      /// \param i The item to delete.
    154166      /// \pre \e i must be in the heap.
     167#ifdef DOXYGEN
    155168      void erase(const Item &i) {}
     169#else
     170      void erase(const Item&) {}
     171#endif     
    156172
    157173      /// \brief The priority of the given item.
    … …  
    160176      /// \param i The item.
    161177      /// \pre \e i must be in the heap.
     178#ifdef DOXYGEN
    162179      Prio operator[](const Item &i) const {}
     180#else
     181      Prio operator[](const Item&) const { return Prio(); }
     182#endif     
    163183
    164184      /// \brief Set the priority of an item or insert it, if it is
    … …  
    171191      /// \param i The item.
    172192      /// \param p The priority.
     193#ifdef DOXYGEN
    173194      void set(const Item &i, const Prio &p) {}
     195#else
     196      void set(const Item&, const Prio&) {}
     197#endif     
    174198
    175199      /// \brief Decrease the priority of an item to the given value.
    … …  
    179203      /// \param p The priority.
    180204      /// \pre \e i must be stored in the heap with priority at least \e p.
     205#ifdef DOXYGEN
    181206      void decrease(const Item &i, const Prio &p) {}
     207#else
     208      void decrease(const Item&, const Prio&) {}
     209#endif     
    182210
    183211      /// \brief Increase the priority of an item to the given value.
    … …  
    187215      /// \param p The priority.
    188216      /// \pre \e i must be stored in the heap with priority at most \e p.
     217#ifdef DOXYGEN
    189218      void increase(const Item &i, const Prio &p) {}
     219#else
     220      void increase(const Item&, const Prio&) {}
     221#endif     
    190222
    191223      /// \brief Return the state of an item.
    … …  
    197229      /// to the heap again.
    198230      /// \param i The item.
     231#ifdef DOXYGEN
    199232      State state(const Item &i) const {}
     233#else
     234      State state(const Item&) const { return PRE_HEAP; }
     235#endif     
    200236
    201237      /// \brief Set the state of an item in the heap.
    … …  
    206242      /// \param i The item.
    207243      /// \param st The state. It should not be \c IN_HEAP.
     244#ifdef DOXYGEN
    208245      void state(const Item& i, State st) {}
     246#else
     247      void state(const Item&, State) {}
     248#endif     
    209249
    210250

  • lemon/network_simplex.h

    r788 r812  
    4444  /// \ref amo93networkflows, \ref dantzig63linearprog,
    4545  /// \ref kellyoneill91netsimplex.
    46   /// This algorithm is a specialized version of the linear programming
    47   /// simplex method directly for the minimum cost flow problem.
    48   /// It is one of the most efficient solution methods.
     46  /// This algorithm is a highly efficient specialized version of the
     47  /// linear programming simplex method directly for the minimum cost
     48  /// flow problem.
    4949  ///
    50   /// In general this class is the fastest implementation available
    51   /// in LEMON for the minimum cost flow problem.
    52   /// Moreover it supports both directions of the supply/demand inequality
     50  /// In general, %NetworkSimplex is the fastest implementation available
     51  /// in LEMON for this problem.
     52  /// Moreover, it supports both directions of the supply/demand inequality
    5353  /// constraints. For more information, see \ref SupplyType.
    5454  ///
    … …  
    5959  ///
    6060  /// \tparam GR The digraph type the algorithm runs on.
    61   /// \tparam V The value type used for flow amounts, capacity bounds
     61  /// \tparam V The number type used for flow amounts, capacity bounds
    6262  /// and supply values in the algorithm. By default, it is \c int.
    63   /// \tparam C The value type used for costs and potentials in the
     63  /// \tparam C The number type used for costs and potentials in the
    6464  /// algorithm. By default, it is the same as \c V.
    6565  ///
    66   /// \warning Both value types must be signed and all input data must
     66  /// \warning Both number types must be signed and all input data must
    6767  /// be integer.
    6868  ///
    … …  
    127127    /// By default, \ref BLOCK_SEARCH "Block Search" is used, which
    128128    /// proved to be the most efficient and the most robust on various
    129     /// test inputs according to our benchmark tests.
     129    /// test inputs.
    130130    /// However, another pivot rule can be selected using the \ref run()
    131131    /// function with the proper parameter.
    … …  
    165165
    166166    typedef std::vector<int> IntVector;
    167     typedef std::vector<bool> BoolVector;
     167    typedef std::vector<char> CharVector;
    168168    typedef std::vector<Value> ValueVector;
    169169    typedef std::vector<Cost> CostVector;
    … …  
    213213    IntVector _last_succ;
    214214    IntVector _dirty_revs;
    215     BoolVector _forward;
    216     IntVector _state;
     215    CharVector _forward;
     216    CharVector _state;
    217217    int _root;
    218218
    … …  
    222222    int stem, par_stem, new_stem;
    223223    Value delta;
     224   
     225    const Value MAX;
    224226
    225227  public:
    … …  
    243245      const IntVector  &_target;
    244246      const CostVector &_cost;
    245       const IntVector &_state;
     247      const CharVector &_state;
    246248      const CostVector &_pi;
    247249      int &_in_arc;
    … …  
    295297      const IntVector  &_target;
    296298      const CostVector &_cost;
    297       const IntVector &_state;
     299      const CharVector &_state;
    298300      const CostVector &_pi;
    299301      int &_in_arc;
    … …  
    334336      const IntVector  &_target;
    335337      const CostVector &_cost;
    336       const IntVector &_state;
     338      const CharVector &_state;
    337339      const CostVector &_pi;
    338340      int &_in_arc;
    … …  
    407409      const IntVector  &_target;
    408410      const CostVector &_cost;
    409       const IntVector &_state;
     411      const CharVector &_state;
    410412      const CostVector &_pi;
    411413      int &_in_arc;
    … …  
    510512      const IntVector  &_target;
    511513      const CostVector &_cost;
    512       const IntVector &_state;
     514      const CharVector &_state;
    513515      const CostVector &_pi;
    514516      int &_in_arc;
    … …  
    632634    NetworkSimplex(const GR& graph, bool arc_mixing = false) :
    633635      _graph(graph), _node_id(graph), _arc_id(graph),
     636      MAX(std::numeric_limits<Value>::max()),
    634637      INF(std::numeric_limits<Value>::has_infinity ?
    635           std::numeric_limits<Value>::infinity() :
    636           std::numeric_limits<Value>::max())
     638          std::numeric_limits<Value>::infinity() : MAX)
    637639    {
    638       // Check the value types
     640      // Check the number types
    639641      LEMON_ASSERT(std::numeric_limits<Value>::is_signed,
    640642        "The flow type of NetworkSimplex must be signed");
    … …  
    728730    /// If it is not used before calling \ref run(), the upper bounds
    729731    /// will be set to \ref INF on all arcs (i.e. the flow value will be
    730     /// unbounded from above on each arc).
     732    /// unbounded from above).
    731733    ///
    732734    /// \param map An arc map storing the upper bounds.
    … …  
    10211023          Value c = _lower[i];
    10221024          if (c >= 0) {
    1023             _cap[i] = _upper[i] < INF ? _upper[i] - c : INF;
     1025            _cap[i] = _upper[i] < MAX ? _upper[i] - c : INF;
    10241026          } else {
    1025             _cap[i] = _upper[i] < INF + c ? _upper[i] - c : INF;
     1027            _cap[i] = _upper[i] < MAX + c ? _upper[i] - c : INF;
    10261028          }
    10271029          _supply[_source[i]] -= c;
    … …  
    12151217        e = _pred[u];
    12161218        d = _forward[u] ?
    1217           _flow[e] : (_cap[e] == INF ? INF : _cap[e] - _flow[e]);
     1219          _flow[e] : (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]);
    12181220        if (d < delta) {
    12191221          delta = d;
    … …  
    12261228        e = _pred[u];
    12271229        d = _forward[u] ?
    1228           (_cap[e] == INF ? INF : _cap[e] - _flow[e]) : _flow[e];
     1230          (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]) : _flow[e];
    12291231        if (d <= delta) {
    12301232          delta = d;
    … …  
    14251427        findJoinNode();
    14261428        bool change = findLeavingArc();
    1427         if (delta >= INF) return UNBOUNDED;
     1429        if (delta >= MAX) return UNBOUNDED;
    14281430        changeFlow(change);
    14291431        if (change) {

  • test/min_cost_flow_test.cc

    r669 r819  
    2525
    2626#include <lemon/network_simplex.h>
     27#include <lemon/capacity_scaling.h>
     28#include <lemon/cost_scaling.h>
     29#include <lemon/cycle_canceling.h>
    2730
    2831#include <lemon/concepts/digraph.h>
     32#include <lemon/concepts/heap.h>
    2933#include <lemon/concept_check.h>
    3034
    … …  
    3337using namespace lemon;
    3438
     39// Test networks
    3540char test_lgf[] =
    3641  "@nodes\n"
    … …  
    7782  "target 12\n";
    7883
     84char test_neg1_lgf[] =
     85  "@nodes\n"
     86  "label   sup\n"
     87  "    1   100\n"
     88  "    2     0\n"
     89  "    3     0\n"
     90  "    4  -100\n"
     91  "    5     0\n"
     92  "    6     0\n"
     93  "    7     0\n"
     94  "@arcs\n"
     95  "      cost   low1   low2\n"
     96  "1 2    100      0      0\n"
     97  "1 3     30      0      0\n"
     98  "2 4     20      0      0\n"
     99  "3 4     80      0      0\n"
     100  "3 2     50      0      0\n"
     101  "5 3     10      0      0\n"
     102  "5 6     80      0   1000\n"
     103  "6 7     30      0  -1000\n"
     104  "7 5   -120      0      0\n";
     105 
     106char test_neg2_lgf[] =
     107  "@nodes\n"
     108  "label   sup\n"
     109  "    1   100\n"
     110  "    2  -300\n"
     111  "@arcs\n"
     112  "      cost\n"
     113  "1 2     -1\n";
     114
     115
     116// Test data
     117typedef ListDigraph Digraph;
     118DIGRAPH_TYPEDEFS(ListDigraph);
     119
     120Digraph gr;
     121Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), l3(gr), u(gr);
     122Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr), s4(gr), s5(gr), s6(gr);
     123ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max());
     124Node v, w;
     125
     126Digraph neg1_gr;
     127Digraph::ArcMap<int> neg1_c(neg1_gr), neg1_l1(neg1_gr), neg1_l2(neg1_gr);
     128ConstMap<Arc, int> neg1_u1(std::numeric_limits<int>::max()), neg1_u2(5000);
     129Digraph::NodeMap<int> neg1_s(neg1_gr);
     130
     131Digraph neg2_gr;
     132Digraph::ArcMap<int> neg2_c(neg2_gr);
     133ConstMap<Arc, int> neg2_l(0), neg2_u(1000);
     134Digraph::NodeMap<int> neg2_s(neg2_gr);
     135
    79136
    80137enum SupplyType {
    … …  
    83140  LEQ
    84141};
     142
    85143
    86144// Check the interface of an MCF algorithm
    … …  
    269327}
    270328
     329template < typename MCF, typename Param >
     330void runMcfGeqTests( Param param,
     331                     const std::string &test_str = "",
     332                     bool full_neg_cost_support = false )
     333{
     334  MCF mcf1(gr), mcf2(neg1_gr), mcf3(neg2_gr);
     335 
     336  // Basic tests
     337  mcf1.upperMap(u).costMap(c).supplyMap(s1);
     338  checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s1,
     339           mcf1.OPTIMAL, true,     5240, test_str + "-1");
     340  mcf1.stSupply(v, w, 27);
     341  checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s2,
     342           mcf1.OPTIMAL, true,     7620, test_str + "-2");
     343  mcf1.lowerMap(l2).supplyMap(s1);
     344  checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s1,
     345           mcf1.OPTIMAL, true,     5970, test_str + "-3");
     346  mcf1.stSupply(v, w, 27);
     347  checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s2,
     348           mcf1.OPTIMAL, true,     8010, test_str + "-4");
     349  mcf1.reset().supplyMap(s1);
     350  checkMcf(mcf1, mcf1.run(param), gr, l1, cu, cc, s1,
     351           mcf1.OPTIMAL, true,       74, test_str + "-5");
     352  mcf1.lowerMap(l2).stSupply(v, w, 27);
     353  checkMcf(mcf1, mcf1.run(param), gr, l2, cu, cc, s2,
     354           mcf1.OPTIMAL, true,       94, test_str + "-6");
     355  mcf1.reset();
     356  checkMcf(mcf1, mcf1.run(param), gr, l1, cu, cc, s3,
     357           mcf1.OPTIMAL, true,        0, test_str + "-7");
     358  mcf1.lowerMap(l2).upperMap(u);
     359  checkMcf(mcf1, mcf1.run(param), gr, l2, u, cc, s3,
     360           mcf1.INFEASIBLE, false,    0, test_str + "-8");
     361  mcf1.lowerMap(l3).upperMap(u).costMap(c).supplyMap(s4);
     362  checkMcf(mcf1, mcf1.run(param), gr, l3, u, c, s4,
     363           mcf1.OPTIMAL, true,     6360, test_str + "-9");
     364
     365  // Tests for the GEQ form
     366  mcf1.reset().upperMap(u).costMap(c).supplyMap(s5);
     367  checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s5,
     368           mcf1.OPTIMAL, true,     3530, test_str + "-10", GEQ);
     369  mcf1.lowerMap(l2);
     370  checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s5,
     371           mcf1.OPTIMAL, true,     4540, test_str + "-11", GEQ);
     372  mcf1.supplyMap(s6);
     373  checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s6,
     374           mcf1.INFEASIBLE, false,    0, test_str + "-12", GEQ);
     375
     376  // Tests with negative costs
     377  mcf2.lowerMap(neg1_l1).costMap(neg1_c).supplyMap(neg1_s);
     378  checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l1, neg1_u1, neg1_c, neg1_s,
     379           mcf2.UNBOUNDED, false,     0, test_str + "-13");
     380  mcf2.upperMap(neg1_u2);
     381  checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l1, neg1_u2, neg1_c, neg1_s,
     382           mcf2.OPTIMAL, true,   -40000, test_str + "-14");
     383  mcf2.reset().lowerMap(neg1_l2).costMap(neg1_c).supplyMap(neg1_s);
     384  checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l2, neg1_u1, neg1_c, neg1_s,
     385           mcf2.UNBOUNDED, false,     0, test_str + "-15");
     386
     387  mcf3.costMap(neg2_c).supplyMap(neg2_s);
     388  if (full_neg_cost_support) {
     389    checkMcf(mcf3, mcf3.run(param), neg2_gr, neg2_l, neg2_u, neg2_c, neg2_s,
     390             mcf3.OPTIMAL, true,   -300, test_str + "-16", GEQ);
     391  } else {
     392    checkMcf(mcf3, mcf3.run(param), neg2_gr, neg2_l, neg2_u, neg2_c, neg2_s,
     393             mcf3.UNBOUNDED, false,   0, test_str + "-17", GEQ);
     394  }
     395  mcf3.upperMap(neg2_u);
     396  checkMcf(mcf3, mcf3.run(param), neg2_gr, neg2_l, neg2_u, neg2_c, neg2_s,
     397           mcf3.OPTIMAL, true,     -300, test_str + "-18", GEQ);
     398}
     399
     400template < typename MCF, typename Param >
     401void runMcfLeqTests( Param param,
     402                     const std::string &test_str = "" )
     403{
     404  // Tests for the LEQ form
     405  MCF mcf1(gr);
     406  mcf1.supplyType(mcf1.LEQ);
     407  mcf1.upperMap(u).costMap(c).supplyMap(s6);
     408  checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s6,
     409           mcf1.OPTIMAL, true,   5080, test_str + "-19", LEQ);
     410  mcf1.lowerMap(l2);
     411  checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s6,
     412           mcf1.OPTIMAL, true,   5930, test_str + "-20", LEQ);
     413  mcf1.supplyMap(s5);
     414  checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s5,
     415           mcf1.INFEASIBLE, false,  0, test_str + "-21", LEQ);
     416}
     417
     418
    271419int main()
    272420{
    273   // Check the interfaces
    274   {
    275     typedef concepts::Digraph GR;
    276     checkConcept< McfClassConcept<GR, int, int>,
    277                   NetworkSimplex<GR> >();
    278     checkConcept< McfClassConcept<GR, double, double>,
    279                   NetworkSimplex<GR, double> >();
    280     checkConcept< McfClassConcept<GR, int, double>,
    281                   NetworkSimplex<GR, int, double> >();
    282   }
    283 
    284   // Run various MCF tests
    285   typedef ListDigraph Digraph;
    286   DIGRAPH_TYPEDEFS(ListDigraph);
    287 
    288   // Read the test digraph
    289   Digraph gr;
    290   Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), l3(gr), u(gr);
    291   Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr), s4(gr), s5(gr), s6(gr);
    292   ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max());
    293   Node v, w;
    294 
     421  // Read the test networks
    295422  std::istringstream input(test_lgf);
    296423  DigraphReader<Digraph>(gr, input)
    … …  
    310437    .run();
    311438 
    312   // Build test digraphs with negative costs
    313   Digraph neg_gr;
    314   Node n1 = neg_gr.addNode();
    315   Node n2 = neg_gr.addNode();
    316   Node n3 = neg_gr.addNode();
    317   Node n4 = neg_gr.addNode();
    318   Node n5 = neg_gr.addNode();
    319   Node n6 = neg_gr.addNode();
    320   Node n7 = neg_gr.addNode();
    321  
    322   Arc a1 = neg_gr.addArc(n1, n2);
    323   Arc a2 = neg_gr.addArc(n1, n3);
    324   Arc a3 = neg_gr.addArc(n2, n4);
    325   Arc a4 = neg_gr.addArc(n3, n4);
    326   Arc a5 = neg_gr.addArc(n3, n2);
    327   Arc a6 = neg_gr.addArc(n5, n3);
    328   Arc a7 = neg_gr.addArc(n5, n6);
    329   Arc a8 = neg_gr.addArc(n6, n7);
    330   Arc a9 = neg_gr.addArc(n7, n5);
    331  
    332   Digraph::ArcMap<int> neg_c(neg_gr), neg_l1(neg_gr, 0), neg_l2(neg_gr, 0);
    333   ConstMap<Arc, int> neg_u1(std::numeric_limits<int>::max()), neg_u2(5000);
    334   Digraph::NodeMap<int> neg_s(neg_gr, 0);
    335  
    336   neg_l2[a7] =  1000;
    337   neg_l2[a8] = -1000;
    338  
    339   neg_s[n1] =  100;
    340   neg_s[n4] = -100;
    341  
    342   neg_c[a1] =  100;
    343   neg_c[a2] =   30;
    344   neg_c[a3] =   20;
    345   neg_c[a4] =   80;
    346   neg_c[a5] =   50;
    347   neg_c[a6] =   10;
    348   neg_c[a7] =   80;
    349   neg_c[a8] =   30;
    350   neg_c[a9] = -120;
    351 
    352   Digraph negs_gr;
    353   Digraph::NodeMap<int> negs_s(negs_gr);
    354   Digraph::ArcMap<int> negs_c(negs_gr);
    355   ConstMap<Arc, int> negs_l(0), negs_u(1000);
    356   n1 = negs_gr.addNode();
    357   n2 = negs_gr.addNode();
    358   negs_s[n1] = 100;
    359   negs_s[n2] = -300;
    360   negs_c[negs_gr.addArc(n1, n2)] = -1;
    361 
    362 
    363   // A. Test NetworkSimplex with the default pivot rule
    364   {
    365     NetworkSimplex<Digraph> mcf(gr);
    366 
    367     // Check the equality form
    368     mcf.upperMap(u).costMap(c);
    369     checkMcf(mcf, mcf.supplyMap(s1).run(),
    370              gr, l1, u, c, s1, mcf.OPTIMAL, true,   5240, "#A1");
    371     checkMcf(mcf, mcf.stSupply(v, w, 27).run(),
    372              gr, l1, u, c, s2, mcf.OPTIMAL, true,   7620, "#A2");
    373     mcf.lowerMap(l2);
    374     checkMcf(mcf, mcf.supplyMap(s1).run(),
    375              gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#A3");
    376     checkMcf(mcf, mcf.stSupply(v, w, 27).run(),
    377              gr, l2, u, c, s2, mcf.OPTIMAL, true,   8010, "#A4");
    378     mcf.reset();
    379     checkMcf(mcf, mcf.supplyMap(s1).run(),
    380              gr, l1, cu, cc, s1, mcf.OPTIMAL, true,   74, "#A5");
    381     checkMcf(mcf, mcf.lowerMap(l2).stSupply(v, w, 27).run(),
    382              gr, l2, cu, cc, s2, mcf.OPTIMAL, true,   94, "#A6");
    383     mcf.reset();
    384     checkMcf(mcf, mcf.run(),
    385              gr, l1, cu, cc, s3, mcf.OPTIMAL, true,    0, "#A7");
    386     checkMcf(mcf, mcf.lowerMap(l2).upperMap(u).run(),
    387              gr, l2, u, cc, s3, mcf.INFEASIBLE, false, 0, "#A8");
    388     mcf.reset().lowerMap(l3).upperMap(u).costMap(c).supplyMap(s4);
    389     checkMcf(mcf, mcf.run(),
    390              gr, l3, u, c, s4, mcf.OPTIMAL, true,   6360, "#A9");
    391 
    392     // Check the GEQ form
    393     mcf.reset().upperMap(u).costMap(c).supplyMap(s5);
    394     checkMcf(mcf, mcf.run(),
    395              gr, l1, u, c, s5, mcf.OPTIMAL, true,   3530, "#A10", GEQ);
    396     mcf.supplyType(mcf.GEQ);
    397     checkMcf(mcf, mcf.lowerMap(l2).run(),
    398              gr, l2, u, c, s5, mcf.OPTIMAL, true,   4540, "#A11", GEQ);
    399     mcf.supplyMap(s6);
    400     checkMcf(mcf, mcf.run(),
    401              gr, l2, u, c, s6, mcf.INFEASIBLE, false,  0, "#A12", GEQ);
    402 
    403     // Check the LEQ form
    404     mcf.reset().supplyType(mcf.LEQ);
    405     mcf.upperMap(u).costMap(c).supplyMap(s6);
    406     checkMcf(mcf, mcf.run(),
    407              gr, l1, u, c, s6, mcf.OPTIMAL, true,   5080, "#A13", LEQ);
    408     checkMcf(mcf, mcf.lowerMap(l2).run(),
    409              gr, l2, u, c, s6, mcf.OPTIMAL, true,   5930, "#A14", LEQ);
    410     mcf.supplyMap(s5);
    411     checkMcf(mcf, mcf.run(),
    412              gr, l2, u, c, s5, mcf.INFEASIBLE, false,  0, "#A15", LEQ);
    413 
    414     // Check negative costs
    415     NetworkSimplex<Digraph> neg_mcf(neg_gr);
    416     neg_mcf.lowerMap(neg_l1).costMap(neg_c).supplyMap(neg_s);
    417     checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l1, neg_u1,
    418       neg_c, neg_s, neg_mcf.UNBOUNDED, false,    0, "#A16");
    419     neg_mcf.upperMap(neg_u2);
    420     checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l1, neg_u2,
    421       neg_c, neg_s, neg_mcf.OPTIMAL, true,  -40000, "#A17");
    422     neg_mcf.reset().lowerMap(neg_l2).costMap(neg_c).supplyMap(neg_s);
    423     checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l2, neg_u1,
    424       neg_c, neg_s, neg_mcf.UNBOUNDED, false,    0, "#A18");
    425      
    426     NetworkSimplex<Digraph> negs_mcf(negs_gr);
    427     negs_mcf.costMap(negs_c).supplyMap(negs_s);
    428     checkMcf(negs_mcf, negs_mcf.run(), negs_gr, negs_l, negs_u,
    429       negs_c, negs_s, negs_mcf.OPTIMAL, true, -300, "#A19", GEQ);
    430   }
    431 
    432   // B. Test NetworkSimplex with each pivot rule
    433   {
    434     NetworkSimplex<Digraph> mcf(gr);
    435     mcf.supplyMap(s1).costMap(c).upperMap(u).lowerMap(l2);
    436 
    437     checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::FIRST_ELIGIBLE),
    438              gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B1");
    439     checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BEST_ELIGIBLE),
    440              gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B2");
    441     checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BLOCK_SEARCH),
    442              gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B3");
    443     checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::CANDIDATE_LIST),
    444              gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B4");
    445     checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::ALTERING_LIST),
    446              gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B5");
     439  std::istringstream neg_inp1(test_neg1_lgf);
     440  DigraphReader<Digraph>(neg1_gr, neg_inp1)
     441    .arcMap("cost", neg1_c)
     442    .arcMap("low1", neg1_l1)
     443    .arcMap("low2", neg1_l2)
     444    .nodeMap("sup", neg1_s)
     445    .run();
     446 
     447  std::istringstream neg_inp2(test_neg2_lgf);
     448  DigraphReader<Digraph>(neg2_gr, neg_inp2)
     449    .arcMap("cost", neg2_c)
     450    .nodeMap("sup", neg2_s)
     451    .run();
     452 
     453  // Check the interface of NetworkSimplex
     454  {
     455    typedef concepts::Digraph GR;
     456    checkConcept< McfClassConcept<GR, int, int>,
     457                  NetworkSimplex<GR> >();
     458    checkConcept< McfClassConcept<GR, double, double>,
     459                  NetworkSimplex<GR, double> >();
     460    checkConcept< McfClassConcept<GR, int, double>,
     461                  NetworkSimplex<GR, int, double> >();
     462  }
     463
     464  // Check the interface of CapacityScaling
     465  {
     466    typedef concepts::Digraph GR;
     467    checkConcept< McfClassConcept<GR, int, int>,
     468                  CapacityScaling<GR> >();
     469    checkConcept< McfClassConcept<GR, double, double>,
     470                  CapacityScaling<GR, double> >();
     471    checkConcept< McfClassConcept<GR, int, double>,
     472                  CapacityScaling<GR, int, double> >();
     473    typedef CapacityScaling<GR>::
     474      SetHeap<concepts::Heap<int, RangeMap<int> > >::Create CAS;
     475    checkConcept< McfClassConcept<GR, int, int>, CAS >();
     476  }
     477
     478  // Check the interface of CostScaling
     479  {
     480    typedef concepts::Digraph GR;
     481    checkConcept< McfClassConcept<GR, int, int>,
     482                  CostScaling<GR> >();
     483    checkConcept< McfClassConcept<GR, double, double>,
     484                  CostScaling<GR, double> >();
     485    checkConcept< McfClassConcept<GR, int, double>,
     486                  CostScaling<GR, int, double> >();
     487    typedef CostScaling<GR>::
     488      SetLargeCost<double>::Create COS;
     489    checkConcept< McfClassConcept<GR, int, int>, COS >();
     490  }
     491
     492  // Check the interface of CycleCanceling
     493  {
     494    typedef concepts::Digraph GR;
     495    checkConcept< McfClassConcept<GR, int, int>,
     496                  CycleCanceling<GR> >();
     497    checkConcept< McfClassConcept<GR, double, double>,
     498                  CycleCanceling<GR, double> >();
     499    checkConcept< McfClassConcept<GR, int, double>,
     500                  CycleCanceling<GR, int, double> >();
     501  }
     502
     503  // Test NetworkSimplex
     504  {
     505    typedef NetworkSimplex<Digraph> MCF;
     506    runMcfGeqTests<MCF>(MCF::FIRST_ELIGIBLE, "NS-FE", true);
     507    runMcfLeqTests<MCF>(MCF::FIRST_ELIGIBLE, "NS-FE");
     508    runMcfGeqTests<MCF>(MCF::BEST_ELIGIBLE,  "NS-BE", true);
     509    runMcfLeqTests<MCF>(MCF::BEST_ELIGIBLE,  "NS-BE");
     510    runMcfGeqTests<MCF>(MCF::BLOCK_SEARCH,   "NS-BS", true);
     511    runMcfLeqTests<MCF>(MCF::BLOCK_SEARCH,   "NS-BS");
     512    runMcfGeqTests<MCF>(MCF::CANDIDATE_LIST, "NS-CL", true);
     513    runMcfLeqTests<MCF>(MCF::CANDIDATE_LIST, "NS-CL");
     514    runMcfGeqTests<MCF>(MCF::ALTERING_LIST,  "NS-AL", true);
     515    runMcfLeqTests<MCF>(MCF::ALTERING_LIST,  "NS-AL");
     516  }
     517 
     518  // Test CapacityScaling
     519  {
     520    typedef CapacityScaling<Digraph> MCF;
     521    runMcfGeqTests<MCF>(0, "SSP");
     522    runMcfGeqTests<MCF>(2, "CAS");
     523  }
     524
     525  // Test CostScaling
     526  {
     527    typedef CostScaling<Digraph> MCF;
     528    runMcfGeqTests<MCF>(MCF::PUSH, "COS-PR");
     529    runMcfGeqTests<MCF>(MCF::AUGMENT, "COS-AR");
     530    runMcfGeqTests<MCF>(MCF::PARTIAL_AUGMENT, "COS-PAR");
     531  }
     532
     533  // Test CycleCanceling
     534  {
     535    typedef CycleCanceling<Digraph> MCF;
     536    runMcfGeqTests<MCF>(MCF::SIMPLE_CYCLE_CANCELING, "SCC");
     537    runMcfGeqTests<MCF>(MCF::MINIMUM_MEAN_CYCLE_CANCELING, "MMCC");
     538    runMcfGeqTests<MCF>(MCF::CANCEL_AND_TIGHTEN, "CAT");
    447539  }
    448540
Note: See TracChangeset for help on using the changeset viewer.