retrograd's blog

By retrograd, history, 5 months ago, In English

Hello!

Recently I have been trying to learn link cut trees (and splay trees, for that matter). I have tried to polish an implementation that is short (for our ICPC notebooks), and also easy to use and extend. I might be extending this blog post towards a tutorial on how link cut trees are used and, more so, how this template can be used.

The implementation is here:

struct LinkCut {
  struct Node {
    int p = 0, c[2] = {0, 0}, pp = 0;
    bool flip = 0;
    int val = 0, dp = 0;
  };
  vector<Node> T;
 
  LinkCut(int n) : T(n + 1) {}
 
  // SPLAY TREE OPERATIONS START

  int dir(int x, int y) { return T[x].c[1] == y; }
 
  void set(int x, int d, int y) {
    if (x) T[x].c[d] = y, pull(x);
    if (y) T[y].p = x;
  }
 
  void pull(int x) {
    if (!x) return;
    int &l = T[x].c[0], &r = T[x].c[1];
    T[x].dp = max({T[x].val, T[l].dp, T[r].dp});
  }
 
  void push(int x) {
    if (!x || !T[x].flip) return;
    int &l = T[x].c[0], &r = T[x].c[1];
    swap(l, r); T[l].flip ^= 1; T[r].flip ^= 1;
    T[x].flip = 0;
  }
 
  void rotate(int x, int d) { 
    int y = T[x].p, z = T[y].p, w = T[x].c[d];
    swap(T[x].pp, T[y].pp);
    set(y, !d, w);
    set(x, d, y);
    set(z, dir(z, y), x);
  }
 
  void splay(int x) { 
    for (push(x); T[x].p;) {
      int y = T[x].p, z = T[y].p;
      push(z); push(y); push(x);
      int dx = dir(y, x), dy = dir(z, y);
      if (!z) 
        rotate(x, !dx); 
      else if (dx == dy) 
        rotate(y, !dx), rotate(x, !dx); 
      else
        rotate(x, dy), rotate(x, dx);
    }
  }
 
  // SPLAY TREE OPERATIONS END
 
  void MakeRoot(int u) {
    Access(u);
    int l = T[u].c[0];
    T[l].flip ^= 1;
    swap(T[l].p, T[l].pp);
    set(u, 0, 0);
  }
 
  void Access(int _u) {
    for (int v = 0, u = _u; u; u = T[v = u].pp) {
      splay(u); splay(v);
      int r = T[u].c[1];
      T[v].pp = 0;
      swap(T[r].p, T[r].pp);
      set(u, 1, v);
    }
    splay(_u);
  }

  void Link(int u, int v) { 
    assert(!Connected(u, v));
    MakeRoot(v);
    T[v].pp = u;
  }

  void Cut(int u, int v) {
    MakeRoot(u); Access(u); splay(v);
    assert(T[v].pp == u);
    T[v].pp = 0;
  }

  bool Connected(int u, int v) {
    if (u == v) return true;
    MakeRoot(u); Access(v); splay(u);
    return T[v].p == u || T[T[v].p].p == u;
  }

  int GetPath(int u, int v) {
    MakeRoot(u); Access(v); return v;
  }
};

It is around 100 lines long (which is not ideal), but it has some neat features. For example, if you call lc.GetPath(a, b), the implementation will return the root of a splay tree node which contains the whole path from a to b. Also, the function lc.Access(v) will make sure that node v's splay tree would contain the whole path from the root at that time to v.

