Reimplement expression trees in C/C++ - Githubissues

cjdrake / pyeda

Python EDA

BSD 2-Clause "Simplified" License

305 stars 55 forks source link

Reimplement expression trees in C/C++ #98

Closed cjdrake closed 9 years ago

cjdrake commented 10 years ago

This is an area that really needs as much performance as possible. Very large Boolean functions (see the AES code) are just too overwhelming for Python to handle.

cjdrake commented 9 years ago

Making some progress here, but still some work to do. Listing some stuff I would like to finish before doing a release.

Must Have:

[x] Simplification
[x] BoolExpr DFS iterator (for support/inputs)
[x] BoolExpr hash table {int: BoolExpr *} (for compose/restrict)
[x] SAT integration, with assumptions
[x] Minimization (Espresso) integration, cube/cover representation
[x] DIMACS conversion
[x] Unicode and LaTeX string conversions
[x] Shannon expansion
[ ] 100% unit test coverage
[x] Tseitin encoding
[x] Equivalence (heuristic)
[ ] Splitting variable (heuristic)
[x] Negation Normal Form
[x] Conjunctive/Disjunctive Normal Form
[x] to_dot graphviz conversion
[x] Complete Sum

Nice to Have:

Canonical CNF/DNF
Algebraic Normal Form (ANF)
Native Majority / Minority operators