RhodeCode

    IntVector _rev_thread;

    IntVector _succ_num;

    IntVector _last_succ;

    IntVector _dirty_revs;

      _rev_thread.resize(all_node_num);

      _succ_num.resize(all_node_num);

      _last_succ.resize(all_node_num);

      _rev_thread[0] = _root;

      _succ_num[_root] = all_node_num;

      _last_succ[_root] = _root - 1;

        _rev_thread[u + 1] = u;

        _succ_num[u] = 1;

        _last_succ[u] = u;

        if (_succ_num[u] < _succ_num[v]) {

          u = _parent[u];

        } else {

          v = _parent[v];

        }

    // Update the tree structure

    void updateTreeStructure() {

      int u, w;

      int old_rev_thread = _rev_thread[u_out];

      int old_succ_num = _succ_num[u_out];

      int old_last_succ = _last_succ[u_out];

      u = _last_succ[u_in];  // the last successor of u_in

      right = _thread[u];    // the node after it

      // Handle the case when old_rev_thread equals to v_in

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

      if (old_rev_thread == v_in) {

        last = _thread[_last_succ[u_out]];

      } else {

        last = _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)

      _dirty_revs.clear();

      _dirty_revs.push_back(v_in);

        // Insert the next stem node into the thread list

        new_stem = _parent[stem];

        _thread[u] = new_stem;

        _dirty_revs.push_back(u);

        // Remove the subtree of stem from the thread list

        w = _rev_thread[stem];

        _thread[w] = right;

        _rev_thread[right] = w;

        // Change the parent node and shift stem nodes

        // Update u and right

        u = _last_succ[stem] == _last_succ[par_stem] ?

          _rev_thread[par_stem] : _last_succ[stem];

      _rev_thread[last] = u;

      _last_succ[u_out] = u;

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

      // the case when old_rev_thread equals to v_in

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

      if (old_rev_thread != v_in) {

        _thread[old_rev_thread] = right;

        _rev_thread[right] = old_rev_thread;

      }

      // Update _rev_thread using the new _thread values

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

        u = _dirty_revs[i];

        _rev_thread[_thread[u]] = u;

      }

      // Update _pred, _forward, _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];

      u = u_out;

      while (u != u_in) {

        w = _parent[u];

        _pred[u] = _pred[w];

        _forward[u] = !_forward[w];

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

        _succ_num[u] = tmp_sc;

        _last_succ[w] = tmp_ls;

        u = w;

      }

      _pred[u_in] = in_arc;

      _forward[u_in] = (u_in == _source[in_arc]);

      _succ_num[u_in] = old_succ_num;

      // Set limits for updating _last_succ form v_in and v_out

      // towards the root

      int up_limit_in = -1;

      int up_limit_out = -1;

      if (_last_succ[join] == v_in) {

        up_limit_out = join;

        up_limit_in = join;

      }

      // Update _last_succ from v_in towards the root

      for (u = v_in; u != up_limit_in && _last_succ[u] == v_in;

           u = _parent[u]) {

        _last_succ[u] = _last_succ[u_out];

      }

      // Update _last_succ from v_out towards the root

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

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

             u = _parent[u]) {

          _last_succ[u] = old_rev_thread;

        }

      } else {

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

             u = _parent[u]) {

          _last_succ[u] = _last_succ[u_out];

        }

      }

      // Update _succ_num from v_in to join

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

        _succ_num[u] += old_succ_num;

      }

      // Update _succ_num from v_out to join

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

        _succ_num[u] -= old_succ_num;

    // Update potentials

    void updatePotential() {

      if (_succ_num[u_in] > _node_num / 2) {

        // Update in the upper subtree (which contains the root)

        int before = _rev_thread[u_in];

        int after = _thread[_last_succ[u_in]];

        _thread[before] = after;

        _pi[_root] -= sigma;

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

          _pi[u] -= sigma;

        }

        _thread[before] = u_in;

      } else {

        // Update in the lower subtree (which has been moved)

        int end = _thread[_last_succ[u_in]];

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

          _pi[u] += sigma;

        }

          updateTreeStructure();

          updatePotential();