# HG changeset patch
# User kpeter
# Date 1226573682 0
# Node ID 74520139e388af75a97744b2776d49413f85779c
# Parent  197e2ea11bad170d381cc45113aa625c4b506c34
Improve tree update procedure in NetworkSimplex
The new method updates a smaller subtree (fixing a bug) and shifting the
potentials with a costant value.

diff -r 197e2ea11bad -r 74520139e388 lemon/network_simplex.h
--- a/lemon/network_simplex.h	Fri Nov 07 20:15:10 2008 +0000
+++ b/lemon/network_simplex.h	Thu Nov 13 10:54:42 2008 +0000
@@ -1133,20 +1133,14 @@
     /// Update \c depth and \c potential node maps.
     inline void updateDepthPotential() {
       _depth[u_in] = _depth[v_in] + 1;
-      _potential[u_in] = _forward[u_in] ?
-        _potential[v_in] - _cost[_pred_edge[u_in]] :
-        _potential[v_in] + _cost[_pred_edge[u_in]];
-
-      Node u = _thread[u_in], v;
-      while (true) {
-        v = _parent[u];
-        if (v == INVALID) break;
-        _depth[u] = _depth[v] + 1;
-        _potential[u] = _forward[u] ?
-          _potential[v] - _cost[_pred_edge[u]] :
-          _potential[v] + _cost[_pred_edge[u]];
-        if (_depth[u] <= _depth[v_in]) break;
-        u = _thread[u];
+      Cost sigma = _forward[u_in] ?
+        _potential[v_in] - _potential[u_in] - _cost[_pred_edge[u_in]] :
+        _potential[v_in] - _potential[u_in] + _cost[_pred_edge[u_in]];
+      _potential[u_in] += sigma;
+      for(Node u = _thread[u_in]; _parent[u] != INVALID; u = _thread[u]) {
+        _depth[u] = _depth[_parent[u]] + 1;
+        if (_depth[u] <= _depth[u_in]) break;
+        _potential[u] += sigma;
       }
     }