COIN-OR::LEMON - Graph Library

Changeset 2628:74520139e388 in lemon-0.x


Ignore:
Timestamp:
11/13/08 11:54:42 (15 years ago)
Author:
Peter Kovacs
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3513
Message:

Improve tree update procedure in NetworkSimplex?
The new method updates a smaller subtree (fixing a bug) and shifting the
potentials with a costant value.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/network_simplex.h

    r2623 r2628  
    11341134    inline void updateDepthPotential() {
    11351135      _depth[u_in] = _depth[v_in] + 1;
    1136       _potential[u_in] = _forward[u_in] ?
    1137         _potential[v_in] - _cost[_pred_edge[u_in]] :
    1138         _potential[v_in] + _cost[_pred_edge[u_in]];
    1139 
    1140       Node u = _thread[u_in], v;
    1141       while (true) {
    1142         v = _parent[u];
    1143         if (v == INVALID) break;
    1144         _depth[u] = _depth[v] + 1;
    1145         _potential[u] = _forward[u] ?
    1146           _potential[v] - _cost[_pred_edge[u]] :
    1147           _potential[v] + _cost[_pred_edge[u]];
    1148         if (_depth[u] <= _depth[v_in]) break;
    1149         u = _thread[u];
     1136      Cost sigma = _forward[u_in] ?
     1137        _potential[v_in] - _potential[u_in] - _cost[_pred_edge[u_in]] :
     1138        _potential[v_in] - _potential[u_in] + _cost[_pred_edge[u_in]];
     1139      _potential[u_in] += sigma;
     1140      for(Node u = _thread[u_in]; _parent[u] != INVALID; u = _thread[u]) {
     1141        _depth[u] = _depth[_parent[u]] + 1;
     1142        if (_depth[u] <= _depth[u_in]) break;
     1143        _potential[u] += sigma;
    11501144      }
    11511145    }
Note: See TracChangeset for help on using the changeset viewer.