# Storing Set Families More Compactly with Top ZDDs
## 3 Top Tree and Top DAG
### Top DAG Compression
#### 3.2.2 Operations on Top DAGs  
Consider to support operations on a tree \(T\) which is represented by top DAG \(\mathcal{T}D\). From now on, a node \(x\) in \(T\) stands for the node with preorder id \(x\) in \(T\). By storing additional information to each vertex of the top DAG, the following tree operations can be supported [12]. * \(Access(x)\): returns the label of \(x\). * \(Decompress(x)\): returns the subtree \(T(x)\) of \(T\) rooted at \(x\). * \(Parent(x)\): returns the preorder id of the parent of \(x\). Figure 8: An example of top tree. Alongside each vertex of the top tree, the corresponding cluster is drawn. Red nodes show boundary nodes. * \(Depth(x)\): returns the depth, i.e., the distance to the root, of \(x\). * \(Height(x)\): returns the height, i.e., the distance to the farthest leaf, of \(x\). * \(Size(x)\): returns the subtree size rooted at \(x\). * \(Firstchild(x)\): returns the preorder id of the first child of \(x\), or reports \(x\) is a leaf. * \(NextSibling(x)\): returns the preorder id of the next sibling of \(x\), or reports it does not exist. * \(LevelAncestor(x,i)\): returns the preorder id of the ancestor of \(x\) with distance \(i\) from \(x\). * \(LCA(x,y)\): returns the preorder id of the lowest common ancestor between \(x\) and \(y\). For a tree with \(n\) nodes, all operations except \(Decompress(\cdot)\) are done in \(\operatorname{O}(\log n)\) time, and \(Decompress(\cdot)\) is done in \(\operatorname{O}(\log n+|T(x)|)\) time. We explain the algorithm for \(Access(x)\) based on a recursive function \(sub(u,k)\) for a vertex \(u\) of the top DAG and an integer \(k\). The function \(sub(u,k)\) returns the label of the node with local preorder id \(k\) inside the cluster corresponding to vertex \(u\) of the top DAG. Note that \(Access(x)\) can be achieved by doing \(sub(r,x)\) because the cluster corresponding to \(r\) is the whole tree. The function \(sub(u,k)\) is computed recursively as follows. If \(u\) has no outgoing edges, \(u\) is a leaf of the top DAG. Thus, \(u\) corresponds to a cluster consisting of a single edge. In this case \(k\) is either \(0\) or \(1\). For such a cluster, only the label of the two endpoints of the edge is stored. Let \(s\) and \(t\) be the label of the starting point and ending point, respectively. If \(k=0\), it returns \(sub(u,k)=s\); if \(k=1\), it returns \(sub(u,k)=t\). If \(u\) is a vertex corresponding to horizontal merge, let \(v\) and \(w\) be the left and the right child of \(u\), respectively, let \(cl(u),cl(v),cl(w)\) be the corresponding cluster of \(u,v,w\), respectively, and let \(C(u),C(v),C(w)\) be their sizes. If we traverse nodes of \(cl(u)\) in preorder, the first one is the node shared by \(cl(v)\) and \(cl(w)\), then all the nodes of \(cl(v)\) appear and finally nodes of \(cl(w)\) are traversed. Therefore \(sub(u,k)\) is computed as follows. * If \(k=1\): the corresponding node for \(sub(u,k)\) is contained in both \(cl(v)\) and \(cl(w)\), and it holds \(sub(u,k)=sub(v,1)=sub(w,1)\). * If \(2\leq k\leq C(v)\): the corresponding node for \(sub(u,k)\) is in \(cl(v)\), and it holds \(sub(u,k)=sub(v,k)\). * If \(C(v)+1\leq k\leq C(v)+C(w)-1\): the corresponding node for \(sub(u,k)\) is in \(cl(w)\), and it holds \(sub(u,k)=sub(w,k-C(v)+1)\). This function can be computed if the cluster size \(C(\cdot)\) is known for each vertex of the top DAG. Finally, if \(u\) is a vertex corresponding to vertical merge, define \(v\), \(w\), \(cl(u)\), \(cl(v)\), \(cl(w)\), \(C(u)\), \(C(v)\), \(C(w)\) similarly to the horizontal merge case. We need another value \(D(v)\), which is the preorder id of the bottom boundary of \(cl(v)\). If we traverse nodes of \(cl(u)\) in preorder, we first visit nodes of \(cl(v)\) with local preorder id up to \(D(v)\), then visit all nodes of \(cl(w)\), then finally visit nodes of \(cl(v)\) with local preorder id from \(D(v)+1\). Therefore \(sub(u,k)\) is computed as follows. * If \(1\leq k\leq D(v)-1\): the corresponding node for \(sub(u,k)\) is in \(cl(v)\), and it holds \(sub(u,k)=sub(v,k)\).