1.1 --- a/lemon/network_simplex.h	Fri Apr 03 13:46:16 2009 +0200
     1.2 +++ b/lemon/network_simplex.h	Fri Apr 03 18:59:15 2009 +0200
     1.3 @@ -54,7 +54,8 @@
     1.4    /// \tparam C The value type used for costs and potentials in the
     1.5    /// algorithm. By default it is the same as \c F.
     1.6    ///
     1.7 -  /// \warning Both value types must be signed integer types.
     1.8 +  /// \warning Both value types must be signed and all input data must
     1.9 +  /// be integer.
    1.10    ///
    1.11    /// \note %NetworkSimplex provides five different pivot rule
    1.12    /// implementations. For more information see \ref PivotRule.
    1.13 @@ -1044,8 +1045,10 @@
    1.14        }
    1.15  
    1.16        // Initialize arc maps
    1.17 -      Flow max_cap = std::numeric_limits<Flow>::max();
    1.18 -      Cost max_cost = std::numeric_limits<Cost>::max() / 4;
    1.19 +      Flow inf_cap =
    1.20 +        std::numeric_limits<Flow>::has_infinity ?
    1.21 +        std::numeric_limits<Flow>::infinity() :
    1.22 +        std::numeric_limits<Flow>::max();
    1.23        if (_pupper && _pcost) {
    1.24          for (int i = 0; i != _arc_num; ++i) {
    1.25            Arc e = _arc_ref[i];
    1.26 @@ -1069,7 +1072,7 @@
    1.27              _cap[i] = (*_pupper)[_arc_ref[i]];
    1.28          } else {
    1.29            for (int i = 0; i != _arc_num; ++i)
    1.30 -            _cap[i] = max_cap;
    1.31 +            _cap[i] = inf_cap;
    1.32          }
    1.33          if (_pcost) {
    1.34            for (int i = 0; i != _arc_num; ++i)
    1.35 @@ -1079,6 +1082,18 @@
    1.36              _cost[i] = 1;
    1.37          }
    1.38        }
    1.39 +      
    1.40 +      // Initialize artifical cost
    1.41 +      Cost art_cost;
    1.42 +      if (std::numeric_limits<Cost>::is_exact) {
    1.43 +        art_cost = std::numeric_limits<Cost>::max() / 4 + 1;
    1.44 +      } else {
    1.45 +        art_cost = std::numeric_limits<Cost>::min();
    1.46 +        for (int i = 0; i != _arc_num; ++i) {
    1.47 +          if (_cost[i] > art_cost) art_cost = _cost[i];
    1.48 +        }
    1.49 +        art_cost = (art_cost + 1) * _node_num;
    1.50 +      }
    1.51  
    1.52        // Remove non-zero lower bounds
    1.53        if (_plower) {
    1.54 @@ -1100,17 +1115,17 @@
    1.55          _last_succ[u] = u;
    1.56          _parent[u] = _root;
    1.57          _pred[u] = e;
    1.58 -        _cost[e] = max_cost;
    1.59 -        _cap[e] = max_cap;
    1.60 +        _cost[e] = art_cost;
    1.61 +        _cap[e] = inf_cap;
    1.62          _state[e] = STATE_TREE;
    1.63          if (_supply[u] >= 0) {
    1.64            _flow[e] = _supply[u];
    1.65            _forward[u] = true;
    1.66 -          _pi[u] = -max_cost;
    1.67 +          _pi[u] = -art_cost;
    1.68          } else {
    1.69            _flow[e] = -_supply[u];
    1.70            _forward[u] = false;
    1.71 -          _pi[u] = max_cost;
    1.72 +          _pi[u] = art_cost;
    1.73          }
    1.74        }
    1.75  
    1.76 @@ -1327,22 +1342,10 @@
    1.77        Cost sigma = _forward[u_in] ?
    1.78          _pi[v_in] - _pi[u_in] - _cost[_pred[u_in]] :
    1.79          _pi[v_in] - _pi[u_in] + _cost[_pred[u_in]];
    1.80 -      if (_succ_num[u_in] > _node_num / 2) {
    1.81 -        // Update in the upper subtree (which contains the root)
    1.82 -        int before = _rev_thread[u_in];
    1.83 -        int after = _thread[_last_succ[u_in]];
    1.84 -        _thread[before] = after;
    1.85 -        _pi[_root] -= sigma;
    1.86 -        for (int u = _thread[_root]; u != _root; u = _thread[u]) {
    1.87 -          _pi[u] -= sigma;
    1.88 -        }
    1.89 -        _thread[before] = u_in;
    1.90 -      } else {
    1.91 -        // Update in the lower subtree (which has been moved)
    1.92 -        int end = _thread[_last_succ[u_in]];
    1.93 -        for (int u = u_in; u != end; u = _thread[u]) {
    1.94 -          _pi[u] += sigma;
    1.95 -        }
    1.96 +      // Update potentials in the subtree, which has been moved
    1.97 +      int end = _thread[_last_succ[u_in]];
    1.98 +      for (int u = u_in; u != end; u = _thread[u]) {
    1.99 +        _pi[u] += sigma;
   1.100        }
   1.101      }
   1.102