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:

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.