How to efficiently implement binary decision diagrams (BDD)?

Question

Background about binary decision diagrams can be found here BDD on wikipedia.

The simplest approach is to build BDT (Binary Decision Tree) and then reduce it due to two rules:
- Merge any isomorphic subgraphs.
- Eliminate any node whose two children are isomorphic.
But there is one major problem BDT can be really huge in comparison to BDD. Is there any way to build BDD without building BDT first?

Answer 1

Use the Mk (make node) and Build (construct BDD) algorithms from Andersen, pp. 16-17. I haven't played with BDDs in a while, but I believe either H or T should be a hash table. Use hash tables for both to be on the safe side.

Answer 2

The way to build the BDD is from the parse tree for the expression representing the Boolean function you are trying to build.

I.e., if you want the BDD for (A+B).(C+D), you first parse (A+B).(C+D) into a tree:

   .
  / \
 +   +
/ \ / \
A B C D

then build the BDD recursively - you need methods that can form the AND and the OR of two BDDS, and the base case (single variable BDD).

This works just as well for logic circuits too (view as a parse DAG instead of tree).

These notes on BDDs explain how to implement AND and OR, also the hashtables that are needed to make things work efficiently: http://bit.ly/cuClGe