(this file is automatically generated from Java source)
Back to book index.

Z-BDD Tutorial

This tutorial demonstrates basic Z-BDD operations

Z-BDD Initialization

There are several Z-BDD objects in JDD, they are however all created in a similar fashion to the BDD object. Consult BDD tutorial for more info.

The basic Z-BDD class is ZDD. It uses BDD-style initialization

ZDD zdd = new ZDD(1000,100);

It contains all the basic operations, which are:

base()
empty()
subset1()
subset0()
union()
intersect()
diff()
change()

This sequence of code builds all the examples found in Minato original paper:

ZDD zdd = new ZDD(1000,100);
int v1 = zdd.createVar();
int v2 = zdd.createVar();

int a = zdd.empty();
int b = zdd.base();
int c = zdd.change(b, v1);
int d = zdd.change(b, v2);
int e = zdd.union(c,d);
int f = zdd.union(b,e);
int g = zdd.diff(f,c);

Note that in contrast to BDDs, Z-BDD variables (here v1 and v2) are just number and no Z-BDD trees. You can't do stuff like int a = zdd.union(v1,v2)!!!

As with BDDs, you can visualize Z-BDD trees by single calls in JDD:

zdd.print(g);
zdd.printSet(g);
zdd.printCubes(g);

7. v2: 1, 1

{ base, v2 }
{ 00, 10 }

But you will probably prefer the DOT printer printDot(). It was used to produce the following images:

a	b	c	d	e	f	g

Additional Z-BDD operators

The ZDD class has some sub-classes with additional operators. These operators are used in more advanced applications. In some cases, the new operators outperform the basic Z-BDD operators, see for example the N Queens applet where a Z-BDD/CSP algorithms is included.

The ZDD2 object

ZDD2 contains additional operations for unate cube set algebra. These operations are shown below

Class jdd.zdd.ZDD2
return type	method	parameters
void	showStats
void	internal_test
int	mul	( int, int )
int	div	( int, int )
int	mod	( int, int )

The ZDDCSP object

ZDDCSP adds extra ZDD operations for CSP problems. it is based on 'On the properties of combination set operations', by Okuno, Minato and Isozaki.

The new operations are:

Class jdd.zdd.ZDDCSP
return type	method	parameters
int	restrict	( int, int )
void	showStats
void	internal_test
int	exclude_slow	( int, int )
int	exclude	( int, int )

The ZDDGraph object

ZDDGraph is intended to [in near future] include common ZDD operations used in graph algorithms, as explained in Coudert's paper.

The graph-operations we are working on are:

Class jdd.zdd.ZDDGraph
return type	method	parameters
void	internal_test
int	allEdge	( int, int )
int	allEdge
int	noSubset	( int, int )
int	noSupset	( int, int )
int	maxSet	( int )
int	MaxDot	( int, int )

Additional Z-BDD objects

There are several additional Z-BDD objects that are currently not documented in the API.