RhodeCode

                if (new_rank_v < old_rank_v) {

                  _rank[v] = new_rank_v;

                  _next_out[v] = _first_out[v];

                  // Remove v from its old bucket

                  if (old_rank_v < _max_rank) {

                    if (_buckets[old_rank_v] == v) {

                      _buckets[old_rank_v] = _bucket_next[v];

                    } else {

                      int pv = _bucket_prev[v], nv = _bucket_next[v];

                      _bucket_next[pv] = nv;

                      _bucket_prev[nv] = pv;

                    }

                  }

                  // Insert v into its new bucket

                  int nv = _buckets[new_rank_v];

                  _bucket_next[v] = nv;

                  _bucket_prev[nv] = v;

                  _buckets[new_rank_v] = v;

                }

              }

            }

          }

          // Finish search if there are no more active nodes

          if (_excess[u] > 0) {

            total_excess -= _excess[u];

            if (total_excess <= 0) break;

          }

        }

        if (total_excess <= 0) break;

      }

      // Relabel nodes

      for (int u = 0; u != _res_node_num; ++u) {

        int k = std::min(_rank[u], r);

        if (k > 0) {

          _pi[u] -= _epsilon * k;

          _next_out[u] = _first_out[u];

        }

      }

    }

    /// Execute the algorithm performing augment and relabel operations

    void startAugment(int max_length) {

      // Paramters for heuristics

      const int EARLY_TERM_EPSILON_LIMIT = 1000;

        (_res_node_num + _sup_node_num * _sup_node_num));

      // Perform cost scaling phases

      for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ?

                                        1 : _epsilon / _alpha )

      {

        // Early termination heuristic

        if (_epsilon <= EARLY_TERM_EPSILON_LIMIT) {

          if (earlyTermination()) break;

        }

        // Initialize current phase

        initPhase();

        // Perform partial augment and relabel operations

        while (true) {

          // Select an active node (FIFO selection)

          while (_active_nodes.size() > 0 &&

                 _excess[_active_nodes.front()] <= 0) {

            _active_nodes.pop_front();

          }

          if (_active_nodes.size() == 0) break;

          int start = _active_nodes.front();

          // Find an augmenting path from the start node

          int tip = start;

            int u;

            int last_out = _first_out[tip+1];

            for (int a = _next_out[tip]; a != last_out; ++a) {

              u = _target[a];

                path.push_back(a);

                _next_out[tip] = a;

                tip = u;

                goto next_step;

              }

            }

            // Relabel tip node

            if (tip != start) {

              int ra = _reverse[path.back()];

            }

            for (int a = _first_out[tip]; a != last_out; ++a) {

              rc = _cost[a] + pi_tip - _pi[_target[a]];

                min_red_cost = rc;

              }

            }

            _pi[tip] -= min_red_cost + _epsilon;

            _next_out[tip] = _first_out[tip];

            ++relabel_cnt;

            // Step back

            if (tip != start) {

              path.pop_back();

            }

          next_step: ;

          }

          // Augment along the found path (as much flow as possible)

          Value delta;

          int pa, u, v = start;

          for (int i = 0; i != int(path.size()); ++i) {

            pa = path[i];

            u = v;

            v = _target[pa];

            delta = std::min(_res_cap[pa], _excess[u]);

            _res_cap[pa] -= delta;

            _res_cap[_reverse[pa]] += delta;

            _excess[u] -= delta;

            _excess[v] += delta;

              _active_nodes.push_back(v);

          }

          // Global update heuristic

            globalUpdate();

          }

        }

      }

    }

    /// Execute the algorithm performing push and relabel operations

    void startPush() {

      // Paramters for heuristics

      const int EARLY_TERM_EPSILON_LIMIT = 1000;

      const double GLOBAL_UPDATE_FACTOR = 2.0;

        (_res_node_num + _sup_node_num * _sup_node_num));

      // Perform cost scaling phases

      BoolVector hyper(_res_node_num, false);

      LargeCostVector hyper_cost(_res_node_num);

      for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ?

                                        1 : _epsilon / _alpha )

      {

        // Early termination heuristic

        if (_epsilon <= EARLY_TERM_EPSILON_LIMIT) {

          if (earlyTermination()) break;

        }

        // Initialize current phase

        initPhase();

        // Perform push and relabel operations

        while (_active_nodes.size() > 0) {

          LargeCost min_red_cost, rc, pi_n;

          Value delta;

          int n, t, a, last_out = _res_arc_num;

        next_node:

          // Select an active node (FIFO selection)

          n = _active_nodes.front();

          last_out = _first_out[n+1];

          pi_n = _pi[n];

          // Perform push operations if there are admissible arcs

          if (_excess[n] > 0) {

            for (a = _next_out[n]; a != last_out; ++a) {

              if (_res_cap[a] > 0 &&

                  _cost[a] + pi_n - _pi[_target[a]] < 0) {

                delta = std::min(_res_cap[a], _excess[n]);

                t = _target[a];

                // Push-look-ahead heuristic

                Value ahead = -_excess[t];

                int last_out_t = _first_out[t+1];

                LargeCost pi_t = _pi[t];

                for (int ta = _next_out[t]; ta != last_out_t; ++ta) {

                  if (_res_cap[ta] > 0 &&

                      _cost[ta] + pi_t - _pi[_target[ta]] < 0)

                    ahead += _res_cap[ta];

                  if (ahead >= delta) break;

                }

                if (ahead < 0) ahead = 0;

                // Push flow along the arc

                if (ahead < delta && !hyper[t]) {

                  _res_cap[a] -= ahead;

                  _res_cap[_reverse[a]] += ahead;

                  _excess[n] -= ahead;

                  _excess[t] += ahead;

                  _active_nodes.push_front(t);

                  hyper[t] = true;

                  hyper_cost[t] = _cost[a] + pi_n - pi_t;

                  _next_out[n] = a;

                  goto next_node;

                } else {

                  _res_cap[a] -= delta;

                  _res_cap[_reverse[a]] += delta;

                  _excess[n] -= delta;

                  _excess[t] += delta;

                  if (_excess[t] > 0 && _excess[t] <= delta)

                    _active_nodes.push_back(t);

                }

                if (_excess[n] == 0) {

                  _next_out[n] = a;

                  goto remove_nodes;

                }

              }

            }

            _next_out[n] = a;

          }

          // Relabel the node if it is still active (or hyper)

          if (_excess[n] > 0 || hyper[n]) {

             min_red_cost = hyper[n] ? -hyper_cost[n] :

               std::numeric_limits<LargeCost>::max();

            for (int a = _first_out[n]; a != last_out; ++a) {

              rc = _cost[a] + pi_n - _pi[_target[a]];

                min_red_cost = rc;

              }

            }

            _pi[n] -= min_red_cost + _epsilon;

            _next_out[n] = _first_out[n];

            hyper[n] = false;

            ++relabel_cnt;

          }

          // Remove nodes that are not active nor hyper

        remove_nodes:

          while ( _active_nodes.size() > 0 &&

                  _excess[_active_nodes.front()] <= 0 &&

                  !hyper[_active_nodes.front()] ) {

            _active_nodes.pop_front();

          }

          // Global update heuristic

            globalUpdate();

            for (int u = 0; u != _res_node_num; ++u)

              hyper[u] = false;

          }

        }

      }

    }

  }; //class CostScaling

  ///@}

} //namespace lemon

#endif //LEMON_COST_SCALING_H