COIN-OR::LEMON - Graph Library

Changeset 605:5232721b3f14 in lemon-1.2 for lemon


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

Rework the interface of NetworkSimplex? (#234)

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

File:
1 edited

Legend:

Unmodified
Added
Removed
  • 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 {
Note: See TracChangeset for help on using the changeset viewer.