Expand description
xDD is a library for binary decision diagrams - either BDD or XDD.
These were largely described by Minato, although this library is designed using Knuth’s notations in “The Art of Computer Programming” volume 4 fascicle 1, “Binary decision diagrams”
The library differs from the BDD library on crates.io in being targetted at combinatorics and having features essential for combinatorics like generating function generation. It also uses external factories for generating xDDs, which improves efficiency for generating structures with lots of reuse which tends to arise in combinatorics. It also supports ZDDs as well as BDDs.
It supports 16 bits for variables and 32 bits for pointers, limiting it to trees of 4 billion nodes. This may be changed in a newer version to a larger number.
Modules
- Implement πDD (as described by S Minato) and Rot-πDD (as described by Y Inoue)
Structs
- A factory that can do efficient operations on BDDs.
- A node in a version of a binary decision tree with optional multiplicity.
- The identifier of a node on the tree (effectively a pointer), along with an associated multiplicity (number of times represented, for a multiset).
- The identifier of a variable. Variable 0 is the highest one in the diagram.
- A factory that can do efficient operations on BDDs.
Traits
- A object that can function as a decision diagram factory, doing stuff quickly.