1131 } |
1131 } |
1132 |
1132 |
1133 /// Update \c depth and \c potential node maps. |
1133 /// Update \c depth and \c potential node maps. |
1134 inline void updateDepthPotential() { |
1134 inline void updateDepthPotential() { |
1135 _depth[u_in] = _depth[v_in] + 1; |
1135 _depth[u_in] = _depth[v_in] + 1; |
1136 _potential[u_in] = _forward[u_in] ? |
1136 Cost sigma = _forward[u_in] ? |
1137 _potential[v_in] - _cost[_pred_edge[u_in]] : |
1137 _potential[v_in] - _potential[u_in] - _cost[_pred_edge[u_in]] : |
1138 _potential[v_in] + _cost[_pred_edge[u_in]]; |
1138 _potential[v_in] - _potential[u_in] + _cost[_pred_edge[u_in]]; |
1139 |
1139 _potential[u_in] += sigma; |
1140 Node u = _thread[u_in], v; |
1140 for(Node u = _thread[u_in]; _parent[u] != INVALID; u = _thread[u]) { |
1141 while (true) { |
1141 _depth[u] = _depth[_parent[u]] + 1; |
1142 v = _parent[u]; |
1142 if (_depth[u] <= _depth[u_in]) break; |
1143 if (v == INVALID) break; |
1143 _potential[u] += sigma; |
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]; |
|
1150 } |
1144 } |
1151 } |
1145 } |
1152 |
1146 |
1153 /// Execute the algorithm. |
1147 /// Execute the algorithm. |
1154 bool start(PivotRuleEnum pivot_rule) { |
1148 bool start(PivotRuleEnum pivot_rule) { |