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:

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:

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:

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:

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:

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.

Ben Lynn blynn@cs.stanford.edu 💡