# Storing Set Families More Compactly with Top ZDDs
## 4 Top ZDD
### Operations on Top ZDDs
Using the function \(\textit{size}(x^{\prime})\), we can compute a recursive function similar to Algorithm 1. Instead of \(D(\cdot)\) in Algorithm 1, we use _preorder_diff_. When we arrive at a dummy leaf, we use a value in \(\textit{dst\_dummy}\) to move to the corresponding internal vertex of \(T^{\prime}\) and restart the recursive computation. Then for the vertex of the original ZDD whose preorder id in \(T\) is \(x\), we can obtain the leaf of \(T^{\prime}\) corresponding to the cluster of a single edge containing \(x\). To compute \(\ell(x)\), we traverse the path from the root of \(T^{\prime}\) to the leaf corresponding to the cluster containing \(x\). First we set \(s=1\). During the traversal, if the current vertex is for vertical merge and the next vertex is its right child, that is, the next cluster is in the bottom, we add the _label_diff_ value of the top cluster to \(s\). The index of _label_diff_ is computed from \(B_{H}\) and \(bp\). When we reach the leaf \(p^{\prime}\) of \(T^{\prime}\), if \(x\) is its top boundary node, it holds \(\ell(x)=s\), otherwise, let \(k=leaf\_rank(p^{\prime})\), then we obtain \(\ell(x)=s+\textit{label\_span}[k-\textit{rank}_{1}(B_{dummy},k)]\). Because each operation is done in constant time and the height of the top DAG is \(\mathrm{O}(\log n)\), \(\ell(x)\) is computed in \(\mathrm{O}(\log n)\) time. Next, we show how to compute \(y=\textit{zero}(x)\). We can compute \(\textit{one}(x)\) in a similar way. We do a recursive computation as operations on top DAG, a difference is how to process complement edges. There are two cases: if the 0-edge from \(x\) is in the spanning tree or not. If the 0-edge from \(x\) is in the spanning tree, the edge is stored in a cluster with a single edge \((x,y)\). The top boundary node of such a cluster is \(x\). Therefore we search clusters whose top boundary node is \(x\). If the 0-edge from \(x\) is not in the spanning tree, it is a complement edge and it is stored in some vertex on the path from a cluster \(C\) with a single edge whose bottom boundary node is \(x\) to the root. Therefore we search for \(C\). First, we recursively find a non-dummy leaf of \(T^{\prime}\) whose top boundary node is \(x\). During this process, if there is a vertex whose top boundary is \(x\) and its cluster contains more than one edge and corresponds to horizontal merge, we move to the left child, because the 0-edge from \(x\) must exist in the left cluster. If we find a non-dummy leaf of \(T^{\prime}\) which corresponds to a cluster with a single edge and its top boundary node is \(x\), its bottom boundary node is \(y=\textit{zero}(x)\). We climb up the tree until the root to compute the global preorder id of \(y\). If there does not exist such a leaf, the 0-edge from \(x\) is not in the spanning tree. We find a cluster with a single edge whose bottom boundary node is \(x\). From the definition of the top ZDD, the 0-edge from \(x\) is stored in some vertices visited during the traversal. Because complement edges stored in a cluster are sorted in local preorder ids inside the cluster of starting points, we can check if there exists a 0-edge whose starting point is \(x\) in \(\mathrm{O}(\log n)\) time. If it exists, we obtain the local preorder id of \(y\) inside the cluster. By going back to the root, we obtain the global preorder id of \(y\). Note that complement edges for all clusters are stored in one array, and therefore we need to obtain the interval of indices of the array corresponding to a cluster. This can be done using \(B_{edge}\). In the worst case, we perform a binary search in each cluster on the search path. Therefore the time complexity of \(zero(x)\) is \(\mathrm{O}(\log^{2}n)\).