Separate types for flow and cost values in NetworkSimplex (#234)
authorPeter Kovacs <kpeter@inf.elte.hu>
Fri, 03 Apr 2009 13:46:16 +0200
changeset 5999ad8d2122b50
parent 598 c7d160f73d52
child 600 6ac5d9ae1d3d
Separate types for flow and cost values in NetworkSimplex (#234)
lemon/network_simplex.h
test/min_cost_flow_test.cc
     1.1 --- a/lemon/network_simplex.h	Wed Mar 25 21:37:50 2009 +0100
     1.2 +++ b/lemon/network_simplex.h	Fri Apr 03 13:46:16 2009 +0200
     1.3 @@ -49,24 +49,28 @@
     1.4    /// in LEMON for the minimum cost flow problem.
     1.5    ///
     1.6    /// \tparam GR The digraph type the algorithm runs on.
     1.7 -  /// \tparam V The value type used in the algorithm.
     1.8 -  /// By default it is \c int.
     1.9 +  /// \tparam F The value type used for flow amounts, capacity bounds
    1.10 +  /// and supply values in the algorithm. By default it is \c int.
    1.11 +  /// \tparam C The value type used for costs and potentials in the
    1.12 +  /// algorithm. By default it is the same as \c F.
    1.13    ///
    1.14 -  /// \warning The value type must be a signed integer type.
    1.15 +  /// \warning Both value types must be signed integer types.
    1.16    ///
    1.17    /// \note %NetworkSimplex provides five different pivot rule
    1.18    /// implementations. For more information see \ref PivotRule.
    1.19 -  template <typename GR, typename V = int>
    1.20 +  template <typename GR, typename F = int, typename C = F>
    1.21    class NetworkSimplex
    1.22    {
    1.23    public:
    1.24  
    1.25 -    /// The value type of the algorithm
    1.26 -    typedef V Value;
    1.27 +    /// The flow type of the algorithm
    1.28 +    typedef F Flow;
    1.29 +    /// The cost type of the algorithm
    1.30 +    typedef C Cost;
    1.31      /// The type of the flow map
    1.32 -    typedef typename GR::template ArcMap<Value> FlowMap;
    1.33 +    typedef typename GR::template ArcMap<Flow> FlowMap;
    1.34      /// The type of the potential map
    1.35 -    typedef typename GR::template NodeMap<Value> PotentialMap;
    1.36 +    typedef typename GR::template NodeMap<Cost> PotentialMap;
    1.37  
    1.38    public:
    1.39  
    1.40 @@ -117,14 +121,16 @@
    1.41  
    1.42      TEMPLATE_DIGRAPH_TYPEDEFS(GR);
    1.43  
    1.44 -    typedef typename GR::template ArcMap<Value> ValueArcMap;
    1.45 -    typedef typename GR::template NodeMap<Value> ValueNodeMap;
    1.46 +    typedef typename GR::template ArcMap<Flow> FlowArcMap;
    1.47 +    typedef typename GR::template ArcMap<Cost> CostArcMap;
    1.48 +    typedef typename GR::template NodeMap<Flow> FlowNodeMap;
    1.49  
    1.50      typedef std::vector<Arc> ArcVector;
    1.51      typedef std::vector<Node> NodeVector;
    1.52      typedef std::vector<int> IntVector;
    1.53      typedef std::vector<bool> BoolVector;
    1.54 -    typedef std::vector<Value> ValueVector;
    1.55 +    typedef std::vector<Flow> FlowVector;
    1.56 +    typedef std::vector<Cost> CostVector;
    1.57  
    1.58      // State constants for arcs
    1.59      enum ArcStateEnum {
    1.60 @@ -141,13 +147,13 @@
    1.61      int _arc_num;
    1.62  
    1.63      // Parameters of the problem
    1.64 -    ValueArcMap *_plower;
    1.65 -    ValueArcMap *_pupper;
    1.66 -    ValueArcMap *_pcost;
    1.67 -    ValueNodeMap *_psupply;
    1.68 +    FlowArcMap *_plower;
    1.69 +    FlowArcMap *_pupper;
    1.70 +    CostArcMap *_pcost;
    1.71 +    FlowNodeMap *_psupply;
    1.72      bool _pstsup;
    1.73      Node _psource, _ptarget;
    1.74 -    Value _pstflow;
    1.75 +    Flow _pstflow;
    1.76  
    1.77      // Result maps
    1.78      FlowMap *_flow_map;
    1.79 @@ -162,11 +168,11 @@
    1.80      IntVector _target;
    1.81  
    1.82      // Node and arc data
    1.83 -    ValueVector _cap;
    1.84 -    ValueVector _cost;
    1.85 -    ValueVector _supply;
    1.86 -    ValueVector _flow;
    1.87 -    ValueVector _pi;
    1.88 +    FlowVector _cap;
    1.89 +    CostVector _cost;
    1.90 +    FlowVector _supply;
    1.91 +    FlowVector _flow;
    1.92 +    CostVector _pi;
    1.93  
    1.94      // Data for storing the spanning tree structure
    1.95      IntVector _parent;
    1.96 @@ -184,7 +190,7 @@
    1.97      int in_arc, join, u_in, v_in, u_out, v_out;
    1.98      int first, second, right, last;
    1.99      int stem, par_stem, new_stem;
   1.100 -    Value delta;
   1.101 +    Flow delta;
   1.102  
   1.103    private:
   1.104  
   1.105 @@ -196,9 +202,9 @@
   1.106        // References to the NetworkSimplex class
   1.107        const IntVector  &_source;
   1.108        const IntVector  &_target;
   1.109 -      const ValueVector &_cost;
   1.110 +      const CostVector &_cost;
   1.111        const IntVector  &_state;
   1.112 -      const ValueVector &_pi;
   1.113 +      const CostVector &_pi;
   1.114        int &_in_arc;
   1.115        int _arc_num;
   1.116  
   1.117 @@ -216,7 +222,7 @@
   1.118  
   1.119        // Find next entering arc
   1.120        bool findEnteringArc() {
   1.121 -        Value c;
   1.122 +        Cost c;
   1.123          for (int e = _next_arc; e < _arc_num; ++e) {
   1.124            c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
   1.125            if (c < 0) {
   1.126 @@ -247,9 +253,9 @@
   1.127        // References to the NetworkSimplex class
   1.128        const IntVector  &_source;
   1.129        const IntVector  &_target;
   1.130 -      const ValueVector &_cost;
   1.131 +      const CostVector &_cost;
   1.132        const IntVector  &_state;
   1.133 -      const ValueVector &_pi;
   1.134 +      const CostVector &_pi;
   1.135        int &_in_arc;
   1.136        int _arc_num;
   1.137  
   1.138 @@ -264,7 +270,7 @@
   1.139  
   1.140        // Find next entering arc
   1.141        bool findEnteringArc() {
   1.142 -        Value c, min = 0;
   1.143 +        Cost c, min = 0;
   1.144          for (int e = 0; e < _arc_num; ++e) {
   1.145            c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
   1.146            if (c < min) {
   1.147 @@ -286,9 +292,9 @@
   1.148        // References to the NetworkSimplex class
   1.149        const IntVector  &_source;
   1.150        const IntVector  &_target;
   1.151 -      const ValueVector &_cost;
   1.152 +      const CostVector &_cost;
   1.153        const IntVector  &_state;
   1.154 -      const ValueVector &_pi;
   1.155 +      const CostVector &_pi;
   1.156        int &_in_arc;
   1.157        int _arc_num;
   1.158  
   1.159 @@ -314,7 +320,7 @@
   1.160  
   1.161        // Find next entering arc
   1.162        bool findEnteringArc() {
   1.163 -        Value c, min = 0;
   1.164 +        Cost c, min = 0;
   1.165          int cnt = _block_size;
   1.166          int e, min_arc = _next_arc;
   1.167          for (e = _next_arc; e < _arc_num; ++e) {
   1.168 @@ -358,9 +364,9 @@
   1.169        // References to the NetworkSimplex class
   1.170        const IntVector  &_source;
   1.171        const IntVector  &_target;
   1.172 -      const ValueVector &_cost;
   1.173 +      const CostVector &_cost;
   1.174        const IntVector  &_state;
   1.175 -      const ValueVector &_pi;
   1.176 +      const CostVector &_pi;
   1.177        int &_in_arc;
   1.178        int _arc_num;
   1.179  
   1.180 @@ -394,7 +400,7 @@
   1.181  
   1.182        /// Find next entering arc
   1.183        bool findEnteringArc() {
   1.184 -        Value min, c;
   1.185 +        Cost min, c;
   1.186          int e, min_arc = _next_arc;
   1.187          if (_curr_length > 0 && _minor_count < _minor_limit) {
   1.188            // Minor iteration: select the best eligible arc from the
   1.189 @@ -463,9 +469,9 @@
   1.190        // References to the NetworkSimplex class
   1.191        const IntVector  &_source;
   1.192        const IntVector  &_target;
   1.193 -      const ValueVector &_cost;
   1.194 +      const CostVector &_cost;
   1.195        const IntVector  &_state;
   1.196 -      const ValueVector &_pi;
   1.197 +      const CostVector &_pi;
   1.198        int &_in_arc;
   1.199        int _arc_num;
   1.200  
   1.201 @@ -473,15 +479,15 @@
   1.202        int _block_size, _head_length, _curr_length;
   1.203        int _next_arc;
   1.204        IntVector _candidates;
   1.205 -      ValueVector _cand_cost;
   1.206 +      CostVector _cand_cost;
   1.207  
   1.208        // Functor class to compare arcs during sort of the candidate list
   1.209        class SortFunc
   1.210        {
   1.211        private:
   1.212 -        const ValueVector &_map;
   1.213 +        const CostVector &_map;
   1.214        public:
   1.215 -        SortFunc(const ValueVector &map) : _map(map) {}
   1.216 +        SortFunc(const CostVector &map) : _map(map) {}
   1.217          bool operator()(int left, int right) {
   1.218            return _map[left] > _map[right];
   1.219          }
   1.220 @@ -590,9 +596,12 @@
   1.221        _local_flow(false), _local_potential(false),
   1.222        _node_id(graph)
   1.223      {
   1.224 -      LEMON_ASSERT(std::numeric_limits<Value>::is_integer &&
   1.225 -                   std::numeric_limits<Value>::is_signed,
   1.226 -        "The value type of NetworkSimplex must be a signed integer");
   1.227 +      LEMON_ASSERT(std::numeric_limits<Flow>::is_integer &&
   1.228 +                   std::numeric_limits<Flow>::is_signed,
   1.229 +        "The flow type of NetworkSimplex must be signed integer");
   1.230 +      LEMON_ASSERT(std::numeric_limits<Cost>::is_integer &&
   1.231 +                   std::numeric_limits<Cost>::is_signed,
   1.232 +        "The cost type of NetworkSimplex must be signed integer");
   1.233      }
   1.234  
   1.235      /// Destructor.
   1.236 @@ -609,14 +618,14 @@
   1.237      /// on all arcs.
   1.238      ///
   1.239      /// \param map An arc map storing the lower bounds.
   1.240 -    /// Its \c Value type must be convertible to the \c Value type
   1.241 +    /// Its \c Value type must be convertible to the \c Flow type
   1.242      /// of the algorithm.
   1.243      ///
   1.244      /// \return <tt>(*this)</tt>
   1.245      template <typename LOWER>
   1.246      NetworkSimplex& lowerMap(const LOWER& map) {
   1.247        delete _plower;
   1.248 -      _plower = new ValueArcMap(_graph);
   1.249 +      _plower = new FlowArcMap(_graph);
   1.250        for (ArcIt a(_graph); a != INVALID; ++a) {
   1.251          (*_plower)[a] = map[a];
   1.252        }
   1.253 @@ -629,17 +638,17 @@
   1.254      /// If none of the functions \ref upperMap(), \ref capacityMap()
   1.255      /// and \ref boundMaps() is used before calling \ref run(),
   1.256      /// the upper bounds (capacities) will be set to
   1.257 -    /// \c std::numeric_limits<Value>::max() on all arcs.
   1.258 +    /// \c std::numeric_limits<Flow>::max() on all arcs.
   1.259      ///
   1.260      /// \param map An arc map storing the upper bounds.
   1.261 -    /// Its \c Value type must be convertible to the \c Value type
   1.262 +    /// Its \c Value type must be convertible to the \c Flow type
   1.263      /// of the algorithm.
   1.264      ///
   1.265      /// \return <tt>(*this)</tt>
   1.266      template<typename UPPER>
   1.267      NetworkSimplex& upperMap(const UPPER& map) {
   1.268        delete _pupper;
   1.269 -      _pupper = new ValueArcMap(_graph);
   1.270 +      _pupper = new FlowArcMap(_graph);
   1.271        for (ArcIt a(_graph); a != INVALID; ++a) {
   1.272          (*_pupper)[a] = map[a];
   1.273        }
   1.274 @@ -666,13 +675,13 @@
   1.275      /// If none of the functions \ref upperMap(), \ref capacityMap()
   1.276      /// and \ref boundMaps() is used before calling \ref run(),
   1.277      /// the upper bounds (capacities) will be set to
   1.278 -    /// \c std::numeric_limits<Value>::max() on all arcs.
   1.279 +    /// \c std::numeric_limits<Flow>::max() on all arcs.
   1.280      ///
   1.281      /// \param lower An arc map storing the lower bounds.
   1.282      /// \param upper An arc map storing the upper bounds.
   1.283      ///
   1.284      /// The \c Value type of the maps must be convertible to the
   1.285 -    /// \c Value type of the algorithm.
   1.286 +    /// \c Flow type of the algorithm.
   1.287      ///
   1.288      /// \note This function is just a shortcut of calling \ref lowerMap()
   1.289      /// and \ref upperMap() separately.
   1.290 @@ -690,14 +699,14 @@
   1.291      /// will be set to \c 1 on all arcs.
   1.292      ///
   1.293      /// \param map An arc map storing the costs.
   1.294 -    /// Its \c Value type must be convertible to the \c Value type
   1.295 +    /// Its \c Value type must be convertible to the \c Cost type
   1.296      /// of the algorithm.
   1.297      ///
   1.298      /// \return <tt>(*this)</tt>
   1.299      template<typename COST>
   1.300      NetworkSimplex& costMap(const COST& map) {
   1.301        delete _pcost;
   1.302 -      _pcost = new ValueArcMap(_graph);
   1.303 +      _pcost = new CostArcMap(_graph);
   1.304        for (ArcIt a(_graph); a != INVALID; ++a) {
   1.305          (*_pcost)[a] = map[a];
   1.306        }
   1.307 @@ -712,7 +721,7 @@
   1.308      /// (It makes sense only if non-zero lower bounds are given.)
   1.309      ///
   1.310      /// \param map A node map storing the supply values.
   1.311 -    /// Its \c Value type must be convertible to the \c Value type
   1.312 +    /// Its \c Value type must be convertible to the \c Flow type
   1.313      /// of the algorithm.
   1.314      ///
   1.315      /// \return <tt>(*this)</tt>
   1.316 @@ -720,7 +729,7 @@
   1.317      NetworkSimplex& supplyMap(const SUP& map) {
   1.318        delete _psupply;
   1.319        _pstsup = false;
   1.320 -      _psupply = new ValueNodeMap(_graph);
   1.321 +      _psupply = new FlowNodeMap(_graph);
   1.322        for (NodeIt n(_graph); n != INVALID; ++n) {
   1.323          (*_psupply)[n] = map[n];
   1.324        }
   1.325 @@ -741,7 +750,7 @@
   1.326      /// (i.e. the supply of \c s and the demand of \c t).
   1.327      ///
   1.328      /// \return <tt>(*this)</tt>
   1.329 -    NetworkSimplex& stSupply(const Node& s, const Node& t, Value k) {
   1.330 +    NetworkSimplex& stSupply(const Node& s, const Node& t, Flow k) {
   1.331        delete _psupply;
   1.332        _psupply = NULL;
   1.333        _pstsup = true;
   1.334 @@ -874,14 +883,14 @@
   1.335      /// \brief Return the total cost of the found flow.
   1.336      ///
   1.337      /// This function returns the total cost of the found flow.
   1.338 -    /// The complexity of the function is \f$ O(e) \f$.
   1.339 +    /// The complexity of the function is O(e).
   1.340      ///
   1.341      /// \note The return type of the function can be specified as a
   1.342      /// template parameter. For example,
   1.343      /// \code
   1.344      ///   ns.totalCost<double>();
   1.345      /// \endcode
   1.346 -    /// It is useful if the total cost cannot be stored in the \c Value
   1.347 +    /// It is useful if the total cost cannot be stored in the \c Cost
   1.348      /// type of the algorithm, which is the default return type of the
   1.349      /// function.
   1.350      ///
   1.351 @@ -900,8 +909,8 @@
   1.352      }
   1.353  
   1.354  #ifndef DOXYGEN
   1.355 -    Value totalCost() const {
   1.356 -      return totalCost<Value>();
   1.357 +    Cost totalCost() const {
   1.358 +      return totalCost<Cost>();
   1.359      }
   1.360  #endif
   1.361  
   1.362 @@ -910,7 +919,7 @@
   1.363      /// This function returns the flow on the given arc.
   1.364      ///
   1.365      /// \pre \ref run() must be called before using this function.
   1.366 -    Value flow(const Arc& a) const {
   1.367 +    Flow flow(const Arc& a) const {
   1.368        return (*_flow_map)[a];
   1.369      }
   1.370  
   1.371 @@ -930,7 +939,7 @@
   1.372      /// given node.
   1.373      ///
   1.374      /// \pre \ref run() must be called before using this function.
   1.375 -    Value potential(const Node& n) const {
   1.376 +    Cost potential(const Node& n) const {
   1.377        return (*_potential_map)[n];
   1.378      }
   1.379  
   1.380 @@ -996,7 +1005,7 @@
   1.381          _pstflow = 0;
   1.382        }
   1.383        if (_psupply) {
   1.384 -        Value sum = 0;
   1.385 +        Flow sum = 0;
   1.386          int i = 0;
   1.387          for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
   1.388            _node_id[n] = i;
   1.389 @@ -1035,6 +1044,8 @@
   1.390        }
   1.391  
   1.392        // Initialize arc maps
   1.393 +      Flow max_cap = std::numeric_limits<Flow>::max();
   1.394 +      Cost max_cost = std::numeric_limits<Cost>::max() / 4;
   1.395        if (_pupper && _pcost) {
   1.396          for (int i = 0; i != _arc_num; ++i) {
   1.397            Arc e = _arc_ref[i];
   1.398 @@ -1057,9 +1068,8 @@
   1.399            for (int i = 0; i != _arc_num; ++i)
   1.400              _cap[i] = (*_pupper)[_arc_ref[i]];
   1.401          } else {
   1.402 -          Value val = std::numeric_limits<Value>::max();
   1.403            for (int i = 0; i != _arc_num; ++i)
   1.404 -            _cap[i] = val;
   1.405 +            _cap[i] = max_cap;
   1.406          }
   1.407          if (_pcost) {
   1.408            for (int i = 0; i != _arc_num; ++i)
   1.409 @@ -1073,7 +1083,7 @@
   1.410        // Remove non-zero lower bounds
   1.411        if (_plower) {
   1.412          for (int i = 0; i != _arc_num; ++i) {
   1.413 -          Value c = (*_plower)[_arc_ref[i]];
   1.414 +          Flow c = (*_plower)[_arc_ref[i]];
   1.415            if (c != 0) {
   1.416              _cap[i] -= c;
   1.417              _supply[_source[i]] -= c;
   1.418 @@ -1083,8 +1093,6 @@
   1.419        }
   1.420  
   1.421        // Add artificial arcs and initialize the spanning tree data structure
   1.422 -      Value max_cap = std::numeric_limits<Value>::max();
   1.423 -      Value max_cost = std::numeric_limits<Value>::max() / 4;
   1.424        for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
   1.425          _thread[u] = u + 1;
   1.426          _rev_thread[u + 1] = u;
   1.427 @@ -1137,7 +1145,7 @@
   1.428        }
   1.429        delta = _cap[in_arc];
   1.430        int result = 0;
   1.431 -      Value d;
   1.432 +      Flow d;
   1.433        int e;
   1.434  
   1.435        // Search the cycle along the path form the first node to the root
   1.436 @@ -1175,7 +1183,7 @@
   1.437      void changeFlow(bool change) {
   1.438        // Augment along the cycle
   1.439        if (delta > 0) {
   1.440 -        Value val = _state[in_arc] * delta;
   1.441 +        Flow val = _state[in_arc] * delta;
   1.442          _flow[in_arc] += val;
   1.443          for (int u = _source[in_arc]; u != join; u = _parent[u]) {
   1.444            _flow[_pred[u]] += _forward[u] ? -val : val;
   1.445 @@ -1316,7 +1324,7 @@
   1.446  
   1.447      // Update potentials
   1.448      void updatePotential() {
   1.449 -      Value sigma = _forward[u_in] ?
   1.450 +      Cost sigma = _forward[u_in] ?
   1.451          _pi[v_in] - _pi[u_in] - _cost[_pred[u_in]] :
   1.452          _pi[v_in] - _pi[u_in] + _cost[_pred[u_in]];
   1.453        if (_succ_num[u_in] > _node_num / 2) {
     2.1 --- a/test/min_cost_flow_test.cc	Wed Mar 25 21:37:50 2009 +0100
     2.2 +++ b/test/min_cost_flow_test.cc	Fri Apr 03 13:46:16 2009 +0200
     2.3 @@ -77,7 +77,7 @@
     2.4  
     2.5  
     2.6  // Check the interface of an MCF algorithm
     2.7 -template <typename GR, typename Value>
     2.8 +template <typename GR, typename Flow, typename Cost>
     2.9  class McfClassConcept
    2.10  {
    2.11  public:
    2.12 @@ -116,18 +116,19 @@
    2.13  
    2.14      typedef typename GR::Node Node;
    2.15      typedef typename GR::Arc Arc;
    2.16 -    typedef concepts::ReadMap<Node, Value> NM;
    2.17 -    typedef concepts::ReadMap<Arc, Value> AM;
    2.18 +    typedef concepts::ReadMap<Node, Flow> NM;
    2.19 +    typedef concepts::ReadMap<Arc, Flow> FAM;
    2.20 +    typedef concepts::ReadMap<Arc, Cost> CAM;
    2.21  
    2.22      const GR &g;
    2.23 -    const AM &lower;
    2.24 -    const AM &upper;
    2.25 -    const AM &cost;
    2.26 +    const FAM &lower;
    2.27 +    const FAM &upper;
    2.28 +    const CAM &cost;
    2.29      const NM &sup;
    2.30      const Node &n;
    2.31      const Arc &a;
    2.32 -    const Value &k;
    2.33 -    Value v;
    2.34 +    const Flow &k;
    2.35 +    Flow v;
    2.36      bool b;
    2.37  
    2.38      typename MCF::FlowMap &flow;
    2.39 @@ -206,15 +207,16 @@
    2.40  {
    2.41    // Check the interfaces
    2.42    {
    2.43 -    typedef int Value;
    2.44 +    typedef int Flow;
    2.45 +    typedef int Cost;
    2.46      // TODO: This typedef should be enabled if the standard maps are
    2.47      // reference maps in the graph concepts (See #190).
    2.48  /**/
    2.49      //typedef concepts::Digraph GR;
    2.50      typedef ListDigraph GR;
    2.51  /**/
    2.52 -    checkConcept< McfClassConcept<GR, Value>,
    2.53 -                  NetworkSimplex<GR, Value> >();
    2.54 +    checkConcept< McfClassConcept<GR, Flow, Cost>,
    2.55 +                  NetworkSimplex<GR, Flow, Cost> >();
    2.56    }
    2.57  
    2.58    // Run various MCF tests