# Storing Set Families More Compactly with Top ZDDs
## 4 Top ZDD  
We explain our top ZDD, which is a representation of ZDD by top DAG compression. Though it is easy to apply our compression scheme for general rooted DAGs, we consider the only compression of ZDDs. A ZDD \(G=(V,E)\) is a directed acyclic graph in which branching nodes have labels \(\ell(\cdot)\) and edges have labels 0 or 1. We can regard it as a graph with only edges being labelled. For each edge \((u,v)\) of ZDD \(G\), we define its label as a pair (edge label \(0/1\), \(\ell(v)-\ell(u)\)) if \(v\) is a branching node, or a pair (edge label \(0/1\), \(\bot/\top\)) if \(v\) is a terminal node. Note that in the second case, we are not taking the difference of labels. We only care whether the terminal is \(\top\) or \(\bot\). In practice, we can use \(c+1\) instead of \(\bot\), and \(c+2\) instead of \(\top\) for the second element of the second case. It is enough to distinguish the above two cases because \(\ell(v)-\ell(u)\) is always less than \(c\) for any \(u,v\). Below we assume ZDDs have labels for only edges, and 0-edge comes before 1-edge for each node. Next, we consider top trees for edge-labelled trees. The difference from node-labelled trees is only how to store the information for single edge clusters. In Section 3.2.1, we stored labels for both endpoints of edges. We change this for storing only edge labels. The top ZDD is constructed from a ZDD \(G=(V,E)\) as follows. 1. We perform a depth-first traversal from the root of \(G\) and obtain a spanning tree \(T\) of all branching nodes. During the process, we do not distinguish 0-edges and 1-edges, and terminal nodes are not included in the tree. Nodes of the tree are identified with their preorder ids in \(T\). If we say node \(u\), it means the node in \(T\) with preorder id \(u\). We call edges of \(G\) not included in \(T\) as _complement edges_. 2. We convert the spanning tree \(T\) to a top tree \(\mathcal{T}\) by the greedy algorithm. 3. For each complement edge \((u,v)\), we store its information in a node of \(\mathcal{T}\) as follows. If \(v\) is a terminal, let \(a\) be the vertex of the top tree corresponding to the cluster of a single edge between \(u\) and its parent in \(T\). Note that \(a\) is uniquely determined. Then we store a triple (\((u,v)\), edge label \(0/1\), \(\bot/\top\)) in \(a\). If \(v\) is a branching node, we store the information of the complement edge to a vertex of \(T\) corresponding to a cluster containing both \(u\) and \(v\). The information to store is a triple (\((u,v)\), edge label \(0/1\), \(\ell(u)-\ell(v)\)). Each vertex stores such information as follows. Let \(a,b\) be the vertices of the top tree corresponding to the clusters of single edges towards \(u,v\) in \(T\), respectively. Then we store the triple in the lowest common ancestor \(\operatorname{lca}(a,b)\) in \(T\). Here the information \((u,v)\) represents local preorder ids inside the cluster corresponding to \(\operatorname{lca}(a,b)\). Note that \(\operatorname{lca}(a,b)\) may not be the minimal cluster including both \(u\) and \(v\). 4. We create a top DAG \(\mathcal{T}D\) by DAG compression by sharing identical clusters. To determine the identity of two clusters, we compare them together with the information of complement edges in the clusters stored in step 3. Complement edges that do not appear in multiple clusters are moved to the root of \(T\). Figure 9 shows an example of how our algorithm works. In this figure, we show the clusters corresponding to each node. But, they are not stored explicitly. Figure 9: Running example of the Top ZDD construction algorithm. In each branching node of the original ZDD, its preorder id is denoted instead of its label. Red edges are spanning tree edges and green edges are complement edges. For each vertex of the top tree, the corresponding cluster and the complement edges stored are shown. Boundary nodes of each cluster are denoted as black nodes. It is crucial to choose an appropriate data structure to store each information to achieve smaller space consumption.