Melding ZDDs

Let $F, G$ be ZDDs in the same universe $U = \{1,...,n\}$. How do we construct their union, $F \cup G$?

Case 1: If one family is the empty or unit family then the question is easy, and these special cases also hint at the general solution. In particular, if $G = \epsilon$ (represented by the single node $\top$) and $F \ne \emptyset$ and $F \ne \epsilon$ (so $F$ contains a nonterminal node) then, if it does not already exist, we add a dotted edge so that we can travel from the root of $F$ to the $\top$ by following the LO branch every time. In other words, we start from the root of $F$, follow dotted lines as far as possible, and then either do nothing if we end up at $\top$ or reroute the last dotted line we followed to $\top$.

Case 2: Suppose both $F$ and $G$ have a root node labelled $v$ for some $v \in [1..n]$. Let $F_0, F_1$ be the ZDDs on the LO and HI edges respectively. Define $G_0, G_1$ similarly:

meld1.png

Recall $F_0, F_1$ partition the families of sets of $F$ on whether they contain $v$ or not, and similarly for $G_0, G_1$, hence our solution must be:

meld2.png

where we recursively find $H_0 = F_0 \cup G_0$ and $H_1 = F_1 \cup G_1$.

Case 3: Suppose $F$ has root node $v$ and $G$ has root node $w$, and $v \lt w$. Let $F_0, F_1$ be the LO and HI children of the root node of $F$ respectively.

Now $w$ is the smallest integer contained in any set of $G$, hence no set in $G$ contains $v$. Thus $F \cup G$ is:

meld3.png

where $H = F_0 \cup G$. Just like the easy special case $G = \epsilon$, whenever $w \gt v$, we do nothing but follow the dotted line. In fact, by defining $\top$ to be larger than every integer, we see how this special case is related.

We have described all cases of a top-down recursive algorithm for constructing the union of any two families. Observe we avoid creating nodes whose HI edges point to $\bot$, and we avoid duplicating any nodes.

The above arguments hold for any binary operation $\diamond$ that distributes over union satisfying $F \diamond G \subseteq F \cup G$, namely the output lies within the union of the inputs.

As $F\cap G, F \setminus G , F\oplus G$ all lie within $F\cup G$, for these operations the above arguments apply when $F, G$ have root nodes with the same label. Similarly, we do nothing but follow the dotted line when the root $w$ of $G$ is greater than the root $v$ of $F$. The only difference is in the handling of $F_1$. For intersections, since this represents the sets of $F$ containing $v$ and since no set in $G$ contains $v$, we lop off the entire branch leaving only the ZDD $F_0\cap G$. For the difference and symmetric difference, as in the union, we leave $F_1$ intact as it represents sets of $F$ not present in $G$.

One more wrinkle: the case $v \gt w$ is symmetric except for the asymmetric difference operation. We have $F\setminus G = F \setminus G_0$ in this case.

Let us summarize the nonterminal cases. Let $\diamond$ be one of $\cup, \cap, \setminus, \oplus$. We reuse the above notation, that is, $F, G$ are nontrivial ZDDs with roots labelled $v, w$ respectively, and $F_0, F_1$ are the LO and HI children of $v$ respectively and $G_0, G_1$ are similarly defined.

When $v = w$, then $F \diamond G$ is recursively defined by:

meld4.png

where $H_0 = F_0 \diamond G_0, H_1 = F_1 \diamond G_1$.

When $v \lt w$, let $H = F_0 \diamond G$. If $\diamond = \cap$ then $F \cap G = H$, otherwise $F \diamond G$ is:

meld5.png

Lastly, when $v \gt w$ the cases are symmetric except when $\diamond = \setminus$, whence $F \setminus G = F \setminus G_0$.

Join, meet, and other operations are less straightforward. Let us investigate the join operation. Suppose we wish to compute $H = F \sqcup G$ where $F$ and $G$ have the same label. Again, denoting the LO and HI children with 0 and 1 subscripts, we have:

  • $H_0 = F_0 \sqcup G_0$

  • $H_1 = (F_0 \sqcup G_1) \cup (F_1 \sqcup G_0) \cup (F_1 \sqcup G_1)$

which lead to algorithms similar to the above, except the $H_1$ recursion branches out and can be computed in different ways. By distributivity:

$H_1 = ((F_0 \cup F_1) \sqcup G_1) \cup (F_1 \sqcup G_0) = (F_1 \sqcup (G_0 \cup G_1)) \cup (F_0 \sqcup G_1)$

Thus we have 3 methods to compute $H_1$. Depending on the inputs, one alternative may significantly outperform the others.