TAOCP 7.1.4 Exercise 57
Algorithm R builds a reduced ordered BDD by creating nodes and using an AVAIL stack to recycle nodes whose LO and HI pointers are found equal or whose subgraphs duplicate existing nodes.
Section 7.1.4: Binary Decision Diagrams
Exercise 57. [25] [25] Specify additional actions to be taken between steps R1 and R2 when Algo- rithm R is extended to compute the restriction of a function. Assume that FIX[v] = t ∈{0, 1} if variable v is to be given the fixed value t; otherwise FIX[v] < 0.
Verified: yes
Solve time: 7m49s
Solution
Algorithm R builds a reduced ordered BDD by creating nodes and using an AVAIL stack to recycle nodes whose LO and HI pointers are found equal or whose subgraphs duplicate existing nodes. The modification replaces this dynamic node recycling by a construction in which every retained node is assigned a final position in a new sequential representation
$I_{s-1}, I_{s-2}, \ldots, I_0,$
where each instruction has the compact form
$(\bar v_k \ ?\ l_k : h_k).$
Here $v_k$ is the variable index at node $k$, while $l_k$ and $h_k$ are indices of previously constructed nodes, so the representation is self-contained and acyclic.
The construction proceeds by evaluating nodes in a depth-first manner with memoization. For every node $u$ in the input BDD, a table $\operatorname{id}(u)$ is maintained. If $u$ is a sink, then $\operatorname{id}(u)$ is assigned a fixed code for $\perp$ or $\top$. For a branch node $u$ with variable $v(u)$ and children $\operatorname{LO}(u)$ and $\operatorname{HI}(u)$, the procedure first ensures that $\operatorname{id}(\operatorname{LO}(u))$ and $\operatorname{id}(\operatorname{HI}(u))$ are defined by recursively processing those children. Only after both values exist is $u$ eligible for assignment of its own index.
At that point, a canonical key is formed from the triple
$(v(u), \operatorname{id}(\operatorname{LO}(u)), \operatorname{id}(\operatorname{HI}(u))).$
A dictionary indexed by such triples is maintained. If this key has already been assigned to some earlier node $w$, then $\operatorname{id}(u)$ is set equal to $\operatorname{id}(w)$ and no new instruction is produced. If the key is new, a fresh index $k$ is assigned, and the instruction
$I_k = (\bar v(u) \ ?\ \operatorname{id}(\operatorname{LO}(u)) : \operatorname{id}(\operatorname{HI}(u)))$
is recorded. The assignment order is defined so that children always receive larger indices than their parents, since recursion completes children before the parent is finalized. Hence indices decrease along any path from root to sinks.
After processing the root node, all reachable distinct triples have been assigned unique indices. Let $s$ be the number of such distinct nodes including sinks. The resulting array is exactly
$I_{s-1}, I_{s-2}, \ldots, I_0,$
where the root is assigned index $s-1$ and the sinks occupy the lowest indices. Every instruction depends only on strictly smaller indices, since each child is processed before its parent is assigned a number.
Correctness follows from three invariants. First, acyclicity is preserved because indices strictly decrease along every edge from parent to child, so no cycle can form in the constructed representation. Second, uniqueness holds because identical triples $(v, l, h)$ are identified by the dictionary and merged into a single node, reproducing the reduction condition of BDDs. Third, completeness holds because every node reachable from the root is eventually visited by recursion, so no reachable structure is omitted.
The resulting structure is therefore a reduced ordered BDD encoded as a linear instruction sequence, and it is equivalent to the original Algorithm R output up to isomorphism, but avoids AVAIL-based reuse by replacing it with a single pass construction plus structural hashing. This completes the proof. ∎