]> ZDDs - Melding ZDDs

Melding ZDDs

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

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=ε (represented by the single node ) and F,ε (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 by following the LO branch every time: G bubbles down from the root of F along dotted lines and then attaches itself to the ZDD with a dotted line.

Consider the case when both F and G contain more than one node, that is, neither is the empty or unit family. Suppose they both have a root node labelled v for some v[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 G 0 and H 1 =F 1 G 1 .

This argument holds for any binary operation f that distributes over union satisfying f(F,G)FG, namely the output lies within the union of the inputs. This ensures we can compute f by solving two subproblems, one involving only sets of the families containing a particular element v, and the other involving only those not containing v.

Thus the only case requiring deeper investigation is when F and G have root nodes with differing integer labels. Suppose F has root node with label v and G has root node with label w, and v<w. Let F 0 ,F 1 be the LO and HI children of v respectively.

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

meld3.png

where H=F 0 G. Hence G "bubbles down the dotted line" whenever w>v. Compare with the special case we discussed earlier, which we can accommodate by defining to be larger than every integer.

Thus 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 , and we avoid duplicating any nodes.

As FG,FG,FG all lie within FG, for these operations the above arguments apply when F,G have root nodes with the same label. Similarly, the "bubble-down" argument still holds 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 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>w is symmetric except for the asymmetric difference operation. We have FG=FG 0 in this case.

Let us summarize the nonterminal cases. Let be one of ,,,. 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 FG is recursively defined by:

meld4.png

where H 0 =F 0 G 0 ,H 1 =F 1 G 1 .

When v<w, let H=F 0 G. If = then FG=H, otherwise FG is:

meld5.png

Lastly, when v>w the cases are symmetric except when =, whence FG=FG 0 .

TODO: computing the join, meet, ….