CODEWITHSUNDEEP
javabinary-decision-diagram
rozi
rozi

Reputation: 166

JavaBDD sat count with subset of variables

I am using JavaBDD to do some computation with BDDs. I have a very large BDD with many variables and I want to calculate how many ways it can be satisfied with a small subset of those variables.

My current attempt looks like this:

// var 1,2,3 are BDDVarSets with 1 variable.
BDDVarSet union = var1;
union = union.union(var2);
union = union.union(var3);

BDD varSet restOfVars = allVars.minus(union);
BDD result = largeBdd.exist(restOfVars);

double sats = result.satCount(); // Returns a very large number (way too large).
double partSats = result.satCount(union) // Returns an inccorrect number. It is documented that this should not work.

Is the usage of exist() incorrect?

Upvotes: 1

Views: 83

Answers (1)

rozi
rozi

Reputation: 166

After a bit of playing around I understood what my problem was.

double partSats = result.satCount(union);

Does return the correct answer. What it does is calculate how many possible solutions there are, and divides the solution by 2^(#vars in set).

The reason I thought satCount(union) does not work is due to an incorrect usage of exist() somewhere else in the code.

Here is the implementation of satCound(varSet) for reference:

  /**
   * <p>Calculates the number of satisfying variable assignments to the variables
   * in the given varset.  ASSUMES THAT THE BDD DOES NOT HAVE ANY ASSIGNMENTS TO
   * VARIABLES THAT ARE NOT IN VARSET.  You will need to quantify out the other
   * variables first.</p>
   * 
   * <p>Compare to bdd_satcountset.</p>
   * 
   * @return the number of satisfying variable assignments
   */
  public double satCount(BDDVarSet varset) {
    BDDFactory factory = getFactory();

    if (varset.isEmpty() || isZero()) /* empty set */
      return 0.;

    double unused = factory.varNum();
    unused -= varset.size();
    unused = satCount() / Math.pow(2.0, unused);

    return unused >= 1.0 ? unused : 1.0;
  }

Upvotes: 0

Related Questions