author Peter Kovacs Fri, 03 Apr 2009 13:46:16 +0200 changeset 654 9ad8d2122b50 parent 653 c7d160f73d52 child 655 6ac5d9ae1d3d
Separate types for flow and cost values in NetworkSimplex (#234)
 lemon/network_simplex.h file | annotate | diff | comparison | revisions test/min_cost_flow_test.cc file | annotate | diff | comparison | revisions
     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.357 +    Cost totalCost() const {
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