I feel like there is no implementation with a very clean way of modifying it (for the people who don't know LCT), so I decided to adapt one myself (also, I don't like using raw pointers -- if you're like me, you might enjoy this implementation). Also, another thing that I like about this implementation is that the splay tree code is independent to the fact that it's used inside a link-cut tree (it's just plain splay tree code, which can be extracted away).

In order to adapt the implementation to path aggregates (updates/queries of any type), you would have to create some function that updates/queries the splay tree node GetPath(u, v) and to potentially modify the push and pull methods (push is lazy propagation, whereas pull is regular tree update from children).

The only thing I'm not happy about is that the Access method is pretty ugly. However, I don't want to change its behaviour (I feel it's useful to have v splayed after Access(v) is called). Please let me know if you can rewrite the code in a more beautiful way.

Also, here is a pastebin of a strees test code, in case you want to test the implementation.

Any thoughts on how to improve the implementation? What do you think about it overall?

 
 
 
 
  • Vote: I like it
  • +235
  • Vote: I do not like it

»
5 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Auto comment: topic has been updated by retrograd (previous revision, new revision, compare).

»
5 months ago, # |
  Vote: I like it +27 Vote: I do not like it

There is in fact a way to implement without having to store a path-parent pointer, and that makes the implementation of Access(v) a bit more clean. This is my implementation. You can query for the sum of values of the vertices on a path and add a value to all vertices on a path, and I think it is easy enough to change for other types of queries/updates.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    That’s very interesting! While implementing I realized that one of parent and path parent would always be zero. I’m not sure if I will include it like that, as I think it might make debugging a little painful for little gain (also there might be more ‘if’ guards, if I decide to do so).

    I can see that (apart from the shared parent pointer) you have the Access method coded so that the vertex in the argument is splayed at the end. However, this is dependent on the fact that parent pointers are shared, if I’m not mistaken, right?

    I think your implementation of find_root might be buggy. Shouldn’t you propagate before going to the left child?

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      I don't really understand your first question, you can always splay the vertex in the argument at the end of Access.

      About having to propagate on find_root, I wasn't really sure when I read your question, but I've done some stress testing and it seems like you don't need to propagate there for some reason.

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        I guess you’re right about splaying in the end, it was just that my Access code was uglier that I had eanted it to be.

        I’ve tried your approach for Access, but I found it to be a bit slower ( I think it’s because you splay two times in each iteration, while this implementation splays only once (splay(v)) is a no-op.

        How did you stress test find_root? I assume that the cases where this bug would be exposed would have to be kind of specific. I would try generating long rooted paths and see if calls of rootify(), access() and findroot() yields the proper results (I would be really surprised).

        Anyways, I’ll try to think of some example, but intuition tells me that it might be fishy. Anyways, it’s a function that is usually not used so much, so it’s not that big of a deal.

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I don't see why it should be slower, one of those splays is actually just a rotation.

          I stress tested by generating random pairs of vertices and doing the operations (link, cut, rootify, print root) and comparing the results of the code with and without propagating. Just in case, I have fixed my implementation, thanks for pointing it out!

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    Your code is buggy, you should correct it!

»
5 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Also, I’m wondering why link cut trees have such good complexity guarantees. More specifically, heavy path decomposition guarantees that the path depth of any node is at most $$$O(log N)$$$. Why does this ‘random’ path decomposition work as well? Is there an easy-to-understand or intuitive proof that it is the case?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I would suggest you to look up the MIT OCW 6.851 lecture series. I think link cut trees are discussed in the dynamic graph lecture. It is well explained there why the complexity is what it is.

    (hint: consider the number of heavy and light edges affected in a preferred path change)

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      I’ve watched the analysis, and it seems reasonable (and kind of cool, to be fair); however, in order to fully close the loop, we would also have to prove that re-rooting the represented tree doesn’t change the heavy-light invariant considerably (which is probably true, as the only path where light edges might become heavy is on the reversed path, and there’s probably few of them, but I don’t know for sure). It’s also not clear to me how this impacts splay trees’ performance.

»
5 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Not the cleanest implementation out there, nonetheless I wrote it with readability in mind

It also doesn't use a separate path parent pointer: link

»
5 months ago, # |
  Vote: I like it +8 Vote: I do not like it

does link-cut work with treap, instead of splay?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    $$$\mathcal{O}(\log^2{}n) \rightharpoondown \mathcal{O}(\log{}n)$$$
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Also, another motivation on top of .__.'s is that splay trees are actually comparatively just as easy to code as treaps with parent pointers, in my opinion.

»
5 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Thanks a lot :D

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello! Does anybody know how to implement Dinic's algorithm using the optimization provided by link-cut trees?