# Storing Set Families More Compactly with Top ZDDs
## 3 Top Tree and Top DAG
### Top DAG Compression
#### 3.2.1 Top Tree  
The top tree [21] for a labelled rooted tree \(T\) is a binary tree \(\mathcal{T}\) representing the merging process of clusters of \(T\) defined as follows. A top tree is a meta-binary tree for managing tree structure, and its purpose is to transform a given tree into a somewhat balanced binary tree. We assume that all edges in the tree are directed from the root towards leaves, and an edge \((u,v)\) denotes the edge from node \(u\) to node \(v\). Clusters are subsets of \(T\) with the following properties.  
* A cluster is a subset \(F\) of the nodes of the original tree \(T\) such that nodes in \(F\) are connected in \(T\).
* \(F\) forms a tree and we regard the node in \(F\) closest to the root of \(T\) as the root of the tree. We call the root of \(F\) as the _top boundary node_.
* \(F\) contains at most one node having directed edges to outside of \(F\). If there is such a node, it is called the _bottom boundary node_. A boundary node is either a top boundary node or a bottom boundary node. By merging two adjacent clusters, we obtain a new cluster, where merge means to take the union of node sets of two clusters and make it the node-set of the new cluster. There are five types of merges, as shown in Figure 5. In the figure, ellipses are clusters before merge, black circles are boundary nodes of new clusters, and white circles are not boundary nodes in new clusters.  
Figure 4: An example of DAG compression. Dashed lines are 0-edges, and solid lines are 1-edges. Leaves of the same colour represent the identical subtrees.  
Each leaf of the top tree corresponds to a cluster with the endpoints of an edge of \(T\).
* Each internal vertex of the top tree corresponds to the cluster made by merging the clusters of its two children. This merge is one of the five types in Figure 5.
* The cluster of the root of the top tree is \(T\) itself.  
Figure 8 is an example of the top tree \(\mathcal{T}\) for an unlabeled tree \(T\).  
\(V\) and \(H\) in vertices of the top tree represent vertical and horizontal merges, respectively. Letters on the right of vertices show the type of merges in Figure 5. Clusters corresponding to vertices of the top tree are also shown. Red nodes show boundary nodes of clusters.  
We call the DAG obtained by DAG compression of the top tree \(\mathcal{T}\) as top DAG \(\mathcal{T}D\), and the operation to compute the top DAG \(\mathcal{T}D\) from tree \(T\) is called top DAG compression [12].  
We define labels of vertices in the top tree to apply DAG compression as follows. For a leaf of the top tree, we define its label as the pair of labels of two endpoints of the corresponding edge in \(T\). For an internal vertex of the top tree, its label must have information about cluster merge. It is enough to consider three types of merges, not five as in Figure 5. For vertical merges, it is not necessary to store the information that the merged cluster has a bottom boundary node or not. For horizontal merges, it is enough to store if the left cluster has a bottom boundary node or not. From this observation, we define labels of internal vertices as follows.  
* For vertices corresponding to vertical merge: we set their labels as V.
* For vertices corresponding to horizontal merge: we set their labels as \(\mathrm{H}_{\mathrm{L}}\) if the left child cluster has the bottom boundary node, or \(\mathrm{H}_{\mathrm{R}}\) if the right child cluster has the bottom boundary node. If both children do not have bottom boundary nodes, the label can be arbitrary.  
Top trees created by a greedy algorithm satisfy the following.  
**Theorem 4**.: ([12]) _Let \(n\) be the number of nodes of a tree \(T\). Then the height of top tree \(\mathcal{T}\) created by a greedy algorithm is \(\mathrm{O}(\log n)\)._