Merge bugfix #478
authorAlpar Juttner <alpar@cs.elte.hu>
Thu, 17 Oct 2013 15:08:41 +0200
changeset 1111a78e5b779b69
parent 1107 15e233f588da
parent 1110 c0c2f5c87aa6
child 1112 b6bad215bccd
child 1113 62dba6c90f35
Merge bugfix #478
lemon/capacity_scaling.h
lemon/cost_scaling.h
lemon/cycle_canceling.h
lemon/network_simplex.h
     1.1 --- a/lemon/capacity_scaling.h	Wed Sep 25 11:15:56 2013 +0200
     1.2 +++ b/lemon/capacity_scaling.h	Thu Oct 17 15:08:41 2013 +0200
     1.3 @@ -163,7 +163,7 @@
     1.4      int _root;
     1.5  
     1.6      // Parameters of the problem
     1.7 -    bool _have_lower;
     1.8 +    bool _has_lower;
     1.9      Value _sum_supply;
    1.10  
    1.11      // Data structures for storing the digraph
    1.12 @@ -356,10 +356,9 @@
    1.13      /// \return <tt>(*this)</tt>
    1.14      template <typename LowerMap>
    1.15      CapacityScaling& lowerMap(const LowerMap& map) {
    1.16 -      _have_lower = true;
    1.17 +      _has_lower = true;
    1.18        for (ArcIt a(_graph); a != INVALID; ++a) {
    1.19          _lower[_arc_idf[a]] = map[a];
    1.20 -        _lower[_arc_idb[a]] = map[a];
    1.21        }
    1.22        return *this;
    1.23      }
    1.24 @@ -543,7 +542,7 @@
    1.25          _upper[j] = INF;
    1.26          _cost[j] = _forward[j] ? 1 : -1;
    1.27        }
    1.28 -      _have_lower = false;
    1.29 +      _has_lower = false;
    1.30        return *this;
    1.31      }
    1.32  
    1.33 @@ -754,7 +753,7 @@
    1.34        // Remove non-zero lower bounds
    1.35        const Value MAX = std::numeric_limits<Value>::max();
    1.36        int last_out;
    1.37 -      if (_have_lower) {
    1.38 +      if (_has_lower) {
    1.39          for (int i = 0; i != _root; ++i) {
    1.40            last_out = _first_out[i+1];
    1.41            for (int j = _first_out[i]; j != last_out; ++j) {
    1.42 @@ -839,11 +838,11 @@
    1.43        return OPTIMAL;
    1.44      }
    1.45  
    1.46 -    // Check if the upper bound is greater or equal to the lower bound
    1.47 -    // on each arc.
    1.48 +    // Check if the upper bound is greater than or equal to the lower bound
    1.49 +    // on each forward arc.
    1.50      bool checkBoundMaps() {
    1.51        for (int j = 0; j != _res_arc_num; ++j) {
    1.52 -        if (_upper[j] < _lower[j]) return false;
    1.53 +        if (_forward[j] && _upper[j] < _lower[j]) return false;
    1.54        }
    1.55        return true;
    1.56      }
    1.57 @@ -857,10 +856,10 @@
    1.58          pt = startWithoutScaling();
    1.59  
    1.60        // Handle non-zero lower bounds
    1.61 -      if (_have_lower) {
    1.62 +      if (_has_lower) {
    1.63          int limit = _first_out[_root];
    1.64          for (int j = 0; j != limit; ++j) {
    1.65 -          if (!_forward[j]) _res_cap[j] += _lower[j];
    1.66 +          if (_forward[j]) _res_cap[_reverse[j]] += _lower[j];
    1.67          }
    1.68        }
    1.69  
     2.1 --- a/lemon/cost_scaling.h	Wed Sep 25 11:15:56 2013 +0200
     2.2 +++ b/lemon/cost_scaling.h	Thu Oct 17 15:08:41 2013 +0200
     2.3 @@ -256,7 +256,7 @@
     2.4      int _root;
     2.5  
     2.6      // Parameters of the problem
     2.7 -    bool _have_lower;
     2.8 +    bool _has_lower;
     2.9      Value _sum_supply;
    2.10      int _sup_node_num;
    2.11  
    2.12 @@ -372,10 +372,9 @@
    2.13      /// \return <tt>(*this)</tt>
    2.14      template <typename LowerMap>
    2.15      CostScaling& lowerMap(const LowerMap& map) {
    2.16 -      _have_lower = true;
    2.17 +      _has_lower = true;
    2.18        for (ArcIt a(_graph); a != INVALID; ++a) {
    2.19          _lower[_arc_idf[a]] = map[a];
    2.20 -        _lower[_arc_idb[a]] = map[a];
    2.21        }
    2.22        return *this;
    2.23      }
    2.24 @@ -568,7 +567,7 @@
    2.25          _scost[j] = 0;
    2.26          _scost[_reverse[j]] = 0;
    2.27        }
    2.28 -      _have_lower = false;
    2.29 +      _has_lower = false;
    2.30        return *this;
    2.31      }
    2.32  
    2.33 @@ -780,7 +779,7 @@
    2.34        // Remove infinite upper bounds and check negative arcs
    2.35        const Value MAX = std::numeric_limits<Value>::max();
    2.36        int last_out;
    2.37 -      if (_have_lower) {
    2.38 +      if (_has_lower) {
    2.39          for (int i = 0; i != _root; ++i) {
    2.40            last_out = _first_out[i+1];
    2.41            for (int j = _first_out[i]; j != last_out; ++j) {
    2.42 @@ -837,7 +836,7 @@
    2.43        for (NodeIt n(_graph); n != INVALID; ++n) {
    2.44          sup[n] = _supply[_node_id[n]];
    2.45        }
    2.46 -      if (_have_lower) {
    2.47 +      if (_has_lower) {
    2.48          for (ArcIt a(_graph); a != INVALID; ++a) {
    2.49            int j = _arc_idf[a];
    2.50            Value c = _lower[j];
    2.51 @@ -907,11 +906,11 @@
    2.52        return OPTIMAL;
    2.53      }
    2.54  
    2.55 -    // Check if the upper bound is greater or equal to the lower bound
    2.56 -    // on each arc.
    2.57 +    // Check if the upper bound is greater than or equal to the lower bound
    2.58 +    // on each forward arc.
    2.59      bool checkBoundMaps() {
    2.60        for (int j = 0; j != _res_arc_num; ++j) {
    2.61 -        if (_upper[j] < _lower[j]) return false;
    2.62 +        if (_forward[j] && _upper[j] < _lower[j]) return false;
    2.63        }
    2.64        return true;
    2.65      }
    2.66 @@ -991,10 +990,10 @@
    2.67        }
    2.68  
    2.69        // Handle non-zero lower bounds
    2.70 -      if (_have_lower) {
    2.71 +      if (_has_lower) {
    2.72          int limit = _first_out[_root];
    2.73          for (int j = 0; j != limit; ++j) {
    2.74 -          if (!_forward[j]) _res_cap[j] += _lower[j];
    2.75 +          if (_forward[j]) _res_cap[_reverse[j]] += _lower[j];
    2.76          }
    2.77        }
    2.78      }
     3.1 --- a/lemon/cycle_canceling.h	Wed Sep 25 11:15:56 2013 +0200
     3.2 +++ b/lemon/cycle_canceling.h	Thu Oct 17 15:08:41 2013 +0200
     3.3 @@ -195,7 +195,7 @@
     3.4      int _root;
     3.5  
     3.6      // Parameters of the problem
     3.7 -    bool _have_lower;
     3.8 +    bool _has_lower;
     3.9      Value _sum_supply;
    3.10  
    3.11      // Data structures for storing the digraph
    3.12 @@ -278,10 +278,9 @@
    3.13      /// \return <tt>(*this)</tt>
    3.14      template <typename LowerMap>
    3.15      CycleCanceling& lowerMap(const LowerMap& map) {
    3.16 -      _have_lower = true;
    3.17 +      _has_lower = true;
    3.18        for (ArcIt a(_graph); a != INVALID; ++a) {
    3.19          _lower[_arc_idf[a]] = map[a];
    3.20 -        _lower[_arc_idb[a]] = map[a];
    3.21        }
    3.22        return *this;
    3.23      }
    3.24 @@ -471,7 +470,7 @@
    3.25          _cost[j] = 0;
    3.26          _cost[_reverse[j]] = 0;
    3.27        }
    3.28 -      _have_lower = false;
    3.29 +      _has_lower = false;
    3.30        return *this;
    3.31      }
    3.32  
    3.33 @@ -684,7 +683,7 @@
    3.34        // Remove infinite upper bounds and check negative arcs
    3.35        const Value MAX = std::numeric_limits<Value>::max();
    3.36        int last_out;
    3.37 -      if (_have_lower) {
    3.38 +      if (_has_lower) {
    3.39          for (int i = 0; i != _root; ++i) {
    3.40            last_out = _first_out[i+1];
    3.41            for (int j = _first_out[i]; j != last_out; ++j) {
    3.42 @@ -727,7 +726,7 @@
    3.43        for (NodeIt n(_graph); n != INVALID; ++n) {
    3.44          sup[n] = _supply[_node_id[n]];
    3.45        }
    3.46 -      if (_have_lower) {
    3.47 +      if (_has_lower) {
    3.48          for (ArcIt a(_graph); a != INVALID; ++a) {
    3.49            int j = _arc_idf[a];
    3.50            Value c = _lower[j];
    3.51 @@ -784,11 +783,11 @@
    3.52        return OPTIMAL;
    3.53      }
    3.54  
    3.55 -    // Check if the upper bound is greater or equal to the lower bound
    3.56 -    // on each arc.
    3.57 +    // Check if the upper bound is greater than or equal to the lower bound
    3.58 +    // on each forward arc.
    3.59      bool checkBoundMaps() {
    3.60        for (int j = 0; j != _res_arc_num; ++j) {
    3.61 -        if (_upper[j] < _lower[j]) return false;
    3.62 +        if (_forward[j] && _upper[j] < _lower[j]) return false;
    3.63        }
    3.64        return true;
    3.65      }
    3.66 @@ -835,10 +834,10 @@
    3.67        }
    3.68  
    3.69        // Handle non-zero lower bounds
    3.70 -      if (_have_lower) {
    3.71 +      if (_has_lower) {
    3.72          int limit = _first_out[_root];
    3.73          for (int j = 0; j != limit; ++j) {
    3.74 -          if (!_forward[j]) _res_cap[j] += _lower[j];
    3.75 +          if (_forward[j]) _res_cap[_reverse[j]] += _lower[j];
    3.76          }
    3.77        }
    3.78      }
     4.1 --- a/lemon/network_simplex.h	Wed Sep 25 11:15:56 2013 +0200
     4.2 +++ b/lemon/network_simplex.h	Thu Oct 17 15:08:41 2013 +0200
     4.3 @@ -198,7 +198,7 @@
     4.4      int _search_arc_num;
     4.5  
     4.6      // Parameters of the problem
     4.7 -    bool _have_lower;
     4.8 +    bool _has_lower;
     4.9      SupplyType _stype;
    4.10      Value _sum_supply;
    4.11  
    4.12 @@ -682,7 +682,7 @@
    4.13      /// \return <tt>(*this)</tt>
    4.14      template <typename LowerMap>
    4.15      NetworkSimplex& lowerMap(const LowerMap& map) {
    4.16 -      _have_lower = true;
    4.17 +      _has_lower = true;
    4.18        for (ArcIt a(_graph); a != INVALID; ++a) {
    4.19          _lower[_arc_id[a]] = map[a];
    4.20        }
    4.21 @@ -879,7 +879,7 @@
    4.22          _upper[i] = INF;
    4.23          _cost[i] = 1;
    4.24        }
    4.25 -      _have_lower = false;
    4.26 +      _has_lower = false;
    4.27        _stype = GEQ;
    4.28        return *this;
    4.29      }
    4.30 @@ -1072,7 +1072,7 @@
    4.31            "Upper bounds must be greater or equal to the lower bounds");
    4.32  
    4.33        // Remove non-zero lower bounds
    4.34 -      if (_have_lower) {
    4.35 +      if (_has_lower) {
    4.36          for (int i = 0; i != _arc_num; ++i) {
    4.37            Value c = _lower[i];
    4.38            if (c >= 0) {
    4.39 @@ -1235,7 +1235,7 @@
    4.40        return true;
    4.41      }
    4.42  
    4.43 -    // Check if the upper bound is greater or equal to the lower bound
    4.44 +    // Check if the upper bound is greater than or equal to the lower bound
    4.45      // on each arc.
    4.46      bool checkBoundMaps() {
    4.47        for (int j = 0; j != _arc_num; ++j) {
    4.48 @@ -1612,7 +1612,7 @@
    4.49        }
    4.50  
    4.51        // Transform the solution and the supply map to the original form
    4.52 -      if (_have_lower) {
    4.53 +      if (_has_lower) {
    4.54          for (int i = 0; i != _arc_num; ++i) {
    4.55            Value c = _lower[i];
    4.56            if (c != 0) {