Introduction (what is this all about?)

What is this?

This is an interfaces for working with Binary Decision Diagrams (BDDs). It allows efficient BDD computation in Java by interfacing against two efficient BDD libraries written in C.

What is it good for?

BDDs are used to efficiently represent and manipulate functions that map a binary vector to a boolean value (i.e. f: 2^V -> {0,1}). This representation can be used to efficiently store huge sets/functions/relations in relatively small chunks of memory. It can be used in to solve large combinatorial and graph problems. There are many application from CAD to compiler optimizations to Internet firewall technology.

What is the current status of this project?

Stable = not under heavy development...

Copyrights (what can I do with it?)

Sounds good, can I use it in my project?

Yes

Can I use JBDD in my commercial application?

The JBDD itself is free under the zlib license. You might need to check the BuDDy and CUDD licenses.

Performance (how fast is this thing?)

Which interface should I use??

SBL is the fastest package but BuDDy is more stable.

Why is my BDD application so slow? I thought BDDs were very efficient?

There may be several reasons: bad variable ordering is the most possible. Maybe you are solving your problem in a wrong way? Maybe what you really need is a SAT-solver? Maybe the problem is intractable anyway? Check out Alan Hu's PhD thesis (Stanford) and Bwolen Po-Jen Yang's PhD thesis (CMU) for some basic guidelines on the subject.

For better performance with JBDD, should I get a faster CPU, more cache or more RAM??

More RAM and a large L2 cache is never wrong.

Technical details

How many bytes does each BDD node occupy in JBDD?

The documentation mentions 16 bytes for CUDD and 20 bytes for BuDDy. I think the real numbers are 24 and 28. SBL uses the same structure as BuDDy.

Does JBDD use depth or breadth-first node traversal ??

SBL and BuDDy use depth first. CUDD uses breadth first.

Developer info

Are there any important distinctions between JBDD and JDD that we should know of?

Yes, there is one important difference:

In JDD, operations do not alter the ref-count of the result. In JBDD, returned results of operations are already reference-counted (one up). Thus the following JDD code:

int x = jdd.ref( jdd.not(y) );

... is identical to the following JBDD code:

int x = jbdd.not(y);

Are there any performance differences between BuDDy and CUDD that I should know?

The BDD operation NOT is O(1) in CUDD and O(n) in BuDDy. I think the reverse applies to the operation REF.

Features (not bugs)

The JBDD interface is extremely low-level, I need a more user-friendly API!

The core BDD libraries are low-level to give you complete control over each operation.

We understand that programming at such a low level is error prone. On the other hand, writing your own highly object-oriented wrapper around the core library can be done in a day or two...

Common Problems (stuff that usually fill my mailbox)

How can I submit a bug?

Use the issue tracking system

I cant get the DOT output working!

DOT is a third-party utility provided by AT&T research. Download DOT and install it from http://www.research.att.com/sw/tools/graphviz/. Make also sure that the "dot" executable is in your PATH.

My BDD applications just abort and die, whats happening?

There are three possibilities:

1. You have messed with the BDD variables [something like jbdd.not(-12345)] which will cause the JVM to crash.
2. You have ref-counting problems, in which cases JBDD writes an error message and terminates.
3. The CUDD support is very instable anyway :(

Misc. (anything else)

Can several BDD managers simultaneously exist in JBDD?

No!

What is the relation between JBDD and JavaBDD?

Not related, but its a small world. We have talked...