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 / [822:f903263902f6:803:1b89e29c9fc7] in lemon-main


Ignore:
Files:
3 deleted
6 edited

Legend:

Unmodified
Added
Removed

  • doc/groups.dox

    r813 r771  
    407407 - \ref NetworkSimplex Primal Network Simplex algorithm with various
    408408   pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
    409  - \ref CostScaling Cost Scaling algorithm based on push/augment and
    410    relabel operations \ref goldberg90approximation, \ref goldberg97efficient,
     409 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
     410   cost scaling \ref goldberg90approximation, \ref goldberg97efficient,
    411411   \ref bunnagel98efficient.
    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.
     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.
    416418
    417419In general NetworkSimplex is the most efficient implementation,

  • lemon/Makefile.am

    r822 r799  
    6363        lemon/binom_heap.h \
    6464        lemon/bucket_heap.h \
    65         lemon/capacity_scaling.h \
    6665        lemon/cbc.h \
    6766        lemon/circulation.h \
    … …  
    7069        lemon/concept_check.h \
    7170        lemon/connectivity.h \
     71        lemon/counter.h \
    7272        lemon/core.h \
    73         lemon/cost_scaling.h \
    74         lemon/counter.h \
    7573        lemon/cplex.h \
    76         lemon/cycle_canceling.h \
    7774        lemon/dfs.h \
    7875        lemon/dijkstra.h \

  • lemon/bellman_ford.h

    r804 r788  
    238238        _dist = Traits::createDistMap(*_gr);
    239239      }
    240       if(!_mask) {
    241         _mask = new MaskMap(*_gr);
    242       }
     240      _mask = new MaskMap(*_gr, false);
    243241    }
    244242   
    … …  
    406404          _process.push_back(it);
    407405          _mask->set(it, true);
    408         }
    409       } else {
    410         for (NodeIt it(*_gr); it != INVALID; ++it) {
    411           _mask->set(it, false);
    412406        }
    413407      }

  • lemon/concepts/heap.h

    r817 r710  
    8989      /// handle the cross references. The assigned value must be
    9090      /// \c PRE_HEAP (<tt>-1</tt>) for each item.
    91 #ifdef DOXYGEN
    9291      explicit Heap(ItemIntMap &map) {}
    93 #else
    94       explicit Heap(ItemIntMap&) {}
    95 #endif     
    9692
    9793      /// \brief Constructor.
    … …  
    10399      /// \c PRE_HEAP (<tt>-1</tt>) for each item.
    104100      /// \param comp The function object used for comparing the priorities.
    105 #ifdef DOXYGEN
    106101      explicit Heap(ItemIntMap &map, const CMP &comp) {}
    107 #else
    108       explicit Heap(ItemIntMap&, const CMP&) {}
    109 #endif     
    110102
    111103      /// \brief The number of items stored in the heap.
    … …  
    135127      /// \param p The priority of the item.
    136128      /// \pre \e i must not be stored in the heap.
    137 #ifdef DOXYGEN
    138129      void push(const Item &i, const Prio &p) {}
    139 #else
    140       void push(const Item&, const Prio&) {}
    141 #endif     
    142130
    143131      /// \brief Return the item having minimum priority.
    … …  
    145133      /// This function returns the item having minimum priority.
    146134      /// \pre The heap must be non-empty.
    147       Item top() const { return Item(); }
     135      Item top() const {}
    148136
    149137      /// \brief The minimum priority.
    … …  
    151139      /// This function returns the minimum priority.
    152140      /// \pre The heap must be non-empty.
    153       Prio prio() const { return Prio(); }
     141      Prio prio() const {}
    154142
    155143      /// \brief Remove the item having minimum priority.
    … …  
    165153      /// \param i The item to delete.
    166154      /// \pre \e i must be in the heap.
    167 #ifdef DOXYGEN
    168155      void erase(const Item &i) {}
    169 #else
    170       void erase(const Item&) {}
    171 #endif     
    172156
    173157      /// \brief The priority of the given item.
    … …  
    176160      /// \param i The item.
    177161      /// \pre \e i must be in the heap.
    178 #ifdef DOXYGEN
    179162      Prio operator[](const Item &i) const {}
    180 #else
    181       Prio operator[](const Item&) const { return Prio(); }
    182 #endif     
    183163
    184164      /// \brief Set the priority of an item or insert it, if it is
    … …  
    191171      /// \param i The item.
    192172      /// \param p The priority.
    193 #ifdef DOXYGEN
    194173      void set(const Item &i, const Prio &p) {}
    195 #else
    196       void set(const Item&, const Prio&) {}
    197 #endif     
    198174
    199175      /// \brief Decrease the priority of an item to the given value.
    … …  
    203179      /// \param p The priority.
    204180      /// \pre \e i must be stored in the heap with priority at least \e p.
    205 #ifdef DOXYGEN
    206181      void decrease(const Item &i, const Prio &p) {}
    207 #else
    208       void decrease(const Item&, const Prio&) {}
    209 #endif     
    210182
    211183      /// \brief Increase the priority of an item to the given value.
    … …  
    215187      /// \param p The priority.
    216188      /// \pre \e i must be stored in the heap with priority at most \e p.
    217 #ifdef DOXYGEN
    218189      void increase(const Item &i, const Prio &p) {}
    219 #else
    220       void increase(const Item&, const Prio&) {}
    221 #endif     
    222190
    223191      /// \brief Return the state of an item.
    … …  
    229197      /// to the heap again.
    230198      /// \param i The item.
    231 #ifdef DOXYGEN
    232199      State state(const Item &i) const {}
    233 #else
    234       State state(const Item&) const { return PRE_HEAP; }
    235 #endif     
    236200
    237201      /// \brief Set the state of an item in the heap.
    … …  
    242206      /// \param i The item.
    243207      /// \param st The state. It should not be \c IN_HEAP.
    244 #ifdef DOXYGEN
    245208      void state(const Item& i, State st) {}
    246 #else
    247       void state(const Item&, State) {}
    248 #endif     
    249209
    250210

  • lemon/network_simplex.h

    r812 r788  
    4444  /// \ref amo93networkflows, \ref dantzig63linearprog,
    4545  /// \ref kellyoneill91netsimplex.
    46   /// This algorithm is a highly efficient specialized version of the
    47   /// linear programming simplex method directly for the minimum cost
    48   /// flow problem.
     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.
    4949  ///
    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
     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
    5353  /// constraints. For more information, see \ref SupplyType.
    5454  ///
    … …  
    5959  ///
    6060  /// \tparam GR The digraph type the algorithm runs on.
    61   /// \tparam V The number type used for flow amounts, capacity bounds
     61  /// \tparam V The value type used for flow amounts, capacity bounds
    6262  /// and supply values in the algorithm. By default, it is \c int.
    63   /// \tparam C The number type used for costs and potentials in the
     63  /// \tparam C The value type used for costs and potentials in the
    6464  /// algorithm. By default, it is the same as \c V.
    6565  ///
    66   /// \warning Both number types must be signed and all input data must
     66  /// \warning Both value 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.
     129    /// test inputs according to our benchmark tests.
    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<char> CharVector;
     167    typedef std::vector<bool> BoolVector;
    168168    typedef std::vector<Value> ValueVector;
    169169    typedef std::vector<Cost> CostVector;
    … …  
    213213    IntVector _last_succ;
    214214    IntVector _dirty_revs;
    215     CharVector _forward;
    216     CharVector _state;
     215    BoolVector _forward;
     216    IntVector _state;
    217217    int _root;
    218218
    … …  
    222222    int stem, par_stem, new_stem;
    223223    Value delta;
    224    
    225     const Value MAX;
    226224
    227225  public:
    … …  
    245243      const IntVector  &_target;
    246244      const CostVector &_cost;
    247       const CharVector &_state;
     245      const IntVector &_state;
    248246      const CostVector &_pi;
    249247      int &_in_arc;
    … …  
    297295      const IntVector  &_target;
    298296      const CostVector &_cost;
    299       const CharVector &_state;
     297      const IntVector &_state;
    300298      const CostVector &_pi;
    301299      int &_in_arc;
    … …  
    336334      const IntVector  &_target;
    337335      const CostVector &_cost;
    338       const CharVector &_state;
     336      const IntVector &_state;
    339337      const CostVector &_pi;
    340338      int &_in_arc;
    … …  
    409407      const IntVector  &_target;
    410408      const CostVector &_cost;
    411       const CharVector &_state;
     409      const IntVector &_state;
    412410      const CostVector &_pi;
    413411      int &_in_arc;
    … …  
    512510      const IntVector  &_target;
    513511      const CostVector &_cost;
    514       const CharVector &_state;
     512      const IntVector &_state;
    515513      const CostVector &_pi;
    516514      int &_in_arc;
    … …  
    634632    NetworkSimplex(const GR& graph, bool arc_mixing = false) :
    635633      _graph(graph), _node_id(graph), _arc_id(graph),
    636       MAX(std::numeric_limits<Value>::max()),
    637634      INF(std::numeric_limits<Value>::has_infinity ?
    638           std::numeric_limits<Value>::infinity() : MAX)
     635          std::numeric_limits<Value>::infinity() :
     636          std::numeric_limits<Value>::max())
    639637    {
    640       // Check the number types
     638      // Check the value types
    641639      LEMON_ASSERT(std::numeric_limits<Value>::is_signed,
    642640        "The flow type of NetworkSimplex must be signed");
    … …  
    730728    /// If it is not used before calling \ref run(), the upper bounds
    731729    /// will be set to \ref INF on all arcs (i.e. the flow value will be
    732     /// unbounded from above).
     730    /// unbounded from above on each arc).
    733731    ///
    734732    /// \param map An arc map storing the upper bounds.
    … …  
    10231021          Value c = _lower[i];
    10241022          if (c >= 0) {
    1025             _cap[i] = _upper[i] < MAX ? _upper[i] - c : INF;
     1023            _cap[i] = _upper[i] < INF ? _upper[i] - c : INF;
    10261024          } else {
    1027             _cap[i] = _upper[i] < MAX + c ? _upper[i] - c : INF;
     1025            _cap[i] = _upper[i] < INF + c ? _upper[i] - c : INF;
    10281026          }
    10291027          _supply[_source[i]] -= c;
    … …  
    12171215        e = _pred[u];
    12181216        d = _forward[u] ?
    1219           _flow[e] : (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]);
     1217          _flow[e] : (_cap[e] == INF ? INF : _cap[e] - _flow[e]);
    12201218        if (d < delta) {
    12211219          delta = d;
    … …  
    12281226        e = _pred[u];
    12291227        d = _forward[u] ?
    1230           (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]) : _flow[e];
     1228          (_cap[e] == INF ? INF : _cap[e] - _flow[e]) : _flow[e];
    12311229        if (d <= delta) {
    12321230          delta = d;
    … …  
    14271425        findJoinNode();
    14281426        bool change = findLeavingArc();
    1429         if (delta >= MAX) return UNBOUNDED;
     1427        if (delta >= INF) return UNBOUNDED;
    14301428        changeFlow(change);
    14311429        if (change) {

  • test/min_cost_flow_test.cc

    r819 r669  
    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>
    3027
    3128#include <lemon/concepts/digraph.h>
    32 #include <lemon/concepts/heap.h>
    3329#include <lemon/concept_check.h>
    3430
    … …  
    3733using namespace lemon;
    3834
    39 // Test networks
    4035char test_lgf[] =
    4136  "@nodes\n"
    … …  
    8277  "target 12\n";
    8378
    84 char 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  
    106 char 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
    117 typedef ListDigraph Digraph;
    118 DIGRAPH_TYPEDEFS(ListDigraph);
    119 
    120 Digraph gr;
    121 Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), l3(gr), u(gr);
    122 Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr), s4(gr), s5(gr), s6(gr);
    123 ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max());
    124 Node v, w;
    125 
    126 Digraph neg1_gr;
    127 Digraph::ArcMap<int> neg1_c(neg1_gr), neg1_l1(neg1_gr), neg1_l2(neg1_gr);
    128 ConstMap<Arc, int> neg1_u1(std::numeric_limits<int>::max()), neg1_u2(5000);
    129 Digraph::NodeMap<int> neg1_s(neg1_gr);
    130 
    131 Digraph neg2_gr;
    132 Digraph::ArcMap<int> neg2_c(neg2_gr);
    133 ConstMap<Arc, int> neg2_l(0), neg2_u(1000);
    134 Digraph::NodeMap<int> neg2_s(neg2_gr);
    135 
    13679
    13780enum SupplyType {
    … …  
    14083  LEQ
    14184};
    142 
    14385
    14486// Check the interface of an MCF algorithm
    … …  
    327269}
    328270
    329 template < typename MCF, typename Param >
    330 void 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 
    400 template < typename MCF, typename Param >
    401 void 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 
    419271int main()
    420272{
    421   // Read the test networks
     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
    422295  std::istringstream input(test_lgf);
    423296  DigraphReader<Digraph>(gr, input)
    … …  
    437310    .run();
    438311 
    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
     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
    454364  {
    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
     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
    465433  {
    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");
     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");
    539447  }
    540448
Note: See TracChangeset for help on using the changeset viewer.