CUDD C++ Interface for converting Booleans to BDDs and resulting set of minterms (to cutsets)

Question

I'm working with (https://github.com/ivmai/cudd) with the goal of the following repetitive process:

(1) Input: (Coherent, non-decreasing) Boolean function expression top = a_1a_2a_3...+ x_1x_2x_3... + z_1z_2z_3...). The Booleans I'm working with have thousands of vars (ai...zj) and hundreds of terms.

(2) Processing: Convert Boolean to a BDD to simplify the calculation of the minterms, or mutually exclusive cut-sets (as we call them in the Reliability world).

(3) Output: Take the set of m.e. minimal cutsets (minterms). Calculate the top event probability by adding up all the minterms found in (2).

I've found a way to do this with a labor-intensive manual C interface to build the Boolean. I've also found how to do it with the excellent tulip-dd Py interface, but unable to make it scale as with cudd.

Now I'm hoping with the C++ interface to cudd I can get the best of both worlds (Am I asking for too much?) Namely, the convenience of say tulip-dd with the scalability of cudd. So here's some sample code. Where I'm failing is in step 3, printing out the minterms, which I used to be able to do in C. How do I do it with the C++ interface?! Please see comments in the code for my specific thoughts and attempts.

int main()
{ 


/*DdManager* gbm; /* Global BDD manager. I suppose we do not use this if we use the Cudd type below.*/

/* (1-2) Declare the vars and build the Boolean. Convert Boolean to BDD */
    
    Cudd mgr(0, 0);
    BDD a = mgr.bddVar();
    BDD b = mgr.bddVar();
    BDD c = mgr.bddVar();
    BDD d = mgr.bddVar();
    BDD e = mgr.bddVar();
    BDD top = a*(b + c + d*e);

/* How to print out the equivalent to below, which prints out all minterms and their relevant vars in C. 
But the mgr below has to be a *DManager ? If so, how to convert? */

    Cudd_PrintDebug(mgr, BDD, 2, 4); 
    return 0 
}

Thanks, Gui

Answer 1

The CUDD C++ classes are very little more than a wrapper around the "DdManager*" and "DdNode*" data types. They make sure that you don't accidentally forget to Cudd_Ref(..) or Cudd_RecursiveDeref(...) *DD nodes that you are using.

As such, these classes have functions that you can use to access the underlying data types. So for instance, if you want to call the "Cudd_PrintDebug" function on the "top" BDD, then you can do that with:

    Cudd_PrintDebug(mgr.getManager(), top.getNode(), 2, 4); 

The modification to your code was minimal.

Note that when using a plain CUDD DdNode* that you obtain with the "getNode" function, you have to make sure manually that you don't introduce node count leaks. If you use the DdNodes in a "read only fashion", only store DdNode* that correspond to BDD objects that you also store, and make sure that the BDD objects always live longer than the DdNode* pointers, this does not happen, though. I'm only mentioning this since at some point you may want to iterate through the cubes of a BDD. These are essentially not-guaranteed-to-be-minimal minterms. There are special iterators in CUDD for this. However, if you really want the minterms, this may not be right approach. There is other software using CUDD that comes with its own functions for enumerating the minterms.

As a final note (outside of the scope of StackOverflow), you wrote that "The Booleans I'm working with have thousands of vars (ai...zj) and hundreds of terms." - There is no guarantee that using BDDs with so many variables is the way to go here. But please try it out. Having thousands of variables is often problematic for BDD-based approaches. Your application may or may not be an exception to this observation. An alternative approach may be to encode the search problem for all minterms of your original expression as an incremental satisfiability (SAT) solving problem.