Support real types + numerical stability fix in NS (#254)
authorPeter Kovacs <kpeter@inf.elte.hu>
Fri, 03 Apr 2009 18:59:15 +0200
changeset 6556ac5d9ae1d3d
parent 654 9ad8d2122b50
child 656 e6927fe719e6
Support real types + numerical stability fix in NS (#254)

- Real types are supported by appropriate inicialization.
- A feature of the XTI spanning tree structure is removed to ensure
numerical stability (could cause problems using integer types).
The node potentials are updated always on the lower subtree,
in order to prevent overflow problems.
The former method isn't notably faster during to our tests.
lemon/network_simplex.h
     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