#bdd #diagram #anf

bin+lib bex

A rust library for working with boolean expressions (syntax trees, decision diagrams, algebraic normal form, etc.)

5 releases

new 0.1.4 Jul 13, 2020
0.1.3 Sep 25, 2019
0.1.2 Dec 17, 2018
0.1.1 Dec 17, 2018
0.1.0 Nov 30, 2018

#318 in Data structures

MIT license

165KB
3K SLoC

Rust 2.5K SLoC // 0.2% comments Vue 533 SLoC // 0.0% comments

bex

A rust library for working with boolean expressions (expression trees, decision diagrams, etc.)

This crate lets you build a complicated abstract syntax tree (or logic circuit schematic, if you prefer) by working with individual Bit structs, or vectors that act like integers. You can also solve these AST structures by converting them into reduced, ordered, binary decision diagrams (ROBDDs) - a normal form consisting of if-then-else triples that essentially act like compressed truth tables. You can also construct and manipulate BDDs directly.

Changes in 0.1.4

This version introduces the ANFBase for working with algebraic normal form using a BDD-like graph structure. This version also introduces Cursors, which provide the ability to iterate through BDD solutions and ANF terms.

It also includes a major refactoring effort: the BDD, AST, and ANF bases now all use the same NID/VID types for node and variable identifiers.

Finally, BDD and ANF graphs are now arranged so that variables with the smallest identifiers now appear at the bottom (so that subgraphs are more likely to be shared across functions with different numbers of inputs, and also so that the size of a node's truth table is immediately apparent from its topmost variable.)

For more detail on these and other changes, see CHANGELOG.md.

Dependencies

~2–2.8MB
~54K SLoC