RhodeCode

    typedef std::vector<int> IntVector;

    typedef std::vector<Value> ValueVector;

    typedef std::vector<Cost> CostVector;

    // State constants for arcs

    enum ArcState {

      STATE_LOWER =  1

    };

  private:

    IntVector _rev_thread;

    IntVector _succ_num;

    IntVector _last_succ;

    IntVector _dirty_revs;

    int _root;

    // Temporary data used in the current pivot iteration

    int in_arc, join, u_in, v_in, u_out, v_out;

    Value delta;

    const Value MAX;

      const IntVector  &_source;

      const IntVector  &_target;

      const CostVector &_cost;

      const CostVector &_pi;

      int &_in_arc;

      int _search_arc_num;

      const IntVector  &_source;

      const IntVector  &_target;

      const CostVector &_cost;

      const CostVector &_pi;

      int &_in_arc;

      int _search_arc_num;

      const IntVector  &_source;

      const IntVector  &_target;

      const CostVector &_cost;

      const CostVector &_pi;

      int &_in_arc;

      int _search_arc_num;

      const IntVector  &_source;

      const IntVector  &_target;

      const CostVector &_cost;

      const CostVector &_pi;

      int &_in_arc;

      int _search_arc_num;

      const IntVector  &_source;

      const IntVector  &_target;

      const CostVector &_cost;

      const CostVector &_pi;

      int &_in_arc;

      int _search_arc_num;

      bool findEnteringArc() {

        // Check the current candidate list

        int e;

        for (int i = 0; i != _curr_length; ++i) {

          e = _candidates[i];

            _candidates[i--] = _candidates[--_curr_length];

          }

        }

        int limit = _head_length;

        for (e = _next_arc; e != _search_arc_num; ++e) {

            _candidates[_curr_length++] = e;

          }

          if (--cnt == 0) {

      _parent.resize(all_node_num);

      _pred.resize(all_node_num);

      _thread.resize(all_node_num);

      _rev_thread.resize(all_node_num);

      _succ_num.resize(all_node_num);

          _cap[e] = INF;

          _state[e] = STATE_TREE;

          if (_supply[u] >= 0) {

            _pi[u] = 0;

            _source[e] = u;

            _target[e] = _root;

            _flow[e] = _supply[u];

            _cost[e] = 0;

          } else {

            _pi[u] = ART_COST;

            _source[e] = _root;

            _target[e] = u;

          _succ_num[u] = 1;

          _last_succ[u] = u;

          if (_supply[u] >= 0) {

            _pi[u] = 0;

            _pred[u] = e;

            _source[e] = u;

            _cost[e] = 0;

            _state[e] = STATE_TREE;

          } else {

            _pi[u] = ART_COST;

            _pred[u] = f;

            _source[f] = _root;

          _succ_num[u] = 1;

          _last_succ[u] = u;

          if (_supply[u] <= 0) {

            _pi[u] = 0;

            _pred[u] = e;

            _source[e] = _root;

            _cost[e] = 0;

            _state[e] = STATE_TREE;

          } else {

            _pi[u] = -ART_COST;

            _pred[u] = f;

            _source[f] = u;

    bool findLeavingArc() {

      // Initialize first and second nodes according to the direction

      // of the cycle

      if (_state[in_arc] == STATE_LOWER) {

        first  = _source[in_arc];

        second = _target[in_arc];

      }

      delta = _cap[in_arc];

      int result = 0;

      int e;

      for (int u = first; u != join; u = _parent[u]) {

        e = _pred[u];

        if (d < delta) {

          delta = d;

          u_out = u;

          result = 1;

        }

      }

      for (int u = second; u != join; u = _parent[u]) {

        e = _pred[u];

        if (d <= delta) {

          delta = d;

          u_out = u;

        Value val = _state[in_arc] * delta;

        _flow[in_arc] += val;

        for (int u = _source[in_arc]; u != join; u = _parent[u]) {

        }

        for (int u = _target[in_arc]; u != join; u = _parent[u]) {

        }

      }

      // Update the state of the entering and leaving arcs

    // Update the tree structure

    void updateTreeStructure() {

      int old_rev_thread = _rev_thread[u_out];

      int old_succ_num = _succ_num[u_out];

      int old_last_succ = _last_succ[u_out];

      v_out = _parent[u_out];

      // Handle the case when old_rev_thread equals to v_in

      // (it also means that join and v_out coincide)

      // Update _thread and _parent along the stem nodes (i.e. the nodes

      // between u_in and u_out, whose parent have to be changed)

      _dirty_revs.clear();

      _dirty_revs.push_back(v_in);

      while (stem != u_out) {

        // Insert the next stem node into the thread list

        // Remove the subtree of stem from the thread list

        // Change the parent node and shift stem nodes

        _parent[stem] = par_stem;

        par_stem = stem;

          _rev_thread[par_stem] : _last_succ[stem];

      }

      _parent[u_out] = par_stem;

      // Remove the subtree of u_out from the thread list except for

      // the case when old_rev_thread equals to v_in

      if (old_rev_thread != v_in) {

      }

      // Update _rev_thread using the new _thread values

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

        _rev_thread[_thread[u]] = u;

      }

      // stem nodes from u_out to u_in

      int tmp_sc = 0, tmp_ls = _last_succ[u_out];

        _succ_num[u] = tmp_sc;

      }

      _pred[u_in] = in_arc;

      _succ_num[u_in] = old_succ_num;

      }

      // Update _last_succ from v_in towards the root

      }

      // Update _last_succ from v_out towards the root

      if (join != old_rev_thread && v_in != old_rev_thread) {

             u = _parent[u]) {

          _last_succ[u] = old_rev_thread;

        }

             u = _parent[u]) {

        }

      }

      // Update _succ_num from v_in to join

        _succ_num[u] += old_succ_num;

      }

      // Update _succ_num from v_out to join

        _succ_num[u] -= old_succ_num;

      }

    }

    void updatePotential() {

      int end = _thread[_last_succ[u_in]];

      for (int u = u_in; u != end; u = _thread[u]) {

        _pi[u] += sigma;