algorithmdata-structuresimplementationboolean-logicbinary-decision-diagram

How to efficiently implement binary decision diagrams (BDD)?

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?

Solution

  • 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.