Intersection of two BDDs using CUDD

Question

I would like to find intersection of two BDDs for the following two Boolean functions:

F=A'B'C'D'=1
G=A XOR B XOR C XOR D=1

Here is my code:

 int main (int argc, char *argv[])
    {
        char filename[30];
        DdManager *gbm; /* Global BDD manager. */
        gbm = Cudd_Init(0,0,CUDD_UNIQUE_SLOTS,CUDD_CACHE_SLOTS,0); /* Initialize a new BDD manager. */
        DdNode *bdd, *var, *tmp_neg, *tmp,*f,*g;
        int i;
        bdd = Cudd_ReadOne(gbm); /*Returns the logic one constant of the manager*/
        Cudd_Ref(bdd); /*Increases the reference count of a node*/

        for (i = 3; i >= 0; i--) {
          var = Cudd_bddIthVar(gbm,i); /*Create a new BDD variable*/
          tmp_neg = Cudd_Not(var); /*Perform NOT Boolean operation*/
          tmp = Cudd_bddAnd(gbm, tmp_neg, bdd); /*Perform AND Boolean operation*/
          Cudd_Ref(tmp);
          Cudd_RecursiveDeref(gbm,bdd);
          f = tmp;
        }

        for (i = 3; i >= 0; i--) {
          var = Cudd_bddIthVar(gbm,i); /*Create a new BDD variable*/
          tmp = Cudd_bddXor(gbm, var, bdd); /*Perform AND Boolean operation*/
          Cudd_Ref(tmp);
          Cudd_RecursiveDeref(gbm,bdd);
          g = tmp;
        }
        bdd= Cudd_bddIntersect(gbm,f,g);/*Intersection between F and G */
        bdd = Cudd_BddToAdd(gbm, bdd); /*Convert BDD to ADD for display purpose*/
    print_dd (gbm, bdd, 2,4); /*Print the dd to standard output*/
    sprintf(filename, "./bdd/graph.dot"); /*Write .dot filename to a string*/
    write_dd(gbm, bdd, filename);  /*Write the resulting cascade dd to a file*/
    Cudd_Quit(gbm);
    return 0; 
}

And here is the result I got:

DdManager nodes: 7 | DdManager vars: 4 | DdManager reorderings: 0 | DdManager memory: 8949888 
: 3 nodes 2 leaves 2 minterms
ID =  0xaa40f   index = 0   T = 0           E =  1        

0---  1

As you can see here the intersection gives A=0 and don't cares for B,C and D. I was expecting values of A,B,C and D that satifies both F and G. But clearly A=0 is not the solution for both F and G. For example someone can choose A=0,B=1 which gives 0 for function F. What is wrong here?

Answer 1

This reply comes awfully late, but just to close the issue, the problem is that the last operand to both Cudd_bddAnd and Cudd_bddXor is bdd instead of f or g. Of course, both f and g should be properly initialized (the way bdd is currently initialized). Fixing the code this way will also take care of the multiple dereferences of bdd, which are going to cause grief should garbage collection kick in.

Also, Cudd_bddIntersect does not compute the AND of two BDDs, but a function that implies the AND. It's used when one wants a witness to the nonemptiness of the conjunction of two BDDs without computing the whole result (and then possibly extracting a witness from it).

Finally, bdd is used as both operand to Cudd_BddToAdd and as destination for the return value. This is guaranteed to "leak" BDD nodes.