# Storing Set Families More Compactly with Top ZDDs
## 4 Top ZDD
### Operations on Top ZDDs  
We give algorithms for supporting operations on the original ZDD using the top ZDD. We consider the following three basic operations. We identify each node \(x\) of the ZDD by its preorder id in the spanning tree \(T\) used to construct the top ZDD. An example of ZDD nodal numbering based on this rule is shown in the upper left corner of Figure 9.  
* \(\ell(x)\): returns the label of a branching node \(x\). * \(zero(x)\): returns the preorder id of the node pointed to by the 0-edge of \(x\) or returns \(\bot\) or \(\top\) if the node is a terminal. * \(one(x)\): returns the preorder id of the node pointed to by the 1-edge of \(x\) or returns \(\bot\) or \(\top\) if the node is a terminal. We show \(\ell(x)\) is done in \(\mathrm{O}(\log n)\) time and other operations are done in \(\mathrm{O}(\log^{2}n)\) time where \(n\) is the number of nodes of the ZDD. Below we denote the vertex of \(T^{\prime}\) stored in the top ZDD with preorder id \(x\) by \"vertex \(x\) of \(T^{\prime\prime}\)\". First we explain how to compute \(\ell(x)\) in \(\mathrm{O}(\log n)\) time. We can compute \(\ell(x)\) recursively using an algorithm similar to those on the top DAG. A difference is that in Section 3.2.2 we assumed that each vertex of the top DAG stores the cluster size, while in the top ZDD it is not stored to reduce the space requirement. Therefore we have to compute it using the information in Table 1.  
To work the recursive computation, we need to compute the cluster size \(size(x^{\prime})\) represented by vertex \(x^{\prime}\) of \(T^{\prime}\) efficiently. We can compute \(size(x^{\prime})\) by the number of non-dummy leaves in the subtree of \(T^{\prime}\) rooted at \(x^{\prime}\), and the sizes of the clusters corresponding to dummy leaves in the subtree rooted at \(x^{\prime}\). If we merge two clusters of size \(a\) and \(b\), the resulting cluster has size \(a+b-1\). Therefore if we merge \(k\) clusters whose total size is \(S\), the resulting cluster after \(k-1\) merges has size \(S-k+1\). These values can be computed from the BP sequence \(bp\) of \(T^{\prime}\), the array _clsize_, and the bit vector \(B_{dummy}\). By using \(bp\), we can compute the interval \([l,r]\) of leaf ranks in the subtree rooted at \(x^{\prime}\). Then, using \(B_{dummy}\)  
Figure 10: A top ZDD with \(\mathrm{O}(\log n)\) vertices, where \(n=2^{m}\). We omitted the middle of the graph by dots, but the height differs exponentially. In this ZDD, the spanning tree is a path consisting only of 0-edges, represented in red. The complement edges are indicated in green. In the top ZDD, the cluster corresponding to each node is shown in a smaller size next to it. we can find the number \(c\) of non-dummy leaves and the interval \([l^{\prime},r^{\prime}]\) of non-dummy leaf ranks, in the subtree of \(x^{\prime}\). Because _clsize_ is the array for storing cumulative sums of cluster sizes for dummy leaves, the summation of sizes of clusters corresponding to \(l^{\prime}\)-th to \(r^{\prime}\)-th dummy leaves is obtained from \(\textit{clsize}[r^{\prime}]-\textit{clsize}[l^{\prime}-1]\). Since the size of a cluster for a non-dummy leaf is always 2, the summation of cluster sizes for non-dummy leaves is also obtained. Algorithm 2 gives a pseudo-code for computing \(\textit{size}(x^{\prime})\). This can be done in constant time. ```
0: Preorder \(x^{\prime}\)
0: The size of the cluster for \(x^{\prime}\)
1:\(l\gets leaf\_rank(\textit{leftmost\_leaf}(x))\)
2:\(r\gets leaf\_rank(\textit{rightmost\_leaf}(x))\)
3:\(l^{\prime}\leftarrow\textit{rank}_{1}(B_{dummy},l-1)+1\)
4:\(r^{\prime}\leftarrow\textit{rank}_{1}(B_{dummy},r)\)
5:\(k\gets r-l+1\)
6:\(c\leftarrow(r-l+1)-(r^{\prime}-l^{\prime})\)
7:if\(l^{\prime}=0\)then
8:return\(\textit{clsize}[r^{\prime}]+2c-k\)
9:else
10:return\(\textit{clsize}[r^{\prime}]-\textit{clsize}[l^{\prime}-1]+2c-k\)
```  
**Algorithm 2**\(\textit{size}(x^{\prime})\): the size of the cluster corresponding to vertex \(x^{\prime}\) of \(T^{\prime}\).