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


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.

Files:
3 edited

Legend:

Unmodified
Added
Removed

  • lemon/network_simplex.h

    r604 r605  
    2323///
    2424/// \file
    25 /// \brief Network simplex algorithm for finding a minimum cost flow.
     25/// \brief Network Simplex algorithm for finding a minimum cost flow.
    2626
    2727#include <vector>
    … …  
    3737  /// @{
    3838
    39   /// \brief Implementation of the primal network simplex algorithm
     39  /// \brief Implementation of the primal Network Simplex algorithm
    4040  /// for finding a \ref min_cost_flow "minimum cost flow".
    4141  ///
    42   /// \ref NetworkSimplex implements the primal network simplex algorithm
     42  /// \ref NetworkSimplex implements the primal Network Simplex algorithm
    4343  /// for finding a \ref min_cost_flow "minimum cost flow".
    4444  ///
    45   /// \tparam Digraph The digraph type the algorithm runs on.
    46   /// \tparam LowerMap The type of the lower bound map.
    47   /// \tparam CapacityMap The type of the capacity (upper bound) map.
    48   /// \tparam CostMap The type of the cost (length) map.
    49   /// \tparam SupplyMap The type of the supply map.
     45  /// \tparam GR The digraph type the algorithm runs on.
     46  /// \tparam V The value type used in the algorithm.
     47  /// By default it is \c int.
    5048  ///
    51   /// \warning
    52   /// - Arc capacities and costs should be \e non-negative \e integers.
    53   /// - Supply values should be \e signed \e integers.
    54   /// - The value types of the maps should be convertible to each other.
    55   /// - \c CostMap::Value must be signed type.
     49  /// \warning \c V must be a signed integer type.
    5650  ///
    57   /// \note \ref NetworkSimplex provides five different pivot rule
    58   /// implementations that significantly affect the efficiency of the
    59   /// algorithm.
    60   /// By default "Block Search" pivot rule is used, which proved to be
    61   /// by far the most efficient according to our benchmark tests.
    62   /// However another pivot rule can be selected using \ref run()
    63   /// function with the proper parameter.
    64 #ifdef DOXYGEN
    65   template < typename Digraph,
    66              typename LowerMap,
    67              typename CapacityMap,
    68              typename CostMap,
    69              typename SupplyMap >
    70 
    71 #else
    72   template < typename Digraph,
    73              typename LowerMap = typename Digraph::template ArcMap<int>,
    74              typename CapacityMap = typename Digraph::template ArcMap<int>,
    75              typename CostMap = typename Digraph::template ArcMap<int>,
    76              typename SupplyMap = typename Digraph::template NodeMap<int> >
    77 #endif
     51  /// \note %NetworkSimplex provides five different pivot rule
     52  /// implementations. For more information see \ref PivotRule.
     53  template <typename GR, typename V = int>
    7854  class NetworkSimplex
    7955  {
    80     TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    81 
    82     typedef typename CapacityMap::Value Capacity;
    83     typedef typename CostMap::Value Cost;
    84     typedef typename SupplyMap::Value Supply;
     56  public:
     57
     58    /// The value type of the algorithm
     59    typedef V Value;
     60    /// The type of the flow map
     61    typedef typename GR::template ArcMap<Value> FlowMap;
     62    /// The type of the potential map
     63    typedef typename GR::template NodeMap<Value> PotentialMap;
     64
     65  public:
     66
     67    /// \brief Enum type for selecting the pivot rule.
     68    ///
     69    /// Enum type for selecting the pivot rule for the \ref run()
     70    /// function.
     71    ///
     72    /// \ref NetworkSimplex provides five different pivot rule
     73    /// implementations that significantly affect the running time
     74    /// of the algorithm.
     75    /// By default \ref BLOCK_SEARCH "Block Search" is used, which
     76    /// proved to be the most efficient and the most robust on various
     77    /// test inputs according to our benchmark tests.
     78    /// However another pivot rule can be selected using the \ref run()
     79    /// function with the proper parameter.
     80    enum PivotRule {
     81
     82      /// The First Eligible pivot rule.
     83      /// The next eligible arc is selected in a wraparound fashion
     84      /// in every iteration.
     85      FIRST_ELIGIBLE,
     86
     87      /// The Best Eligible pivot rule.
     88      /// The best eligible arc is selected in every iteration.
     89      BEST_ELIGIBLE,
     90
     91      /// The Block Search pivot rule.
     92      /// A specified number of arcs are examined in every iteration
     93      /// in a wraparound fashion and the best eligible arc is selected
     94      /// from this block.
     95      BLOCK_SEARCH,
     96
     97      /// The Candidate List pivot rule.
     98      /// In a major iteration a candidate list is built from eligible arcs
     99      /// in a wraparound fashion and in the following minor iterations
     100      /// the best eligible arc is selected from this list.
     101      CANDIDATE_LIST,
     102
     103      /// The Altering Candidate List pivot rule.
     104      /// It is a modified version of the Candidate List method.
     105      /// It keeps only the several best eligible arcs from the former
     106      /// candidate list and extends this list in every iteration.
     107      ALTERING_LIST
     108    };
     109
     110  private:
     111
     112    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
     113
     114    typedef typename GR::template ArcMap<Value> ValueArcMap;
     115    typedef typename GR::template NodeMap<Value> ValueNodeMap;
    85116
    86117    typedef std::vector<Arc> ArcVector;
    … …  
    88119    typedef std::vector<int> IntVector;
    89120    typedef std::vector<bool> BoolVector;
    90     typedef std::vector<Capacity> CapacityVector;
    91     typedef std::vector<Cost> CostVector;
    92     typedef std::vector<Supply> SupplyVector;
    93 
    94   public:
    95 
    96     /// The type of the flow map
    97     typedef typename Digraph::template ArcMap<Capacity> FlowMap;
    98     /// The type of the potential map
    99     typedef typename Digraph::template NodeMap<Cost> PotentialMap;
    100 
    101   public:
    102 
    103     /// Enum type for selecting the pivot rule used by \ref run()
    104     enum PivotRuleEnum {
    105       FIRST_ELIGIBLE_PIVOT,
    106       BEST_ELIGIBLE_PIVOT,
    107       BLOCK_SEARCH_PIVOT,
    108       CANDIDATE_LIST_PIVOT,
    109       ALTERING_LIST_PIVOT
    110     };
    111 
    112   private:
     121    typedef std::vector<Value> ValueVector;
    113122
    114123    // State constants for arcs
    … …  
    121130  private:
    122131
    123     // References for the original data
    124     const Digraph &_graph;
    125     const LowerMap *_orig_lower;
    126     const CapacityMap &_orig_cap;
    127     const CostMap &_orig_cost;
    128     const SupplyMap *_orig_supply;
    129     Node _orig_source;
    130     Node _orig_target;
    131     Capacity _orig_flow_value;
     132    // Data related to the underlying digraph
     133    const GR &_graph;
     134    int _node_num;
     135    int _arc_num;
     136
     137    // Parameters of the problem
     138    ValueArcMap *_plower;
     139    ValueArcMap *_pupper;
     140    ValueArcMap *_pcost;
     141    ValueNodeMap *_psupply;
     142    bool _pstsup;
     143    Node _psource, _ptarget;
     144    Value _pstflow;
    132145
    133146    // Result maps
    … …  
    137150    bool _local_potential;
    138151
    139     // The number of nodes and arcs in the original graph
    140     int _node_num;
    141     int _arc_num;
    142 
    143     // Data structures for storing the graph
     152    // Data structures for storing the digraph
    144153    IntNodeMap _node_id;
    145154    ArcVector _arc_ref;
    … …  
    147156    IntVector _target;
    148157
    149     // Node and arc maps
    150     CapacityVector _cap;
    151     CostVector _cost;
    152     CostVector _supply;
    153     CapacityVector _flow;
    154     CostVector _pi;
     158    // Node and arc data
     159    ValueVector _cap;
     160    ValueVector _cost;
     161    ValueVector _supply;
     162    ValueVector _flow;
     163    ValueVector _pi;
    155164
    156165    // Data for storing the spanning tree structure
    … …  
    170179    int first, second, right, last;
    171180    int stem, par_stem, new_stem;
    172     Capacity delta;
     181    Value delta;
    173182
    174183  private:
    175184
    176     /// \brief Implementation of the "First Eligible" pivot rule for the
    177     /// \ref NetworkSimplex "network simplex" algorithm.
    178     ///
    179     /// This class implements the "First Eligible" pivot rule
    180     /// for the \ref NetworkSimplex "network simplex" algorithm.
    181     ///
    182     /// For more information see \ref NetworkSimplex::run().
     185    // Implementation of the First Eligible pivot rule
    183186    class FirstEligiblePivotRule
    184187    {
    … …  
    188191      const IntVector  &_source;
    189192      const IntVector  &_target;
    190       const CostVector &_cost;
     193      const ValueVector &_cost;
    191194      const IntVector  &_state;
    192       const CostVector &_pi;
     195      const ValueVector &_pi;
    193196      int &_in_arc;
    194197      int _arc_num;
    … …  
    199202    public:
    200203
    201       /// Constructor
     204      // Constructor
    202205      FirstEligiblePivotRule(NetworkSimplex &ns) :
    203206        _source(ns._source), _target(ns._target),
    … …  
    206209      {}
    207210
    208       /// Find next entering arc
     211      // Find next entering arc
    209212      bool findEnteringArc() {
    210         Cost c;
     213        Value c;
    211214        for (int e = _next_arc; e < _arc_num; ++e) {
    212215          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    … …  
    231234
    232235
    233     /// \brief Implementation of the "Best Eligible" pivot rule for the
    234     /// \ref NetworkSimplex "network simplex" algorithm.
    235     ///
    236     /// This class implements the "Best Eligible" pivot rule
    237     /// for the \ref NetworkSimplex "network simplex" algorithm.
    238     ///
    239     /// For more information see \ref NetworkSimplex::run().
     236    // Implementation of the Best Eligible pivot rule
    240237    class BestEligiblePivotRule
    241238    {
    … …  
    245242      const IntVector  &_source;
    246243      const IntVector  &_target;
    247       const CostVector &_cost;
     244      const ValueVector &_cost;
    248245      const IntVector  &_state;
    249       const CostVector &_pi;
     246      const ValueVector &_pi;
    250247      int &_in_arc;
    251248      int _arc_num;
    … …  
    253250    public:
    254251
    255       /// Constructor
     252      // Constructor
    256253      BestEligiblePivotRule(NetworkSimplex &ns) :
    257254        _source(ns._source), _target(ns._target),
    … …  
    260257      {}
    261258
    262       /// Find next entering arc
     259      // Find next entering arc
    263260      bool findEnteringArc() {
    264         Cost c, min = 0;
     261        Value c, min = 0;
    265262        for (int e = 0; e < _arc_num; ++e) {
    266263          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    … …  
    276273
    277274
    278     /// \brief Implementation of the "Block Search" pivot rule for the
    279     /// \ref NetworkSimplex "network simplex" algorithm.
    280     ///
    281     /// This class implements the "Block Search" pivot rule
    282     /// for the \ref NetworkSimplex "network simplex" algorithm.
    283     ///
    284     /// For more information see \ref NetworkSimplex::run().
     275    // Implementation of the Block Search pivot rule
    285276    class BlockSearchPivotRule
    286277    {
    … …  
    290281      const IntVector  &_source;
    291282      const IntVector  &_target;
    292       const CostVector &_cost;
     283      const ValueVector &_cost;
    293284      const IntVector  &_state;
    294       const CostVector &_pi;
     285      const ValueVector &_pi;
    295286      int &_in_arc;
    296287      int _arc_num;
    … …  
    302293    public:
    303294
    304       /// Constructor
     295      // Constructor
    305296      BlockSearchPivotRule(NetworkSimplex &ns) :
    306297        _source(ns._source), _target(ns._target),
    … …  
    316307      }
    317308
    318       /// Find next entering arc
     309      // Find next entering arc
    319310      bool findEnteringArc() {
    320         Cost c, min = 0;
     311        Value c, min = 0;
    321312        int cnt = _block_size;
    322313        int e, min_arc = _next_arc;
    … …  
    354345
    355346
    356     /// \brief Implementation of the "Candidate List" pivot rule for the
    357     /// \ref NetworkSimplex "network simplex" algorithm.
    358     ///
    359     /// This class implements the "Candidate List" pivot rule
    360     /// for the \ref NetworkSimplex "network simplex" algorithm.
    361     ///
    362     /// For more information see \ref NetworkSimplex::run().
     347    // Implementation of the Candidate List pivot rule
    363348    class CandidateListPivotRule
    364349    {
    … …  
    368353      const IntVector  &_source;
    369354      const IntVector  &_target;
    370       const CostVector &_cost;
     355      const ValueVector &_cost;
    371356      const IntVector  &_state;
    372       const CostVector &_pi;
     357      const ValueVector &_pi;
    373358      int &_in_arc;
    374359      int _arc_num;
    … …  
    404389      /// Find next entering arc
    405390      bool findEnteringArc() {
    406         Cost min, c;
     391        Value min, c;
    407392        int e, min_arc = _next_arc;
    408393        if (_curr_length > 0 && _minor_count < _minor_limit) {
    … …  
    465450
    466451
    467     /// \brief Implementation of the "Altering Candidate List" pivot rule
    468     /// for the \ref NetworkSimplex "network simplex" algorithm.
    469     ///
    470     /// This class implements the "Altering Candidate List" pivot rule
    471     /// for the \ref NetworkSimplex "network simplex" algorithm.
    472     ///
    473     /// For more information see \ref NetworkSimplex::run().
     452    // Implementation of the Altering Candidate List pivot rule
    474453    class AlteringListPivotRule
    475454    {
    … …  
    479458      const IntVector  &_source;
    480459      const IntVector  &_target;
    481       const CostVector &_cost;
     460      const ValueVector &_cost;
    482461      const IntVector  &_state;
    483       const CostVector &_pi;
     462      const ValueVector &_pi;
    484463      int &_in_arc;
    485464      int _arc_num;
    … …  
    489468      int _next_arc;
    490469      IntVector _candidates;
    491       CostVector _cand_cost;
     470      ValueVector _cand_cost;
    492471
    493472      // Functor class to compare arcs during sort of the candidate list
    … …  
    495474      {
    496475      private:
    497         const CostVector &_map;
     476        const ValueVector &_map;
    498477      public:
    499         SortFunc(const CostVector &map) : _map(map) {}
     478        SortFunc(const ValueVector &map) : _map(map) {}
    500479        bool operator()(int left, int right) {
    501480          return _map[left] > _map[right];
    … …  
    507486    public:
    508487
    509       /// Constructor
     488      // Constructor
    510489      AlteringListPivotRule(NetworkSimplex &ns) :
    511490        _source(ns._source), _target(ns._target),
    … …  
    528507      }
    529508
    530       /// Find next entering arc
     509      // Find next entering arc
    531510      bool findEnteringArc() {
    532511        // Check the current candidate list
    … …  
    593572  public:
    594573
    595     /// \brief General constructor (with lower bounds).
    596     ///
    597     /// General constructor (with lower bounds).
     574    /// \brief Constructor.
     575    ///
     576    /// Constructor.
    598577    ///
    599578    /// \param graph The digraph the algorithm runs on.
    600     /// \param lower The lower bounds of the arcs.
    601     /// \param capacity The capacities (upper bounds) of the arcs.
    602     /// \param cost The cost (length) values of the arcs.
    603     /// \param supply The supply values of the nodes (signed).
    604     NetworkSimplex( const Digraph &graph,
    605                     const LowerMap &lower,
    606                     const CapacityMap &capacity,
    607                     const CostMap &cost,
    608                     const SupplyMap &supply ) :
    609       _graph(graph), _orig_lower(&lower), _orig_cap(capacity),
    610       _orig_cost(cost), _orig_supply(&supply),
     579    NetworkSimplex(const GR& graph) :
     580      _graph(graph),
     581      _plower(NULL), _pupper(NULL), _pcost(NULL),
     582      _psupply(NULL), _pstsup(false),
    611583      _flow_map(NULL), _potential_map(NULL),
    612584      _local_flow(false), _local_potential(false),
    613585      _node_id(graph)
    614     {}
    615 
    616     /// \brief General constructor (without lower bounds).
    617     ///
    618     /// General constructor (without lower bounds).
    619     ///
    620     /// \param graph The digraph the algorithm runs on.
    621     /// \param capacity The capacities (upper bounds) of the arcs.
    622     /// \param cost The cost (length) values of the arcs.
    623     /// \param supply The supply values of the nodes (signed).
    624     NetworkSimplex( const Digraph &graph,
    625                     const CapacityMap &capacity,
    626                     const CostMap &cost,
    627                     const SupplyMap &supply ) :
    628       _graph(graph), _orig_lower(NULL), _orig_cap(capacity),
    629       _orig_cost(cost), _orig_supply(&supply),
    630       _flow_map(NULL), _potential_map(NULL),
    631       _local_flow(false), _local_potential(false),
    632       _node_id(graph)
    633     {}
    634 
    635     /// \brief Simple constructor (with lower bounds).
    636     ///
    637     /// Simple constructor (with lower bounds).
    638     ///
    639     /// \param graph The digraph the algorithm runs on.
    640     /// \param lower The lower bounds of the arcs.
    641     /// \param capacity The capacities (upper bounds) of the arcs.
    642     /// \param cost The cost (length) values of the arcs.
    643     /// \param s The source node.
    644     /// \param t The target node.
    645     /// \param flow_value The required amount of flow from node \c s
    646     /// to node \c t (i.e. the supply of \c s and the demand of \c t).
    647     NetworkSimplex( const Digraph &graph,
    648                     const LowerMap &lower,
    649                     const CapacityMap &capacity,
    650                     const CostMap &cost,
    651                     Node s, Node t,
    652                     Capacity flow_value ) :
    653       _graph(graph), _orig_lower(&lower), _orig_cap(capacity),
    654       _orig_cost(cost), _orig_supply(NULL),
    655       _orig_source(s), _orig_target(t), _orig_flow_value(flow_value),
    656       _flow_map(NULL), _potential_map(NULL),
    657       _local_flow(false), _local_potential(false),
    658       _node_id(graph)
    659     {}
    660 
    661     /// \brief Simple constructor (without lower bounds).
    662     ///
    663     /// Simple constructor (without lower bounds).
    664     ///
    665     /// \param graph The digraph the algorithm runs on.
    666     /// \param capacity The capacities (upper bounds) of the arcs.
    667     /// \param cost The cost (length) values of the arcs.
    668     /// \param s The source node.
    669     /// \param t The target node.
    670     /// \param flow_value The required amount of flow from node \c s
    671     /// to node \c t (i.e. the supply of \c s and the demand of \c t).
    672     NetworkSimplex( const Digraph &graph,
    673                     const CapacityMap &capacity,
    674                     const CostMap &cost,
    675                     Node s, Node t,
    676                     Capacity flow_value ) :
    677       _graph(graph), _orig_lower(NULL), _orig_cap(capacity),
    678       _orig_cost(cost), _orig_supply(NULL),
    679       _orig_source(s), _orig_target(t), _orig_flow_value(flow_value),
    680       _flow_map(NULL), _potential_map(NULL),
    681       _local_flow(false), _local_potential(false),
    682       _node_id(graph)
    683     {}
     586    {
     587      LEMON_ASSERT(std::numeric_limits<Value>::is_integer &&
     588                   std::numeric_limits<Value>::is_signed,
     589        "The value type of NetworkSimplex must be a signed integer");
     590    }
    684591
    685592    /// Destructor.
    … …  
    689596    }
    690597
     598    /// \brief Set the lower bounds on the arcs.
     599    ///
     600    /// This function sets the lower bounds on the arcs.
     601    /// If neither this function nor \ref boundMaps() is used before
     602    /// calling \ref run(), the lower bounds will be set to zero
     603    /// on all arcs.
     604    ///
     605    /// \param map An arc map storing the lower bounds.
     606    /// Its \c Value type must be convertible to the \c Value type
     607    /// of the algorithm.
     608    ///
     609    /// \return <tt>(*this)</tt>
     610    template <typename LOWER>
     611    NetworkSimplex& lowerMap(const LOWER& map) {
     612      delete _plower;
     613      _plower = new ValueArcMap(_graph);
     614      for (ArcIt a(_graph); a != INVALID; ++a) {
     615        (*_plower)[a] = map[a];
     616      }
     617      return *this;
     618    }
     619
     620    /// \brief Set the upper bounds (capacities) on the arcs.
     621    ///
     622    /// This function sets the upper bounds (capacities) on the arcs.
     623    /// If none of the functions \ref upperMap(), \ref capacityMap()
     624    /// and \ref boundMaps() is used before calling \ref run(),
     625    /// the upper bounds (capacities) will be set to
     626    /// \c std::numeric_limits<Value>::max() on all arcs.
     627    ///
     628    /// \param map An arc map storing the upper bounds.
     629    /// Its \c Value type must be convertible to the \c Value type
     630    /// of the algorithm.
     631    ///
     632    /// \return <tt>(*this)</tt>
     633    template<typename UPPER>
     634    NetworkSimplex& upperMap(const UPPER& map) {
     635      delete _pupper;
     636      _pupper = new ValueArcMap(_graph);
     637      for (ArcIt a(_graph); a != INVALID; ++a) {
     638        (*_pupper)[a] = map[a];
     639      }
     640      return *this;
     641    }
     642
     643    /// \brief Set the upper bounds (capacities) on the arcs.
     644    ///
     645    /// This function sets the upper bounds (capacities) on the arcs.
     646    /// It is just an alias for \ref upperMap().
     647    ///
     648    /// \return <tt>(*this)</tt>
     649    template<typename CAP>
     650    NetworkSimplex& capacityMap(const CAP& map) {
     651      return upperMap(map);
     652    }
     653
     654    /// \brief Set the lower and upper bounds on the arcs.
     655    ///
     656    /// This function sets the lower and upper bounds on the arcs.
     657    /// If neither this function nor \ref lowerMap() is used before
     658    /// calling \ref run(), the lower bounds will be set to zero
     659    /// on all arcs.
     660    /// If none of the functions \ref upperMap(), \ref capacityMap()
     661    /// and \ref boundMaps() is used before calling \ref run(),
     662    /// the upper bounds (capacities) will be set to
     663    /// \c std::numeric_limits<Value>::max() on all arcs.
     664    ///
     665    /// \param lower An arc map storing the lower bounds.
     666    /// \param upper An arc map storing the upper bounds.
     667    ///
     668    /// The \c Value type of the maps must be convertible to the
     669    /// \c Value type of the algorithm.
     670    ///
     671    /// \note This function is just a shortcut of calling \ref lowerMap()
     672    /// and \ref upperMap() separately.
     673    ///
     674    /// \return <tt>(*this)</tt>
     675    template <typename LOWER, typename UPPER>
     676    NetworkSimplex& boundMaps(const LOWER& lower, const UPPER& upper) {
     677      return lowerMap(lower).upperMap(upper);
     678    }
     679
     680    /// \brief Set the costs of the arcs.
     681    ///
     682    /// This function sets the costs of the arcs.
     683    /// If it is not used before calling \ref run(), the costs
     684    /// will be set to \c 1 on all arcs.
     685    ///
     686    /// \param map An arc map storing the costs.
     687    /// Its \c Value type must be convertible to the \c Value type
     688    /// of the algorithm.
     689    ///
     690    /// \return <tt>(*this)</tt>
     691    template<typename COST>
     692    NetworkSimplex& costMap(const COST& map) {
     693      delete _pcost;
     694      _pcost = new ValueArcMap(_graph);
     695      for (ArcIt a(_graph); a != INVALID; ++a) {
     696        (*_pcost)[a] = map[a];
     697      }
     698      return *this;
     699    }
     700
     701    /// \brief Set the supply values of the nodes.
     702    ///
     703    /// This function sets the supply values of the nodes.
     704    /// If neither this function nor \ref stSupply() is used before
     705    /// calling \ref run(), the supply of each node will be set to zero.
     706    /// (It makes sense only if non-zero lower bounds are given.)
     707    ///
     708    /// \param map A node map storing the supply values.
     709    /// Its \c Value type must be convertible to the \c Value type
     710    /// of the algorithm.
     711    ///
     712    /// \return <tt>(*this)</tt>
     713    template<typename SUP>
     714    NetworkSimplex& supplyMap(const SUP& map) {
     715      delete _psupply;
     716      _pstsup = false;
     717      _psupply = new ValueNodeMap(_graph);
     718      for (NodeIt n(_graph); n != INVALID; ++n) {
     719        (*_psupply)[n] = map[n];
     720      }
     721      return *this;
     722    }
     723
     724    /// \brief Set single source and target nodes and a supply value.
     725    ///
     726    /// This function sets a single source node and a single target node
     727    /// and the required flow value.
     728    /// If neither this function nor \ref supplyMap() is used before
     729    /// calling \ref run(), the supply of each node will be set to zero.
     730    /// (It makes sense only if non-zero lower bounds are given.)
     731    ///
     732    /// \param s The source node.
     733    /// \param t The target node.
     734    /// \param k The required amount of flow from node \c s to node \c t
     735    /// (i.e. the supply of \c s and the demand of \c t).
     736    ///
     737    /// \return <tt>(*this)</tt>
     738    NetworkSimplex& stSupply(const Node& s, const Node& t, Value k) {
     739      delete _psupply;
     740      _psupply = NULL;
     741      _pstsup = true;
     742      _psource = s;
     743      _ptarget = t;
     744      _pstflow = k;
     745      return *this;
     746    }
     747
    691748    /// \brief Set the flow map.
    692749    ///
    693750    /// This function sets the flow map.
     751    /// If it is not used before calling \ref run(), an instance will
     752    /// be allocated automatically. The destructor deallocates this
     753    /// automatically allocated map, of course.
    694754    ///
    695755    /// \return <tt>(*this)</tt>
    696     NetworkSimplex& flowMap(FlowMap &map) {
     756    NetworkSimplex& flowMap(FlowMap& map) {
    697757      if (_local_flow) {
    698758        delete _flow_map;
    … …  
    705765    /// \brief Set the potential map.
    706766    ///
    707     /// This function sets the potential map.
     767    /// This function sets the potential map, which is used for storing
     768    /// the dual solution.
     769    /// If it is not used before calling \ref run(), an instance will
     770    /// be allocated automatically. The destructor deallocates this
     771    /// automatically allocated map, of course.
    708772    ///
    709773    /// \return <tt>(*this)</tt>
    710     NetworkSimplex& potentialMap(PotentialMap &map) {
     774    NetworkSimplex& potentialMap(PotentialMap& map) {
    711775      if (_local_potential) {
    712776        delete _potential_map;
    … …  
    717781    }
    718782
    719     /// \name Execution control
    720     /// The algorithm can be executed using the
    721     /// \ref lemon::NetworkSimplex::run() "run()" function.
     783    /// \name Execution Control
     784    /// The algorithm can be executed using \ref run().
     785
    722786    /// @{
    723787
    … …  
    725789    ///
    726790    /// This function runs the algorithm.
    727     ///
    728     /// \param pivot_rule The pivot rule that is used during the
    729     /// algorithm.
    730     ///
    731     /// The available pivot rules:
    732     ///
    733     /// - FIRST_ELIGIBLE_PIVOT The next eligible arc is selected in
    734     /// a wraparound fashion in every iteration
    735     /// (\ref FirstEligiblePivotRule).
    736     ///
    737     /// - BEST_ELIGIBLE_PIVOT The best eligible arc is selected in
    738     /// every iteration (\ref BestEligiblePivotRule).
    739     ///
    740     /// - BLOCK_SEARCH_PIVOT A specified number of arcs are examined in
    741     /// every iteration in a wraparound fashion and the best eligible
    742     /// arc is selected from this block (\ref BlockSearchPivotRule).
    743     ///
    744     /// - CANDIDATE_LIST_PIVOT In a major iteration a candidate list is
    745     /// built from eligible arcs in a wraparound fashion and in the
    746     /// following minor iterations the best eligible arc is selected
    747     /// from this list (\ref CandidateListPivotRule).
    748     ///
    749     /// - ALTERING_LIST_PIVOT It is a modified version of the
    750     /// "Candidate List" pivot rule. It keeps only the several best
    751     /// eligible arcs from the former candidate list and extends this
    752     /// list in every iteration (\ref AlteringListPivotRule).
    753     ///
    754     /// According to our comprehensive benchmark tests the "Block Search"
    755     /// pivot rule proved to be the fastest and the most robust on
    756     /// various test inputs. Thus it is the default option.
     791    /// The paramters can be specified using \ref lowerMap(),
     792    /// \ref upperMap(), \ref capacityMap(), \ref boundMaps(),
     793    /// \ref costMap(), \ref supplyMap() and \ref stSupply()
     794    /// functions. For example,
     795    /// \code
     796    ///   NetworkSimplex<ListDigraph> ns(graph);
     797    ///   ns.boundMaps(lower, upper).costMap(cost)
     798    ///     .supplyMap(sup).run();
     799    /// \endcode
     800    ///
     801    /// \param pivot_rule The pivot rule that will be used during the
     802    /// algorithm. For more information see \ref PivotRule.
    757803    ///
    758804    /// \return \c true if a feasible flow can be found.
    759     bool run(PivotRuleEnum pivot_rule = BLOCK_SEARCH_PIVOT) {
     805    bool run(PivotRule pivot_rule = BLOCK_SEARCH) {
    760806      return init() && start(pivot_rule);
    761807    }
    … …  
    766812    /// The results of the algorithm can be obtained using these
    767813    /// functions.\n
    768     /// \ref lemon::NetworkSimplex::run() "run()" must be called before
    769     /// using them.
     814    /// The \ref run() function must be called before using them.
     815
    770816    /// @{
     817
     818    /// \brief Return the total cost of the found flow.
     819    ///
     820    /// This function returns the total cost of the found flow.
     821    /// The complexity of the function is \f$ O(e) \f$.
     822    ///
     823    /// \note The return type of the function can be specified as a
     824    /// template parameter. For example,
     825    /// \code
     826    ///   ns.totalCost<double>();
     827    /// \endcode
     828    /// It is useful if the total cost cannot be stored in the \c Value
     829    /// type of the algorithm, which is the default return type of the
     830    /// function.
     831    ///
     832    /// \pre \ref run() must be called before using this function.
     833    template <typename Num>
     834    Num totalCost() const {
     835      Num c = 0;
     836      if (_pcost) {
     837        for (ArcIt e(_graph); e != INVALID; ++e)
     838          c += (*_flow_map)[e] * (*_pcost)[e];
     839      } else {
     840        for (ArcIt e(_graph); e != INVALID; ++e)
     841          c += (*_flow_map)[e];
     842      }
     843      return c;
     844    }
     845
     846#ifndef DOXYGEN
     847    Value totalCost() const {
     848      return totalCost<Value>();
     849    }
     850#endif
     851
     852    /// \brief Return the flow on the given arc.
     853    ///
     854    /// This function returns the flow on the given arc.
     855    ///
     856    /// \pre \ref run() must be called before using this function.
     857    Value flow(const Arc& a) const {
     858      return (*_flow_map)[a];
     859    }
    771860
    772861    /// \brief Return a const reference to the flow map.
    … …  
    780869    }
    781870
     871    /// \brief Return the potential (dual value) of the given node.
     872    ///
     873    /// This function returns the potential (dual value) of the
     874    /// given node.
     875    ///
     876    /// \pre \ref run() must be called before using this function.
     877    Value potential(const Node& n) const {
     878      return (*_potential_map)[n];
     879    }
     880
    782881    /// \brief Return a const reference to the potential map
    783882    /// (the dual solution).
    784883    ///
    785884    /// This function returns a const reference to a node map storing
    786     /// the found potentials (the dual solution).
     885    /// the found potentials, which form the dual solution of the
     886    /// \ref min_cost_flow "minimum cost flow" problem.
    787887    ///
    788888    /// \pre \ref run() must be called before using this function.
    789889    const PotentialMap& potentialMap() const {
    790890      return *_potential_map;
    791     }
    792 
    793     /// \brief Return the flow on the given arc.
    794     ///
    795     /// This function returns the flow on the given arc.
    796     ///
    797     /// \pre \ref run() must be called before using this function.
    798     Capacity flow(const Arc& arc) const {
    799       return (*_flow_map)[arc];
    800     }
    801 
    802     /// \brief Return the potential of the given node.
    803     ///
    804     /// This function returns the potential of the given node.
    805     ///
    806     /// \pre \ref run() must be called before using this function.
    807     Cost potential(const Node& node) const {
    808       return (*_potential_map)[node];
    809     }
    810 
    811     /// \brief Return the total cost of the found flow.
    812     ///
    813     /// This function returns the total cost of the found flow.
    814     /// The complexity of the function is \f$ O(e) \f$.
    815     ///
    816     /// \pre \ref run() must be called before using this function.
    817     Cost totalCost() const {
    818       Cost c = 0;
    819       for (ArcIt e(_graph); e != INVALID; ++e)
    820         c += (*_flow_map)[e] * _orig_cost[e];
    821       return c;
    822891    }
    823892
    … …  
    843912      int all_node_num = _node_num + 1;
    844913      int all_arc_num = _arc_num + _node_num;
     914      if (_node_num == 0) return false;
    845915
    846916      _arc_ref.resize(_arc_num);
    … …  
    865935      // Initialize node related data
    866936      bool valid_supply = true;
    867       if (_orig_supply) {
    868         Supply sum = 0;
     937      if (!_pstsup && !_psupply) {
     938        _pstsup = true;
     939        _psource = _ptarget = NodeIt(_graph);
     940        _pstflow = 0;
     941      }
     942      if (_psupply) {
     943        Value sum = 0;
    869944        int i = 0;
    870945        for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
    871946          _node_id[n] = i;
    872           _supply[i] = (*_orig_supply)[n];
     947          _supply[i] = (*_psupply)[n];
    873948          sum += _supply[i];
    874949        }
    … …  
    880955          _supply[i] = 0;
    881956        }
    882         _supply[_node_id[_orig_source]] =  _orig_flow_value;
    883         _supply[_node_id[_orig_target]] = -_orig_flow_value;
     957        _supply[_node_id[_psource]] =  _pstflow;
     958        _supply[_node_id[_ptarget]]   = -_pstflow;
    884959      }
    885960      if (!valid_supply) return false;
    … …  
    905980
    906981      // Initialize arc maps
    907       for (int i = 0; i != _arc_num; ++i) {
    908         Arc e = _arc_ref[i];
    909         _source[i] = _node_id[_graph.source(e)];
    910         _target[i] = _node_id[_graph.target(e)];
    911         _cost[i] = _orig_cost[e];
    912         _cap[i] = _orig_cap[e];
     982      if (_pupper && _pcost) {
     983        for (int i = 0; i != _arc_num; ++i) {
     984          Arc e = _arc_ref[i];
     985          _source[i] = _node_id[_graph.source(e)];
     986          _target[i] = _node_id[_graph.target(e)];
     987          _cap[i] = (*_pupper)[e];
     988          _cost[i] = (*_pcost)[e];
     989        }
     990      } else {
     991        for (int i = 0; i != _arc_num; ++i) {
     992          Arc e = _arc_ref[i];
     993          _source[i] = _node_id[_graph.source(e)];
     994          _target[i] = _node_id[_graph.target(e)];
     995        }
     996        if (_pupper) {
     997          for (int i = 0; i != _arc_num; ++i)
     998            _cap[i] = (*_pupper)[_arc_ref[i]];
     999        } else {
     1000          Value val = std::numeric_limits<Value>::max();
     1001          for (int i = 0; i != _arc_num; ++i)
     1002            _cap[i] = val;
     1003        }
     1004        if (_pcost) {
     1005          for (int i = 0; i != _arc_num; ++i)
     1006            _cost[i] = (*_pcost)[_arc_ref[i]];
     1007        } else {
     1008          for (int i = 0; i != _arc_num; ++i)
     1009            _cost[i] = 1;
     1010        }
    9131011      }
    9141012
    9151013      // Remove non-zero lower bounds
    916       if (_orig_lower) {
     1014      if (_plower) {
    9171015        for (int i = 0; i != _arc_num; ++i) {
    918           Capacity c = (*_orig_lower)[_arc_ref[i]];
     1016          Value c = (*_plower)[_arc_ref[i]];
    9191017          if (c != 0) {
    9201018            _cap[i] -= c;
    … …  
    9261024
    9271025      // Add artificial arcs and initialize the spanning tree data structure
    928       Cost max_cost = std::numeric_limits<Cost>::max() / 4;
    929       Capacity max_cap = std::numeric_limits<Capacity>::max();
     1026      Value max_cap = std::numeric_limits<Value>::max();
     1027      Value max_cost = std::numeric_limits<Value>::max() / 4;
    9301028      for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
    9311029        _thread[u] = u + 1;
    … …  
    9801078      delta = _cap[in_arc];
    9811079      int result = 0;
    982       Capacity d;
     1080      Value d;
    9831081      int e;
    9841082
    … …  
    10181116      // Augment along the cycle
    10191117      if (delta > 0) {
    1020         Capacity val = _state[in_arc] * delta;
     1118        Value val = _state[in_arc] * delta;
    10211119        _flow[in_arc] += val;
    10221120        for (int u = _source[in_arc]; u != join; u = _parent[u]) {
    … …  
    11591257    // Update potentials
    11601258    void updatePotential() {
    1161       Cost sigma = _forward[u_in] ?
     1259      Value sigma = _forward[u_in] ?
    11621260        _pi[v_in] - _pi[u_in] - _cost[_pred[u_in]] :
    11631261        _pi[v_in] - _pi[u_in] + _cost[_pred[u_in]];
    … …  
    11821280
    11831281    // Execute the algorithm
    1184     bool start(PivotRuleEnum pivot_rule) {
     1282    bool start(PivotRule pivot_rule) {
    11851283      // Select the pivot rule implementation
    11861284      switch (pivot_rule) {
    1187         case FIRST_ELIGIBLE_PIVOT:
     1285        case FIRST_ELIGIBLE:
    11881286          return start<FirstEligiblePivotRule>();
    1189         case BEST_ELIGIBLE_PIVOT:
     1287        case BEST_ELIGIBLE:
    11901288          return start<BestEligiblePivotRule>();
    1191         case BLOCK_SEARCH_PIVOT:
     1289        case BLOCK_SEARCH:
    11921290          return start<BlockSearchPivotRule>();
    1193         case CANDIDATE_LIST_PIVOT:
     1291        case CANDIDATE_LIST:
    11941292          return start<CandidateListPivotRule>();
    1195         case ALTERING_LIST_PIVOT:
     1293        case ALTERING_LIST:
    11961294          return start<AlteringListPivotRule>();
    11971295      }
    … …  
    11991297    }
    12001298
    1201     template<class PivotRuleImplementation>
     1299    template <typename PivotRuleImpl>
    12021300    bool start() {
    1203       PivotRuleImplementation pivot(*this);
    1204 
    1205       // Execute the network simplex algorithm
     1301      PivotRuleImpl pivot(*this);
     1302
     1303      // Execute the Network Simplex algorithm
    12061304      while (pivot.findEnteringArc()) {
    12071305        findJoinNode();
    … …  
    12201318
    12211319      // Copy flow values to _flow_map
    1222       if (_orig_lower) {
     1320      if (_plower) {
    12231321        for (int i = 0; i != _arc_num; ++i) {
    12241322          Arc e = _arc_ref[i];
    1225           _flow_map->set(e, (*_orig_lower)[e] + _flow[i]);
     1323          _flow_map->set(e, (*_plower)[e] + _flow[i]);
    12261324        }
    12271325      } else {

  • 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;

  • tools/dimacs-solver.cc

    r602 r605  
    106106  if (report) std::cerr << "Read the file: " << ti << '\n';
    107107  ti.restart();
    108   NetworkSimplex< Digraph, Digraph::ArcMap<Value>, Digraph::ArcMap<Value>,
    109                   Digraph::ArcMap<Value>, Digraph::NodeMap<Value> >
    110     ns(g, lower, cap, cost, sup);
     108  NetworkSimplex<Digraph, Value> ns(g);
     109  ns.lowerMap(lower).capacityMap(cap).costMap(cost).supplyMap(sup);
    111110  if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n';
    112111  ti.restart();
Note: See TracChangeset for help on using the changeset viewer.