RhodeCode

    typedef std::vector<signed char> CharVector;

    // Note: vector<signed char> is used instead of vector<ArcState> and 

    // vector<ArcDirection> for efficiency reasons

    // Direction constants for tree arcs

    enum ArcDirection {

      DIR_DOWN = -1,

      DIR_UP   =  1

    };

    CharVector _pred_dir;

    CharVector _state;

      const CharVector &_state;

      const CharVector &_state;

      const CharVector &_state;

      const CharVector &_state;

      const CharVector &_state;

        Cost c;

          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);

          if (c < 0) {

            _cand_cost[e] = c;

          } else {

          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);

          if (c < 0) {

            _cand_cost[e] = c;

      _pred_dir.resize(all_node_num);

            _pred_dir[u] = DIR_UP;

            _pred_dir[u] = DIR_DOWN;

            _pred_dir[u] = DIR_UP;

            _pred_dir[u] = DIR_DOWN;

            _pred_dir[u] = DIR_DOWN;

            _pred_dir[u] = DIR_UP;

      int first, second;

      Value c, d;

      // Search the cycle form the first node to the join node

        d = _flow[e];

        if (_pred_dir[u] == DIR_DOWN) {

          c = _cap[e];

          d = c >= MAX ? INF : c - d;

        }

      // Search the cycle form the second node to the join node

        d = _flow[e];

        if (_pred_dir[u] == DIR_UP) {

          c = _cap[e];

          d = c >= MAX ? INF : c - d;

        }

          _flow[_pred[u]] -= _pred_dir[u] * val;

          _flow[_pred[u]] += _pred_dir[u] * val;

      // Check if u_in and u_out coincide

      if (u_in == u_out) {

        // Update _parent, _pred, _pred_dir

        _parent[u_in] = v_in;

        _pred[u_in] = in_arc;

        _pred_dir[u_in] = u_in == _source[in_arc] ? DIR_UP : DIR_DOWN;

        // Update _thread and _rev_thread

        if (_thread[v_in] != u_out) {

          int after = _thread[old_last_succ];

          _thread[old_rev_thread] = after;

          _rev_thread[after] = old_rev_thread;

          after = _thread[v_in];

          _thread[v_in] = u_out;

          _rev_thread[u_out] = v_in;

          _thread[old_last_succ] = after;

          _rev_thread[after] = old_last_succ;

        }

        // Handle the case when old_rev_thread equals to v_in

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

        int thread_continue = old_rev_thread == v_in ?

          _thread[old_last_succ] : _thread[v_in];

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

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

        int stem = u_in;              // the current stem node

        int par_stem = v_in;          // the new parent of stem

        int next_stem;                // the next stem node

        int last = _last_succ[u_in];  // the last successor of stem

        int before, after = _thread[last];

        _thread[v_in] = u_in;

        _dirty_revs.clear();

        _dirty_revs.push_back(v_in);

        while (stem != u_out) {

          // Insert the next stem node into the thread list

          next_stem = _parent[stem];

          _thread[last] = next_stem;

          _dirty_revs.push_back(last);

          // Remove the subtree of stem from the thread list

          before = _rev_thread[stem];

          _thread[before] = after;

          _rev_thread[after] = before;

          // Change the parent node and shift stem nodes

          _parent[stem] = par_stem;

          par_stem = stem;

          stem = next_stem;

          // Update last and after

          last = _last_succ[stem] == _last_succ[par_stem] ?

            _rev_thread[par_stem] : _last_succ[stem];

          after = _thread[last];

        }

        _parent[u_out] = par_stem;

        _thread[last] = thread_continue;

        _rev_thread[thread_continue] = last;

        _last_succ[u_out] = last;

        // 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) {

          _thread[old_rev_thread] = after;

          _rev_thread[after] = old_rev_thread;

        }

        // Update _rev_thread using the new _thread values

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

          int u = _dirty_revs[i];

          _rev_thread[_thread[u]] = u;

        }

        // Update _pred, _pred_dir, _last_succ and _succ_num for the

        // stem nodes from u_out to u_in

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

        for (int u = u_out, p = _parent[u]; u != u_in; u = p, p = _parent[u]) {

          _pred[u] = _pred[p];

          _pred_dir[u] = -_pred_dir[p];

          tmp_sc += _succ_num[u] - _succ_num[p];

          _succ_num[u] = tmp_sc;

          _last_succ[p] = tmp_ls;

        }

        _pred[u_in] = in_arc;

        _pred_dir[u_in] = u_in == _source[in_arc] ? DIR_UP : DIR_DOWN;

        _succ_num[u_in] = old_succ_num;

      int up_limit_out = _last_succ[join] == v_in ? join : -1;

      int last_succ_out = _last_succ[u_out];

      for (int u = v_in; u != -1 && _last_succ[u] == v_in; u = _parent[u]) {

        _last_succ[u] = last_succ_out;

        for (int u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ;

      }

      else if (last_succ_out != old_last_succ) {

        for (int u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ;

          _last_succ[u] = last_succ_out;

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

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

    // Update potentials in the subtree that has been moved

      Cost sigma = _pi[v_in] - _pi[u_in] -

                   _pred_dir[u_in] * _cost[in_arc];