CUDD-like API
“The CUDD package provides functions to manipulate Binary Decision Diagrams (BDDs) [4, 3], Algebraic Decision Diagrams (ADDs) [2], and Zero-suppressed Binary Decision Diagrams (ZDDs) [5].” [1] However, the software package was written in C, a major hurdle for many potential users who may only be familiar with higher-level programming languages. With the ADD-Lib, we allow these users to call nearly all of CUDD’s C functions directly from within their Java applications.
To take full advantage of the ADD-Lib, we recommend to use the high-level ADD-Lib API that introduces type safety, great support for new algebraic structures, layouting, code generation, etc. You can always go back to the low-level CUDD-like API when necessary.
When working close to the CUDD-like API, you may find the CUDD documentation helpful. We collected useful resources for you:
Disjunction: A Minimal BDD Example
The ADD-Lib’s CUDD-like API is analogous to the CUDD API except that it brings its extensive functionality to the Java world. All API methods have the same name as their CUDD equivalent and types are chosen as close to their C equivalent as possible. In Java you can import all these API methods statically to use them kust like you would in a C program:
import static info.scce.addlib.cudd.Cudd.*;
Analogously to the examples for the use of the ADD-Lib API, let’s start with a minimal BDD example: the disjunction of two variables, var0 and var1:
/* Initialize DDManager with default values */
long ddManager = Cudd_Init(0, 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
/* Get the variables */
long var0 = Cudd_bddIthVar(ddManager, 0);
Cudd_Ref(var0);
long var1 = Cudd_bddIthVar(ddManager, 1);
Cudd_Ref(var1);
/* Build the disjunction */
long disjunction = Cudd_bddOr(ddManager, var0, var1);
Cudd_Ref(disjunction);
Cudd_RecursiveDeref(ddManager, var0);
Cudd_RecursiveDeref(ddManager, var1);
/* Evaluate disjunction for assignment var0 := 1, var1 := 0 */
int[] assignment = {1, 0};
long terminal = Cudd_Eval(ddManager, disjunction, assignment);
/* See if the terminal is what we expect it to be */
long one = Cudd_ReadOne(ddManager);
Cudd_Ref(one);
System.out.println("[[ terminal == one ]] = " + (terminal == one));
assertEquals(terminal, one);
/* Release memory */
Cudd_RecursiveDeref(ddManager, one);
Cudd_RecursiveDeref(ddManager, disjunction);
Cudd_Quit(ddManager);
After initialization of the CUDD Manager, we use it to obtain pointers (long values in Java) to the primitive BDDs for the 0th respectively the 1st variable and increase their reference counter. With the newly obtained variables we build their disjunction and again increase the reference counter of the new node while releasing no longer needed references to the variables. The remainder of the code snipped evaluates the disjunction for an exemplary variable assignment (var0 := 1, var1 := 0) and checks its equality to the constant 1-BDD. Finally, remaining references are released before we quit the CUDD Manager to release its memory.
The Java code is analogous to a C implementation using CUDD directly except that pointers (*DdManager, *DdNode) are handled as long values. For this reason, you may always refer to the CUDD documentation on BBDs, ADDs, and ZDDs for a more detailed description of the API functionality.
The Exact ADD Example from the CUDD Manual
Besides BDDs CUDD supports ADDs, primarily over real numbers (i.e. double values). To stress the correspondence between our CUDD-like API and the original CUDD API consider the following example that implements the exact ADD example from the CUDD manual in Java:
/* Initialize DDManager with default values */
long ddManager = Cudd_Init(0, 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
/* Get a constant */
long f = Cudd_addConst(ddManager, 5);
Cudd_Ref(f);
/* Multiply constant with some variables */
for (int i = 3; i >= 0; i--) {
/* Get the variable */
long var = Cudd_addIthVar(ddManager, i);
Cudd_Ref(var);
/* Multiply the variable to the product */
long tmp = Cudd_addApply(ddManager, Cudd_addTimes, var, f);
Cudd_Ref(tmp);
Cudd_RecursiveDeref(ddManager, f);
Cudd_RecursiveDeref(ddManager, var);
f = tmp;
}
/* ... */
/* Release memory */
Cudd_RecursiveDeref(ddManager, f);
Cudd_Quit(ddManager);
Custom Operations by Callback
CUDD’s Cudd_addApply method accepts function pointers to allow for custom operations on ADDs. In Java the counterparts to this mechanism are the abstract classes DD_AOP_Fn and DD_MAOP_Fn that can be used to implement custom binary or monadic operations in the exact same way one would implement them in CUDD directly. For more detail you may again refer to the CUDD documentation on Cudd_addApply. The below example realizes an operation that sums its operands and adds a constant 8 to it:
/* Initialize DDManager with default values */
long ddManager = Cudd_Init(0, 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
/* Get some variables */
long var0 = Cudd_addIthVar(ddManager, 0);
Cudd_Ref(var0);
long var1 = Cudd_addIthVar(ddManager, 1);
Cudd_Ref(var1);
/* Build sum8: var0 + var1 + 8 */
long sum8 = Cudd_addApply(ddManager, new DD_AOP_Fn() {
@Override
public long apply(long ddManager, long f, long g) {
if (Cudd_IsConstant(f) > 0 && Cudd_IsConstant(g) > 0) {
double value = Cudd_V(f) + Cudd_V(g) + 8;
return Cudd_addConst(ddManager, value);
}
return NULL;
}
}, var0, var1);
Cudd_Ref(sum8);
Cudd_RecursiveDeref(ddManager, var0);
Cudd_RecursiveDeref(ddManager, var1);
/* ... */
/* Release memory */
Cudd_RecursiveDeref(ddManager, sum8);
Cudd_Quit(ddManager);
Conversion Utils
As the CUDD-like API is designed to be as similar to its C equivalent as possible it uses integers even where one would expect a Boolean type in Java. The ADD-Lib comes with a Conversions class that provides some useful methods and constants that can be imported statically:
import static info.scce.addlib.utils.Conversions.*;
Among others the class defines a the value for NULL pointers and allows to convert to and from Boolean values using the methods asBoolean and asInt or their array variant. When used consistently this can contribute greatly towards readability of your code.
[1] F. Somenzi, “CUDD: CU Decision Diagram Package”, vlsi.colorado.edu/~fabio/, 2018.
[2] R. I. Bahar, E. A. Frohm, C. M. Gaona, G. D. Hachtel, E. Macii, A. Pardo, and F. Somenzi, “Algebraic decision diagrams and their applications,” Proceedings of 1993 International Conference on Computer Aided Design (ICCAD), 1993.
[3] K. S. Brace, R. L. Rudell, and R. E. Bryant, “Efficient implementation of a BDD package,” Proceedings of the 27th ACM/IEEE Design Automation Conference, 1990.
[4] R. E. Bryant, “Graph-Based Algorithms for Boolean Function Manipulation,” in IEEE Transactions on Computers, vol. C-35, no. 8, 1986.
[5] S.-I. Minato, “Zero-Suppressed BDDs for Set Manipulation in Combinatorial Problems,” Proceedings of the 30th ACM/IEEE Design Automation Conference, 1993.
