A toy problem

Suppose we have some apples, bananas and cherries, and we are planning what to eat on the weekend. Let’s start with no constraints, so we can choose to eat nothing both days, or eat all three kinds of fruit on both days. How many different kinds of diets are there?

We translate this to a ZDD problem as follows. Let \(a_1, b_1, c_1\) represent eating apples, bananas, cherries, respectively, on Saturday and define \(a_2, b_2, c_2\) similarly for Sunday. Let us order these symbols \(a_1, b_1, c_1, a_2, b_2, c_2\), and number them 1 to 6. We can then use sets of this universe to represent our diet. For example \(\{a_1, c_1, b_2\} = \{1, 3, 5\}\) means we eat apples and cherries on Saturday, and bananas on Sunday.

With no constraints, every set is a valid diet. The ZDD representing this is:

toy1.png

Our counting algorithm (at each node, we sum the counts of its children where \(\top\) has count 1) gives \(2^6 = 64\) different diets. We have 7 nodes; if we used bit fields to represent each possible diet we would need 64 7-bit strings.

Suppose we restrict ourselves to exactly two types of fruit on Saturday. Then we have the ZDD:

toy2.png

The counting algorithm gives 24 possible diets.

Let us change the restriction to eating exactly one kind of fruit on Sunday:

toy3.png

The counting algorithm again gives 24 possible diets.

If we give weights \(x, y, z\) to apples, bananas and cherries respectively, we can compute the mean weight of all solutions by reading the graph from the bottom up. At node 6, we have 1 solution of weight \(z\). This propagates up to node 5, where we also gain 1 solution of weight \(y\), so we pass up 2 solutions of mean weight \((y + z)/2\) to node 4. Here, we gain 1 solution of weight \(x\), so we have 3 solutions with mean

\[ (2 \cdot (y + z) / 2 + 1 \cdot x) / 3 = (x + y + z)/3 .\]

As we move up to node 3, one of the paths gains an additional \(z\), thus at 3 we have 6 solutions with mean:

\[ (3 \cdot (x + y + z)/3 + 3 \cdot ((x + y + z) / 3) + z))/6 = (2x + 2y + 5z)/6 \]

Continuing in this manner, at node 2 we get 12 solutions with mean weight \((2x + 5y + 5z)/6\), and finally, at node 1 we find the mean of all 24 solutions is \((2x + 2y + 2z)/3\).

The ZDD that represents the number of different diets if we eat exactly two kinds of fruit on Saturday and exactly one kind on Sunday is the intersection of the two families:

toy4.png

The counting algorithm gives 9 possible diets.

Given a solution such as \(\{1, 3, 5\}\) we can find the next (lexicographically largest) solution by traversing the ZDD in the same manner we would find a successor to a leaf node in a binary tree (exercise). In short, we follow the path representing our set, then travel up the edges. As soon as we travel along a dotted edge, we reverse direction, and go down the solid edge, then always take the dotted edge if it does not point to \(\bot\), and take the solid edge otherwise. Eventually we reach \(\top\) again. The set represented by this path is the next solution. In our example we travel up from \(\top\) to \(5\) to \(4\), then down the solid edge to \(\top\) giving the answer \(\{1, 3, 4\}\). If we repeat, we now go from \(\top\) to \(4\) to \(3\) to \(2\), then down to \(4\), \(5\), \(6\) then \(\top\) which represents the set \(\{1, 2, 6\}\).

Let’s do one more example. This time, the only restriction is that we must eat apples one day, and not the other. This has the ZDD:

toy5.png

In our tiny example, intersections of families can easily be computed by hand. In general, however, we want an algorithm to compute the intersection of two ZDDs, and similarly for the union, set difference, symmetric difference and so on.


Ben Lynn blynn@cs.stanford.edu 💡