How to encode integers in BDD

Question

I implement in Java.

I'm currently trying to use BDDs (binary decision schemes) to store relationships in a data structure.

eg. R = {(3,2), (2,0)} and the corresponding BDD:

For this reason, I was looking for libraries that have BDD functionality to help me.

I found two possibilities: JavaBDD and JDD.

But in both cases, I don’t understand how I can encode a prime integer in BDD, because how and when do I give the value of my integer? Or what does it mean if the BDD is an integer?

In both cases, there are methods such as:

int variable = createBDD(); //(JBDD) 

or

BDD bdd = new BDD(1000,1000);
int v1 = bdd.createVar(); // (JDD)

How can I just create a BDD, as my example?

Many thanks!

Answer 1

, , , BDD, , . , : 64, 6 . , 64, , , , BDD, , , BDD .

JDD BDD, JDD BDD .

, BDD :

BDD-, maxVariableCount - , ( ):

variablesDefinition - , BDD. , variablesDefinition 2, intereger.

variables - , BDD-. , , 2 , BDD, , variables[0].

BDD bddManager = new BDD(1000,100);

private int variablesDefinition;
private int[][] variables;

private void createVariables(int maxVariableCount) {
    variables = new int[variablesDefinition][maxVariableCount];
    for(int i = 0; i < variables.length; i++) {
        for(int j = 0; j < maxVariableCount; j++) {
            variables[i][j] = bddManager.createVar();
        }
    }
}

bdd .

private int bddFromTuple(int[] tuple) {
     int result;
     result = bddManager.ref(intAsBDD(tuple[0],variables[0]));
     for(int i = 1; i < tuple.length; i++) {
         result = bddManager.ref(bddManager.and(result, intAsBDD(tuple[i], variables[i])));
     }
     return result;
}

private int intAsBDD(int intToConvert, int[] variables) {
    return bddFromBinaryArray(intAsBinary(intToConvert, variables.length), variables);
}
private int[] intAsBinary(int intToConvert, int bitCount) {
    String binaryString =  Integer.toBinaryString(intToConvert);
    int[] returnedArray = new int[bitCount];
    for (int i = bitCount - binaryString.length(); i < returnedArray.length; i++) {
        returnedArray[i] = binaryString.charAt(i - bitCount + binaryString.length()) - DELTAConvertASCIIToInt;
    }
    return returnedArray;
}

static int DELTAConvertASCIIToInt = 48;

private int bddFromBinaryArray(int[] intAsBinary, int[] variables) {
    int f;

    int[] tmp = new int[intAsBinary.length];

    for(int i = 0; i < intAsBinary.length; i++) {
        if(intAsBinary[i] == 0) {
            if (i == 0) {
                tmp[i] = bddManager.ref(bddManager.not(variables[i]));
            }
            else {
                tmp[i] = bddManager.ref(bddManager.and(tmp[i-1], bddManager.not(variables[i])));
                bddManager.deref(tmp[i - 1]);
            }
        }
        else {
            if (i == 0) {
                tmp[i] = bddManager.ref(variables[i]);
            }
            else {
                tmp[i] = bddManager.ref(bddManager.and(tmp[i-1], variables[i]));
                bddManager.deref(tmp[i - 1]);
            }
        }

    }
    f = tmp[tmp.length-1];
    return f;
}

, BDD BDD, BDD BDD, , BDD.

Answer 2

, k-, lex, colex, revdoor, coolex .. k- n , . n = 4, k = 2 (1)

  tuple    rank
  (0,1) -> 1
  (0,2) -> 2
  (0,3) -> 3
  (1,2) -> 4
  (1,3) -> 5
  (2,3) -> 6

() ().