Debug checking for capacity bounds in min cost flow algorithms (#454)
authorPeter Kovacs <kpeter@inf.elte.hu>
Sat, 16 Mar 2013 16:20:41 +0100
changeset 1070ee9bac10f58e
parent 1043 1bafdbd2fc46
child 1071 879fcb781086
child 1109 330264b171cf
Debug checking for capacity bounds in min cost flow algorithms (#454)
lemon/capacity_scaling.h
lemon/cost_scaling.h
lemon/cycle_canceling.h
lemon/network_simplex.h
     1.1 --- a/lemon/capacity_scaling.h	Sat Mar 20 11:03:12 2010 +0100
     1.2 +++ b/lemon/capacity_scaling.h	Sat Mar 16 16:20:41 2013 +0100
     1.3 @@ -737,6 +737,11 @@
     1.4        }
     1.5        if (_sum_supply > 0) return INFEASIBLE;
     1.6  
     1.7 +      // Check lower and upper bounds
     1.8 +      LEMON_DEBUG(checkBoundMaps(),
     1.9 +          "Upper bounds must be greater or equal to the lower bounds");
    1.10 +
    1.11 +
    1.12        // Initialize vectors
    1.13        for (int i = 0; i != _root; ++i) {
    1.14          _pi[i] = 0;
    1.15 @@ -830,6 +835,15 @@
    1.16  
    1.17        return OPTIMAL;
    1.18      }
    1.19 +    
    1.20 +    // Check if the upper bound is greater or equal to the lower bound
    1.21 +    // on each arc.
    1.22 +    bool checkBoundMaps() {
    1.23 +      for (int j = 0; j != _res_arc_num; ++j) {
    1.24 +        if (_upper[j] < _lower[j]) return false;
    1.25 +      }
    1.26 +      return true;
    1.27 +    }
    1.28  
    1.29      ProblemType start() {
    1.30        // Execute the algorithm
     2.1 --- a/lemon/cost_scaling.h	Sat Mar 20 11:03:12 2010 +0100
     2.2 +++ b/lemon/cost_scaling.h	Sat Mar 16 16:20:41 2013 +0100
     2.3 @@ -761,6 +761,10 @@
     2.4        }
     2.5        if (_sum_supply > 0) return INFEASIBLE;
     2.6  
     2.7 +      // Check lower and upper bounds
     2.8 +      LEMON_DEBUG(checkBoundMaps(),
     2.9 +          "Upper bounds must be greater or equal to the lower bounds");
    2.10 +
    2.11  
    2.12        // Initialize vectors
    2.13        for (int i = 0; i != _res_node_num; ++i) {
    2.14 @@ -897,6 +901,15 @@
    2.15  
    2.16        return OPTIMAL;
    2.17      }
    2.18 +    
    2.19 +    // Check if the upper bound is greater or equal to the lower bound
    2.20 +    // on each arc.
    2.21 +    bool checkBoundMaps() {
    2.22 +      for (int j = 0; j != _res_arc_num; ++j) {
    2.23 +        if (_upper[j] < _lower[j]) return false;
    2.24 +      }
    2.25 +      return true;
    2.26 +    }
    2.27  
    2.28      // Execute the algorithm and transform the results
    2.29      void start(Method method) {
     3.1 --- a/lemon/cycle_canceling.h	Sat Mar 20 11:03:12 2010 +0100
     3.2 +++ b/lemon/cycle_canceling.h	Sat Mar 16 16:20:41 2013 +0100
     3.3 @@ -670,6 +670,10 @@
     3.4        }
     3.5        if (_sum_supply > 0) return INFEASIBLE;
     3.6  
     3.7 +      // Check lower and upper bounds
     3.8 +      LEMON_DEBUG(checkBoundMaps(),
     3.9 +          "Upper bounds must be greater or equal to the lower bounds");
    3.10 +
    3.11  
    3.12        // Initialize vectors
    3.13        for (int i = 0; i != _res_node_num; ++i) {
    3.14 @@ -779,6 +783,15 @@
    3.15  
    3.16        return OPTIMAL;
    3.17      }
    3.18 +    
    3.19 +    // Check if the upper bound is greater or equal to the lower bound
    3.20 +    // on each arc.
    3.21 +    bool checkBoundMaps() {
    3.22 +      for (int j = 0; j != _res_arc_num; ++j) {
    3.23 +        if (_upper[j] < _lower[j]) return false;
    3.24 +      }
    3.25 +      return true;
    3.26 +    }
    3.27  
    3.28      // Build a StaticDigraph structure containing the current
    3.29      // residual network
     4.1 --- a/lemon/network_simplex.h	Sat Mar 20 11:03:12 2010 +0100
     4.2 +++ b/lemon/network_simplex.h	Sat Mar 16 16:20:41 2013 +0100
     4.3 @@ -1067,6 +1067,10 @@
     4.4        if ( !((_stype == GEQ && _sum_supply <= 0) ||
     4.5               (_stype == LEQ && _sum_supply >= 0)) ) return false;
     4.6  
     4.7 +      // Check lower and upper bounds
     4.8 +      LEMON_DEBUG(checkBoundMaps(),
     4.9 +          "Upper bounds must be greater or equal to the lower bounds");
    4.10 +
    4.11        // Remove non-zero lower bounds
    4.12        if (_have_lower) {
    4.13          for (int i = 0; i != _arc_num; ++i) {
    4.14 @@ -1230,6 +1234,15 @@
    4.15  
    4.16        return true;
    4.17      }
    4.18 +    
    4.19 +    // Check if the upper bound is greater or equal to the lower bound
    4.20 +    // on each arc.
    4.21 +    bool checkBoundMaps() {
    4.22 +      for (int j = 0; j != _arc_num; ++j) {
    4.23 +        if (_upper[j] < _lower[j]) return false;
    4.24 +      }
    4.25 +      return true;
    4.26 +    }
    4.27  
    4.28      // Find the join node
    4.29      void findJoinNode() {