Skip to content

0.4.2

Compare
Choose a tag to compare
@daemontus daemontus released this 05 Dec 19:13
· 109 commits to master since this release

This version mostly introduces additional low level helper methods. This should not break anything, and it also shouldn't really introduce anything that you need for "normal" use cases.

  • Added Bdd::check_binary_op and Bdd::check_fused_binary_flip_op methods. These operations perform a "dry run" of a particular BDD operation, such that from the result we learn (a) if the resulting BDD would have been empty; (b) approximate number of "steps" needed to compute this BDD. Importantly, this should be faster than running the operation in question (as fewer data structures are needed). This method is useful when comparing the complexity of two operations.
  • Added Bdd::binary_op_with_limit and Bdd::fused_binary_flip_op_with_limit methods. These methods execute a standard BDD operation, but safely fail (with None) if the number of nodes in the resulting Bdd exceeds a certain threshold. Using this approach, you can implement an imperfect memory limit for BDD operations. For example, if you suspect that a particular operation might "explode", but you wan't to avoid killing your program because of it, you can first test it with some reasonable size limit (e.g. 2*max(left.size(), right.size())). Also, by setting limit=1, you can implement a very fast test for emptiness of the resulting BDD (even faster than check_binary_op), as the operation will return None as soon as any new BDD node is created.
  • Added Bdd::support_set which computes the set of BddVariable objects that actually appear in the decision nodes of the BDD.
  • Added Bdd::size_per_variable which computes a map that breaks down how individual BDD variables contribute to the size of the BDD.
  • A bugfix and a faster algorithm for computing Bdd::necessary_clause.