# HG changeset patch
# User Peter Kovacs <kpeter@inf.elte.hu>
# Date 1238759176 -7200
# Node ID 9ad8d2122b50707d35ae3709c49e0c9368a2a6c4
# Parent  c7d160f73d52e2d3f1ab1236cb0b440daf5f7a85
Separate types for flow and cost values in NetworkSimplex (#234)

diff -r c7d160f73d52 -r 9ad8d2122b50 lemon/network_simplex.h
--- a/lemon/network_simplex.h	Wed Mar 25 21:37:50 2009 +0100
+++ b/lemon/network_simplex.h	Fri Apr 03 13:46:16 2009 +0200
@@ -49,24 +49,28 @@
   /// in LEMON for the minimum cost flow problem.
   ///
   /// \tparam GR The digraph type the algorithm runs on.
-  /// \tparam V The value type used in the algorithm.
-  /// By default it is \c int.
+  /// \tparam F The value type used for flow amounts, capacity bounds
+  /// and supply values in the algorithm. By default it is \c int.
+  /// \tparam C The value type used for costs and potentials in the
+  /// algorithm. By default it is the same as \c F.
   ///
-  /// \warning The value type must be a signed integer type.
+  /// \warning Both value types must be signed integer types.
   ///
   /// \note %NetworkSimplex provides five different pivot rule
   /// implementations. For more information see \ref PivotRule.
-  template <typename GR, typename V = int>
+  template <typename GR, typename F = int, typename C = F>
   class NetworkSimplex
   {
   public:
 
-    /// The value type of the algorithm
-    typedef V Value;
+    /// The flow type of the algorithm
+    typedef F Flow;
+    /// The cost type of the algorithm
+    typedef C Cost;
     /// The type of the flow map
-    typedef typename GR::template ArcMap<Value> FlowMap;
+    typedef typename GR::template ArcMap<Flow> FlowMap;
     /// The type of the potential map
-    typedef typename GR::template NodeMap<Value> PotentialMap;
+    typedef typename GR::template NodeMap<Cost> PotentialMap;
 
   public:
 
@@ -117,14 +121,16 @@
 
     TEMPLATE_DIGRAPH_TYPEDEFS(GR);
 
-    typedef typename GR::template ArcMap<Value> ValueArcMap;
-    typedef typename GR::template NodeMap<Value> ValueNodeMap;
+    typedef typename GR::template ArcMap<Flow> FlowArcMap;
+    typedef typename GR::template ArcMap<Cost> CostArcMap;
+    typedef typename GR::template NodeMap<Flow> FlowNodeMap;
 
     typedef std::vector<Arc> ArcVector;
     typedef std::vector<Node> NodeVector;
     typedef std::vector<int> IntVector;
     typedef std::vector<bool> BoolVector;
-    typedef std::vector<Value> ValueVector;
+    typedef std::vector<Flow> FlowVector;
+    typedef std::vector<Cost> CostVector;
 
     // State constants for arcs
     enum ArcStateEnum {
@@ -141,13 +147,13 @@
     int _arc_num;
 
     // Parameters of the problem
-    ValueArcMap *_plower;
-    ValueArcMap *_pupper;
-    ValueArcMap *_pcost;
-    ValueNodeMap *_psupply;
+    FlowArcMap *_plower;
+    FlowArcMap *_pupper;
+    CostArcMap *_pcost;
+    FlowNodeMap *_psupply;
     bool _pstsup;
     Node _psource, _ptarget;
-    Value _pstflow;
+    Flow _pstflow;
 
     // Result maps
     FlowMap *_flow_map;
@@ -162,11 +168,11 @@
     IntVector _target;
 
     // Node and arc data
-    ValueVector _cap;
-    ValueVector _cost;
-    ValueVector _supply;
-    ValueVector _flow;
-    ValueVector _pi;
+    FlowVector _cap;
+    CostVector _cost;
+    FlowVector _supply;
+    FlowVector _flow;
+    CostVector _pi;
 
     // Data for storing the spanning tree structure
     IntVector _parent;
@@ -184,7 +190,7 @@
     int in_arc, join, u_in, v_in, u_out, v_out;
     int first, second, right, last;
     int stem, par_stem, new_stem;
-    Value delta;
+    Flow delta;
 
   private:
 
@@ -196,9 +202,9 @@
       // References to the NetworkSimplex class
       const IntVector  &_source;
       const IntVector  &_target;
-      const ValueVector &_cost;
+      const CostVector &_cost;
       const IntVector  &_state;
-      const ValueVector &_pi;
+      const CostVector &_pi;
       int &_in_arc;
       int _arc_num;
 
@@ -216,7 +222,7 @@
 
       // Find next entering arc
       bool findEnteringArc() {
-        Value c;
+        Cost c;
         for (int e = _next_arc; e < _arc_num; ++e) {
           c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
           if (c < 0) {
@@ -247,9 +253,9 @@
       // References to the NetworkSimplex class
       const IntVector  &_source;
       const IntVector  &_target;
-      const ValueVector &_cost;
+      const CostVector &_cost;
       const IntVector  &_state;
-      const ValueVector &_pi;
+      const CostVector &_pi;
       int &_in_arc;
       int _arc_num;
 
@@ -264,7 +270,7 @@
 
       // Find next entering arc
       bool findEnteringArc() {
-        Value c, min = 0;
+        Cost c, min = 0;
         for (int e = 0; e < _arc_num; ++e) {
           c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
           if (c < min) {
@@ -286,9 +292,9 @@
       // References to the NetworkSimplex class
       const IntVector  &_source;
       const IntVector  &_target;
-      const ValueVector &_cost;
+      const CostVector &_cost;
       const IntVector  &_state;
-      const ValueVector &_pi;
+      const CostVector &_pi;
       int &_in_arc;
       int _arc_num;
 
@@ -314,7 +320,7 @@
 
       // Find next entering arc
       bool findEnteringArc() {
-        Value c, min = 0;
+        Cost c, min = 0;
         int cnt = _block_size;
         int e, min_arc = _next_arc;
         for (e = _next_arc; e < _arc_num; ++e) {
@@ -358,9 +364,9 @@
       // References to the NetworkSimplex class
       const IntVector  &_source;
       const IntVector  &_target;
-      const ValueVector &_cost;
+      const CostVector &_cost;
       const IntVector  &_state;
-      const ValueVector &_pi;
+      const CostVector &_pi;
       int &_in_arc;
       int _arc_num;
 
@@ -394,7 +400,7 @@
 
       /// Find next entering arc
       bool findEnteringArc() {
-        Value min, c;
+        Cost min, c;
         int e, min_arc = _next_arc;
         if (_curr_length > 0 && _minor_count < _minor_limit) {
           // Minor iteration: select the best eligible arc from the
@@ -463,9 +469,9 @@
       // References to the NetworkSimplex class
       const IntVector  &_source;
       const IntVector  &_target;
-      const ValueVector &_cost;
+      const CostVector &_cost;
       const IntVector  &_state;
-      const ValueVector &_pi;
+      const CostVector &_pi;
       int &_in_arc;
       int _arc_num;
 
@@ -473,15 +479,15 @@
       int _block_size, _head_length, _curr_length;
       int _next_arc;
       IntVector _candidates;
-      ValueVector _cand_cost;
+      CostVector _cand_cost;
 
       // Functor class to compare arcs during sort of the candidate list
       class SortFunc
       {
       private:
-        const ValueVector &_map;
+        const CostVector &_map;
       public:
-        SortFunc(const ValueVector &map) : _map(map) {}
+        SortFunc(const CostVector &map) : _map(map) {}
         bool operator()(int left, int right) {
           return _map[left] > _map[right];
         }
@@ -590,9 +596,12 @@
       _local_flow(false), _local_potential(false),
       _node_id(graph)
     {
-      LEMON_ASSERT(std::numeric_limits<Value>::is_integer &&
-                   std::numeric_limits<Value>::is_signed,
-        "The value type of NetworkSimplex must be a signed integer");
+      LEMON_ASSERT(std::numeric_limits<Flow>::is_integer &&
+                   std::numeric_limits<Flow>::is_signed,
+        "The flow type of NetworkSimplex must be signed integer");
+      LEMON_ASSERT(std::numeric_limits<Cost>::is_integer &&
+                   std::numeric_limits<Cost>::is_signed,
+        "The cost type of NetworkSimplex must be signed integer");
     }
 
     /// Destructor.
@@ -609,14 +618,14 @@
     /// on all arcs.
     ///
     /// \param map An arc map storing the lower bounds.
-    /// Its \c Value type must be convertible to the \c Value type
+    /// Its \c Value type must be convertible to the \c Flow type
     /// of the algorithm.
     ///
     /// \return <tt>(*this)</tt>
     template <typename LOWER>
     NetworkSimplex& lowerMap(const LOWER& map) {
       delete _plower;
-      _plower = new ValueArcMap(_graph);
+      _plower = new FlowArcMap(_graph);
       for (ArcIt a(_graph); a != INVALID; ++a) {
         (*_plower)[a] = map[a];
       }
@@ -629,17 +638,17 @@
     /// If none of the functions \ref upperMap(), \ref capacityMap()
     /// and \ref boundMaps() is used before calling \ref run(),
     /// the upper bounds (capacities) will be set to
-    /// \c std::numeric_limits<Value>::max() on all arcs.
+    /// \c std::numeric_limits<Flow>::max() on all arcs.
     ///
     /// \param map An arc map storing the upper bounds.
-    /// Its \c Value type must be convertible to the \c Value type
+    /// Its \c Value type must be convertible to the \c Flow type
     /// of the algorithm.
     ///
     /// \return <tt>(*this)</tt>
     template<typename UPPER>
     NetworkSimplex& upperMap(const UPPER& map) {
       delete _pupper;
-      _pupper = new ValueArcMap(_graph);
+      _pupper = new FlowArcMap(_graph);
       for (ArcIt a(_graph); a != INVALID; ++a) {
         (*_pupper)[a] = map[a];
       }
@@ -666,13 +675,13 @@
     /// If none of the functions \ref upperMap(), \ref capacityMap()
     /// and \ref boundMaps() is used before calling \ref run(),
     /// the upper bounds (capacities) will be set to
-    /// \c std::numeric_limits<Value>::max() on all arcs.
+    /// \c std::numeric_limits<Flow>::max() on all arcs.
     ///
     /// \param lower An arc map storing the lower bounds.
     /// \param upper An arc map storing the upper bounds.
     ///
     /// The \c Value type of the maps must be convertible to the
-    /// \c Value type of the algorithm.
+    /// \c Flow type of the algorithm.
     ///
     /// \note This function is just a shortcut of calling \ref lowerMap()
     /// and \ref upperMap() separately.
@@ -690,14 +699,14 @@
     /// will be set to \c 1 on all arcs.
     ///
     /// \param map An arc map storing the costs.
-    /// Its \c Value type must be convertible to the \c Value type
+    /// Its \c Value type must be convertible to the \c Cost type
     /// of the algorithm.
     ///
     /// \return <tt>(*this)</tt>
     template<typename COST>
     NetworkSimplex& costMap(const COST& map) {
       delete _pcost;
-      _pcost = new ValueArcMap(_graph);
+      _pcost = new CostArcMap(_graph);
       for (ArcIt a(_graph); a != INVALID; ++a) {
         (*_pcost)[a] = map[a];
       }
@@ -712,7 +721,7 @@
     /// (It makes sense only if non-zero lower bounds are given.)
     ///
     /// \param map A node map storing the supply values.
-    /// Its \c Value type must be convertible to the \c Value type
+    /// Its \c Value type must be convertible to the \c Flow type
     /// of the algorithm.
     ///
     /// \return <tt>(*this)</tt>
@@ -720,7 +729,7 @@
     NetworkSimplex& supplyMap(const SUP& map) {
       delete _psupply;
       _pstsup = false;
-      _psupply = new ValueNodeMap(_graph);
+      _psupply = new FlowNodeMap(_graph);
       for (NodeIt n(_graph); n != INVALID; ++n) {
         (*_psupply)[n] = map[n];
       }
@@ -741,7 +750,7 @@
     /// (i.e. the supply of \c s and the demand of \c t).
     ///
     /// \return <tt>(*this)</tt>
-    NetworkSimplex& stSupply(const Node& s, const Node& t, Value k) {
+    NetworkSimplex& stSupply(const Node& s, const Node& t, Flow k) {
       delete _psupply;
       _psupply = NULL;
       _pstsup = true;
@@ -874,14 +883,14 @@
     /// \brief Return the total cost of the found flow.
     ///
     /// This function returns the total cost of the found flow.
-    /// The complexity of the function is \f$ O(e) \f$.
+    /// The complexity of the function is O(e).
     ///
     /// \note The return type of the function can be specified as a
     /// template parameter. For example,
     /// \code
     ///   ns.totalCost<double>();
     /// \endcode
-    /// It is useful if the total cost cannot be stored in the \c Value
+    /// It is useful if the total cost cannot be stored in the \c Cost
     /// type of the algorithm, which is the default return type of the
     /// function.
     ///
@@ -900,8 +909,8 @@
     }
 
 #ifndef DOXYGEN
-    Value totalCost() const {
-      return totalCost<Value>();
+    Cost totalCost() const {
+      return totalCost<Cost>();
     }
 #endif
 
@@ -910,7 +919,7 @@
     /// This function returns the flow on the given arc.
     ///
     /// \pre \ref run() must be called before using this function.
-    Value flow(const Arc& a) const {
+    Flow flow(const Arc& a) const {
       return (*_flow_map)[a];
     }
 
@@ -930,7 +939,7 @@
     /// given node.
     ///
     /// \pre \ref run() must be called before using this function.
-    Value potential(const Node& n) const {
+    Cost potential(const Node& n) const {
       return (*_potential_map)[n];
     }
 
@@ -996,7 +1005,7 @@
         _pstflow = 0;
       }
       if (_psupply) {
-        Value sum = 0;
+        Flow sum = 0;
         int i = 0;
         for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
           _node_id[n] = i;
@@ -1035,6 +1044,8 @@
       }
 
       // Initialize arc maps
+      Flow max_cap = std::numeric_limits<Flow>::max();
+      Cost max_cost = std::numeric_limits<Cost>::max() / 4;
       if (_pupper && _pcost) {
         for (int i = 0; i != _arc_num; ++i) {
           Arc e = _arc_ref[i];
@@ -1057,9 +1068,8 @@
           for (int i = 0; i != _arc_num; ++i)
             _cap[i] = (*_pupper)[_arc_ref[i]];
         } else {
-          Value val = std::numeric_limits<Value>::max();
           for (int i = 0; i != _arc_num; ++i)
-            _cap[i] = val;
+            _cap[i] = max_cap;
         }
         if (_pcost) {
           for (int i = 0; i != _arc_num; ++i)
@@ -1073,7 +1083,7 @@
       // Remove non-zero lower bounds
       if (_plower) {
         for (int i = 0; i != _arc_num; ++i) {
-          Value c = (*_plower)[_arc_ref[i]];
+          Flow c = (*_plower)[_arc_ref[i]];
           if (c != 0) {
             _cap[i] -= c;
             _supply[_source[i]] -= c;
@@ -1083,8 +1093,6 @@
       }
 
       // Add artificial arcs and initialize the spanning tree data structure
-      Value max_cap = std::numeric_limits<Value>::max();
-      Value max_cost = std::numeric_limits<Value>::max() / 4;
       for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
         _thread[u] = u + 1;
         _rev_thread[u + 1] = u;
@@ -1137,7 +1145,7 @@
       }
       delta = _cap[in_arc];
       int result = 0;
-      Value d;
+      Flow d;
       int e;
 
       // Search the cycle along the path form the first node to the root
@@ -1175,7 +1183,7 @@
     void changeFlow(bool change) {
       // Augment along the cycle
       if (delta > 0) {
-        Value val = _state[in_arc] * delta;
+        Flow val = _state[in_arc] * delta;
         _flow[in_arc] += val;
         for (int u = _source[in_arc]; u != join; u = _parent[u]) {
           _flow[_pred[u]] += _forward[u] ? -val : val;
@@ -1316,7 +1324,7 @@
 
     // Update potentials
     void updatePotential() {
-      Value sigma = _forward[u_in] ?
+      Cost sigma = _forward[u_in] ?
         _pi[v_in] - _pi[u_in] - _cost[_pred[u_in]] :
         _pi[v_in] - _pi[u_in] + _cost[_pred[u_in]];
       if (_succ_num[u_in] > _node_num / 2) {
diff -r c7d160f73d52 -r 9ad8d2122b50 test/min_cost_flow_test.cc
--- a/test/min_cost_flow_test.cc	Wed Mar 25 21:37:50 2009 +0100
+++ b/test/min_cost_flow_test.cc	Fri Apr 03 13:46:16 2009 +0200
@@ -77,7 +77,7 @@
 
 
 // Check the interface of an MCF algorithm
-template <typename GR, typename Value>
+template <typename GR, typename Flow, typename Cost>
 class McfClassConcept
 {
 public:
@@ -116,18 +116,19 @@
 
     typedef typename GR::Node Node;
     typedef typename GR::Arc Arc;
-    typedef concepts::ReadMap<Node, Value> NM;
-    typedef concepts::ReadMap<Arc, Value> AM;
+    typedef concepts::ReadMap<Node, Flow> NM;
+    typedef concepts::ReadMap<Arc, Flow> FAM;
+    typedef concepts::ReadMap<Arc, Cost> CAM;
 
     const GR &g;
-    const AM &lower;
-    const AM &upper;
-    const AM &cost;
+    const FAM &lower;
+    const FAM &upper;
+    const CAM &cost;
     const NM &sup;
     const Node &n;
     const Arc &a;
-    const Value &k;
-    Value v;
+    const Flow &k;
+    Flow v;
     bool b;
 
     typename MCF::FlowMap &flow;
@@ -206,15 +207,16 @@
 {
   // Check the interfaces
   {
-    typedef int Value;
+    typedef int Flow;
+    typedef int Cost;
     // TODO: This typedef should be enabled if the standard maps are
     // reference maps in the graph concepts (See #190).
 /**/
     //typedef concepts::Digraph GR;
     typedef ListDigraph GR;
 /**/
-    checkConcept< McfClassConcept<GR, Value>,
-                  NetworkSimplex<GR, Value> >();
+    checkConcept< McfClassConcept<GR, Flow, Cost>,
+                  NetworkSimplex<GR, Flow, Cost> >();
   }
 
   // Run various MCF tests