use vars
qw($VERSION @ISA @EXPORT $AUTOLOAD);
@ISA = qw(Exporter DynaLoader);
# Items to export into callers namespace by default. Note: do not export
# names by default without a very good reason. Use EXPORT_OK instead.
# Do not simply export all your public functions/methods/constants.
# This AUTOLOAD is used to 'autoload' constants from the constant()
# XS function. If a constant is not found then control is passed
# to the AUTOLOAD in AutoLoader.
($constname = $AUTOLOAD) =~ s/.*:://;
my $val = constant
($constname, @_ ?
$_[0] : 0);
$AutoLoader::AUTOLOAD
= $AUTOLOAD;
goto &AutoLoader
::AUTOLOAD
;
croak
"Your vendor has not defined Cudd macro $constname";
eval "sub $AUTOLOAD { $val }";
# Preloaded methods go here.
Cudd - Perl extension for BDDs
C<my $manager = new Cudd;>
Cudd extends Perl so that it manipulates Binary Decision Diagrams
(BDDs) by providing an object-oriented encapsulation of the CUDD
package. The CUDD package is written in C and contains a large
collection of efficient BDD manipulation functions. Only a small
fraction of those functions are currently made available by the Cudd
module. Those that are available, however, allow one to accomplish
The methods defined by Cudd are divided into two packages. The first
package, Cudd, defines methods that create and manipulate BDD managers
and BDD variables. These are the methods defined in package Cudd:
Creates a new BDD manager.
my $numVars = shift || 0;
my $numVarsZ = shift || 0;
my $numSlots = shift || &Cudd
::UNIQUE_SLOTS
;
my $cacheSize = shift || &Cudd
::CACHE_SLOTS
;
my $maxMemory = shift || 0;
my $manager = Init
($numVars,$numVarsZ,$numSlots,$cacheSize,$maxMemory);
my $retval = CheckZeroRef
($$manager);
print "In Cudd::DESTROY $retval non-zero references\n";
Creates a new variable in a BDD manager.
croak
"Invalid reference" unless ref $manager;
my $node = bddNewVar
($$manager);
my $BDD = Cudd
::BDD
->new($manager,$node);
Returns the constant 1 of a BDD manager.
croak
"Invalid reference" unless ref $manager;
my $node = ReadOne
($$manager);
my $BDD = Cudd
::BDD
->new($manager,$node);
Reorders the BDDs of a manager.
my $method = shift || &Cudd
::REORDER_SAME
;
my $minsize = shift || 1;
croak
"Invalid reference" unless ref $manager;
Cudd
::ReduceHeap
($$manager,$method,$minsize);
Enables dynamic reordering for a BDD manager.
my $method = shift || &Cudd
::REORDER_SAME
;
croak
"Invalid reference" unless ref $manager;
Cudd
::AutodynEnable
($$manager,$method);
Disables dynamic reordering for a BDD manager.
croak
"Invalid reference" unless ref $manager;
Cudd
::AutodynDisable
($$manager);
Enables reporting of dynamic reordering.
croak
"Invalid reference" unless ref $manager;
Cudd
::EnableReorderingReporting
($$manager);
=item DoNotReportReordering
Disables reporting of dynamic reordering.
sub DoNotReportReordering
{
croak
"Invalid reference" unless ref $manager;
Cudd
::DisableReorderingReporting
($$manager);
Prints statistical information on a BDD manager.
croak
"Invalid reference" unless ref $manager;
my $retval = Cudd
::PrintInfo
($$manager);
croak
"Error while printing manager info" if ($retval != 1);
Returns the peak number of live nodes in the manager.
croak
"Invalid reference" unless ref $manager;
my $retval = Cudd
::ReadPeakLiveNodeCount
($$manager);
Returns the number of live nodes in the manager.
croak
"Invalid reference" unless ref $manager;
my $retval = Cudd
::ReadNodeCount
($$manager);
=item DynReorderingStatus
Returns a list with two elements. The first is 1 if reordering is
currently enabled and 0 otherwise; the second is the reordering method
sub DynReorderingStatus
{
croak
"Invalid reference" unless ref $manager;
my @retval = Cudd
::ReorderingStatus
($$manager);
'""' => sub { return "OK"; },
'bool' => sub { my $self = shift; return $self->Unequal($self->Zero); }
The second package in module Cudd is Cudd::BDD. It defines methods
that manipulate BDDs. Starting with a set of variables belonging to a
manager, the functions in this package allow one to create BDDs for
arbitrary functions over those variables. These are the methods
my ($class,$manager,$node) = @_;
croak
"Invalid reference" unless ref $manager;
# carp "In Cudd::BDD::new: creating $node\n";
bless { manager
=> $manager,
my $manager = $self->{manager
};
croak
"Invalid reference" unless ref $manager;
# carp "In Cudd::BDD::DESTROY: dereferencing $self->{node}\n";
Cudd
::IterDerefBdd
($$manager,$self->{node
});
Returns the constant 1 BDD from the manager of $f.
my $manager = $f->{'manager'};
croak
"Invalid reference" unless ref $manager;
Returns the constant 0 BDD from the manager of $f.
my $manager = $f->{'manager'};
croak
"Invalid reference" unless ref $manager;
return !$manager->BddOne;
Computes the conjunction of two BDDs. Overloads '*'.
my $manager = $f->{'manager'};
croak
"Invalid reference" unless ref $manager;
my $node = Cudd
::bddAnd
($$manager,$f->{'node'},$g->{'node'});
my $BDD = new Cudd
::BDD
($manager,$node);
Computes the disjunction of two BDDs. Overloads '+'.
my $manager = $f->{'manager'};
croak
"Invalid reference" unless ref $manager;
my $node = Cudd
::bddOr
($$manager,$f->{'node'},$g->{'node'});
my $BDD = new Cudd
::BDD
($manager,$node);
Computes the exclusive or of two BDDs. Overloads '^'.
my $manager = $f->{'manager'};
croak
"Invalid reference" unless ref $manager;
my $node = Cudd
::bddXor
($$manager,$f->{'node'},$g->{'node'});
my $BDD = new Cudd
::BDD
($manager,$node);
my $manager = $f->{'manager'};
croak
"Invalid reference" unless ref $manager;
my $node = Cudd
::bddXnor
($$manager,$f->{'node'},$g->{'node'});
my $BDD = new Cudd
::BDD
($manager,$node);
Computes the NAND of two BDDs.
my $manager = $f->{'manager'};
croak
"Invalid reference" unless ref $manager;
my $node = Cudd
::bddNand
($$manager,$f->{'node'},$g->{'node'});
my $BDD = new Cudd
::BDD
($manager,$node);
Computes the NOR of two BDDs.
my $manager = $f->{'manager'};
croak
"Invalid reference" unless ref $manager;
my $node = Cudd
::bddNor
($$manager,$f->{'node'},$g->{'node'});
my $BDD = new Cudd
::BDD
($manager,$node);
Computes the cofactor of a BDD with respect to another. Uses the constrain
algorithm. Overloads '/'.
my $manager = $f->{'manager'};
my $node = Cudd
::bddConstrain
($$manager,$f->{'node'},$c->{'node'});
my $BDD = new Cudd
::BDD
($manager,$node);
Computes the cofactor of a BDD with respect to another. Uses the restrict
my $manager = $f->{'manager'};
my $node = Cudd
::bddRestrict
($$manager,$f->{'node'},$c->{'node'});
my $BDD = new Cudd
::BDD
($manager,$node);
Finds a small BDD in an interval.
my $manager = $l->{'manager'};
my $node = Cudd
::bddSqueeze
($$manager,$l->{'node'},$u->{'node'});
my $BDD = new Cudd
::BDD
($manager,$node);
Existentially quantifies the variables in a cube from a BDD.
my $manager = $f->{'manager'};
croak
"Invalid reference" unless ref $manager;
my $node = Cudd
::bddExistAbstract
($$manager,$f->{'node'},$cube->{'node'});
my $BDD = new Cudd
::BDD
($manager,$node);
Universally quantifies the variables in a cube from a BDD.
my $manager = $f->{'manager'};
croak
"Invalid reference" unless ref $manager;
my $node = Cudd
::bddUnivAbstract
($$manager,$f->{'node'},$cube->{'node'});
my $BDD = new Cudd
::BDD
($manager,$node);
Existentially quantifies the variables in a cube from the conjunction of
my $manager = $f->{'manager'};
croak
"Invalid reference" unless ref $manager;
my $node = Cudd
::bddAndAbstract
($$manager,$f->{'node'},$g->{'node'},
my $BDD = new Cudd
::BDD
($manager,$node);
Composes a BDD $g into a BDD $f substituting variable $var.
my $manager = $f->{'manager'};
croak
"Invalid reference" unless ref $manager;
my $index = Cudd
::NodeReadIndex
($var->{'node'});
my $node = Cudd
::bddCompose
($$manager,$f->{'node'},$g->{'node'},$index);
my $BDD = new Cudd
::BDD
($manager,$node);
Computes the boolean difference of a BDD with respect to one variable.
my $manager = $f->{'manager'};
croak
"Invalid reference" unless ref $manager;
my $index = Cudd
::NodeReadIndex
($var->{'node'});
my $node = Cudd
::bddBooleanDiff
($$manager,$f->{'node'},$index);
my $BDD = new Cudd
::BDD
($manager,$node);
Computes the correlation of two BDDs. The result is a number between 0
and 1. A value of 1 indicates that the functions $f and $g are
identical. A value of 0 indicates that they are complementary.
my $manager = $f->{'manager'};
croak
"Invalid reference" unless ref $manager;
my $correl = Cudd
::bddCorrelation
($$manager,$f->{'node'},$g->{'node'});
Returns 1 if the BDD $f is monotonic decreasing (negative unate) in
variable $var; 0 otherwise.
my $manager = $f->{'manager'};
croak
"Invalid reference" unless ref $manager;
my $index = Cudd
::NodeReadIndex
($var->{'node'});
my $retval = Cudd
::Decreasing
($$manager,$f->{'node'},$index);
Returns 1 if the BDD $f is monotonic increasing (positive unate) in
variable $var; 0 otherwise.
my $manager = $f->{'manager'};
croak
"Invalid reference" unless ref $manager;
my $index = Cudd
::NodeReadIndex
($var->{'node'});
my $retval = Cudd
::Increasing
($$manager,$f->{'node'},$index);
Finds the essential variables of a BDD. Returns an array of all essentials.
Negative essentials correspond to negative literals.
my $manager = $f->{'manager'};
croak
"Invalid reference" unless ref $manager;
my $essref = Cudd
::FindEssential
($$manager,$f->{'node'});
my $BDD = new Cudd
::BDD
($manager,$ess);
Returns a cube of all the variables in the support of $f.
my $manager = $f->{'manager'};
croak
"Invalid reference" unless ref $manager;
my $support = Cudd
::Support
($$manager,$f->{'node'});
my $BDD = new Cudd
::BDD
($manager,$support);
=item LiteralSetIntersection
Computes the intersection of two literal sets represented by cube BDDs.
sub LiteralSetIntersection
{
my $manager = $f->{'manager'};
croak
"Invalid reference" unless ref $manager;
my $node = Cudd
::bddLiteralSetIntersection
($$manager,$f->{'node'},$g->{'node'});
my $BDD = new Cudd
::BDD
($manager,$node);
Swaps two sets of variables in a BDD.
my ($f,$xref,$yref) = @_;
my $manager = $f->{'manager'};
croak
"Invalid reference" unless ref $manager;
my @xvars = map $_->{'node'}, (@
$xref);
my @yvars = map $_->{'node'}, (@
$yref);
my $node = Cudd
::bddSwapVariables
($$manager,$f->{'node'},\
@xvars,\
@yvars);
my $BDD = new Cudd
::BDD
($manager,$node);
Solves a boolean equation. The first argument $f is the left-hand side
of the equation $f = 0. The second argument is a reference to the
array of the unknowns. The variables that are not unknowns are
my $manager = $f->{'manager'};
croak
"Invalid reference" unless ref $manager;
my $cube = $manager->BddOne;
my ($consist,$solref) = Cudd
::SolveEqn
($$manager,$f->{'node'},
$cube->{'node'},$numvar);
$BDD = new Cudd
::BDD
($manager,$consist);
my $BDD = new Cudd
::BDD
($manager,$sol);
return((\
@solutions,$BDD));
Computes the variable signatures in a BDD. The signature of a variable
is the fraction of minterms in the on-set of the cofactor w.r.t. to
that variable. The function returns an array of as many signatures as
there are variables plus one. The last element of the array is the
fraction of minterms in the ON-set of the BDD, and can be used to
normalize the variable signatures.
my $manager = $f->{'manager'};
croak
"Invalid reference" unless ref $manager;
return Cudd
::CofMinterm
($$manager,$f->{'node'});
Returns signatures normalized between 0 and 2. See also Signatures.
my $raw = Cudd
::BDD
::Signatures
($f);
my $result = [map {$$raw[$_] / $$raw[$size-1]} (0..$size-2)];
Computes a subset of a BDD with a maximum number of nodes. Uses the
my $manager = $f->{'manager'};
croak
"Invalid reference" unless ref $manager;
my $numVars = Cudd
::ReadSize
($$manager);
my $node = Cudd
::SubsetHeavyBranch
($$manager,$f->{'node'},$numVars,$th);
my $BDD = new Cudd
::BDD
($manager,$node);
Computes a subset of a BDD with a maximum number of nodes. Uses the
my $manager = $f->{'manager'};
croak
"Invalid reference" unless ref $manager;
my $numVars = Cudd
::ReadSize
($$manager);
my $node = Cudd
::SubsetShortPaths
($$manager,$f->{'node'},$numVars,$th,0);
my $BDD = new Cudd
::BDD
($manager,$node);
Computes a superset of a BDD with a maximum number of nodes. Uses the
my $manager = $f->{'manager'};
croak
"Invalid reference" unless ref $manager;
my $numVars = Cudd
::ReadSize
($$manager);
my $node = Cudd
::SupersetHeavyBranch
($$manager,$f->{'node'},$numVars,$th);
my $BDD = new Cudd
::BDD
($manager,$node);
Computes a superset of a BDD with a maximum number of nodes. Uses the
my $manager = $f->{'manager'};
croak
"Invalid reference" unless ref $manager;
my $numVars = Cudd
::ReadSize
($$manager);
my $node = Cudd
::SupersetShortPaths
($$manager,$f->{'node'},$numVars,$th,0);
my $BDD = new Cudd
::BDD
($manager,$node);
Creates a new variable adjacent to the given variable. Useful in creating the next state variables of FSMs.
my $manager = $var->{manager
};
croak
"Invalid reference" unless ref $manager;
my $index = Cudd
::NodeReadIndex
($var->{node
});
my $level = Cudd
::ReadPerm
($$manager,$index);
my $node = Cudd
::bddNewVarAtLevel
($$manager,$level);
my $BDD = new Cudd
::BDD
($manager,$node);
Creates a group of variables to be kept adjacent during reordering.
my $method = shift || &Cudd
::MTR_DEFAULT
;
my $manager = $self->{manager
};
croak
"Invalid reference" unless ref $manager;
my $index = Cudd
::NodeReadIndex
($self->{node
});
my $retval = Cudd
::MakeTreeNode
($$manager,$index,$size,$method);
Returns the complement of a BDD. Overloads '!'.
my $manager = $f->{'manager'};
croak
"Invalid reference" unless ref $manager;
my $node = Cudd
::Not
($f->{'node'});
my $BDD = new Cudd
::BDD
($manager,$node);
Returns 1 if the two arguments are equivalent; 0 otherwise. Overloads '=='.
my $manager = $f->{'manager'};
croak
"Invalid reference" unless ref $manager;
return (${$f->{'node'}} == ${$g->{'node'}}) ?
1 : 0;
Returns 1 if the two arguments are not equivalent; 0 otherwise. Overloads '!='.
my $manager = $f->{'manager'};
croak
"Invalid reference" unless ref $manager;
return (${$f->{'node'}} != ${$g->{'node'}}) ?
1 : 0;
Compares two BDDs $f and $g and returns 1 if $f is less than or equal to $g.
my $manager = $f->{'manager'};
croak
"Invalid reference" unless ref $manager;
return Cudd
::bddLeq
($$manager, $f->{'node'}, $g->{'node'});
Compares two BDDs $f and $g and returns 1 if $f is greater than or equal to $g.
my $manager = $f->{'manager'};
croak
"Invalid reference" unless ref $manager;
return Cudd
::bddLeq
($$manager, $g->{'node'}, $f->{'node'});
Returns 1 if the BDD node is complemented, that is, if the BDD evaluates to 0 when all variables are assigned 1.
return Cudd
::IsComplement
($f->{'node'});
Computes a shortest path in a BDD.
my $manager = $f->{'manager'};
croak
"Invalid reference" unless ref $manager;
my $node = Cudd
::ShortestPath
($$manager, $f->{'node'}, $length);
my $BDD = new Cudd
::BDD
($manager,$node);
Returns the number of nodes in the BDD or BDDs passed as arguments.
if (ref($f) eq "Cudd::BDD") {
} elsif (ref($f) eq "ARRAY") {
$f = [map $_->{'node'}, (@
$f)];
} elsif (ref($f) eq "HASH") {
$f = [map $_->{'node'}, values(%$f)];
my $size = Cudd
::SharingSize
($f);
Returns the number of minterms of the BDD. The function of the BDD is
supposed to depend on C<$n> variables.
my $manager = $f->{'manager'};
croak
"Invalid reference" unless ref $manager;
my $retval = Cudd
::CountMinterm
($$manager, $f->{'node'}, $n);
Prints information about a BDD $f. The $pr parameter controls how much
information is printed. The $n parameter specifies how many inputs $f depends
on. This information is necessary to compute the number of minterms.
my $manager = $f->{'manager'};
croak
"Invalid reference" unless ref $manager;
my $retval = Cudd
::PrintDebug
($$manager,$f->{'node'},$n,$pr);
Prints a description of a set of BDDs in dot format. The function has
one mandatory parameter, the list of BDDs for which the dot
description is desired, and two optional parameters, the array of
input names and the array of output names. All parameters are array
references. If the input names are omitted but the output names are
not, a reference to an empty array ([]) should be passed for the input
my ($inameref,$onameref);
my $manager = $first->{'manager'};
croak
"Invalid reference" unless ref $manager;
my $retval = Cudd
::DumpDot
($$manager,\
@f,$onameref,$inameref);
warn "Error while writing dot file" if ($retval != 1);
Computes a function included in the intersection of $f and $g. (That
is, a witness that the intersection is not empty.) Intersect tries to
build as few new nodes as possible.
my $manager = $f->{'manager'};
croak
"Invalid reference" unless ref $manager;
my $node = Cudd
::bddIntersect
($$manager,$f->{'node'},$g->{'node'});
my $BDD = new Cudd
::BDD
($manager,$node);
BDD conjunctive decomposition as in the CAV96 paper by McMillan. The
decomposition is canonical only for a given variable order. If
canonicity is required, variable ordering must be disabled after the
decomposition has been computed. Returns an array with one entry for
my $manager = $f->{'manager'};
croak
"Invalid reference" unless ref $manager;
my $decref = Cudd
::bddConstrainDecomp
($$manager,$f->{'node'});
my $BDD = new Cudd
::BDD
($manager,$dec);
Computes a vector of functions such that their image equals a non-zero
function. Returns an array with one entry for each BDD variable.
my $manager = $f->{'manager'};
croak
"Invalid reference" unless ref $manager;
my $vecref = Cudd
::bddCharToVect
($$manager,$f->{'node'});
my $BDD = new Cudd
::BDD
($manager,$vec);
Selects pairs from a relation C<R(x,y)> (given as a BDD)
in such a way that a given x appears in one pair only. Uses a
priority function to determine which y should be paired to a given x.
my ($f,$Pi,$xref,$yref,$zref) = @_;
my $manager = $f->{'manager'};
croak
"Invalid reference" unless ref $manager;
my @xvars = map $_->{'node'}, (@
$xref);
my @yvars = map $_->{'node'}, (@
$yref);
my @zvars = map $_->{'node'}, (@
$zref);
my $node = Cudd
::PrioritySelect
($$manager,$f->{'node'},$Pi->{'node'},
\
@xvars,\
@yvars,\
@zvars);
my $BDD = new Cudd
::BDD
($manager,$node);
Returns the priority function that is 1 if the distance of x from y is greater than the distance of x from z.
my ($xref,$yref,$zref) = @_;
my $manager = $first->{'manager'};
croak
"Invalid reference" unless ref $manager;
my @xvars = map $_->{'node'}, (@
$xref);
my @yvars = map $_->{'node'}, (@
$yref);
my @zvars = map $_->{'node'}, (@
$zref);
my $node = Cudd
::Dxygtdxz
($$manager,\
@xvars,\
@yvars,\
@zvars);
my $BDD = new Cudd
::BDD
($manager,$node);
Returns the priority function that is 1 if the distance of x from y is greater than the distance of y from z.
my ($xref,$yref,$zref) = @_;
my $manager = $first->{'manager'};
croak
"Invalid reference" unless ref $manager;
my @xvars = map $_->{'node'}, (@
$xref);
my @yvars = map $_->{'node'}, (@
$yref);
my @zvars = map $_->{'node'}, (@
$zref);
my $node = Cudd
::Dxygtdyz
($$manager,\
@xvars,\
@yvars,\
@zvars);
my $BDD = new Cudd
::BDD
($manager,$node);
Returns the priority function that is 1 if x is greater than y.
my ($zref,$xref,$yref) = @_;
my $manager = $first->{'manager'};
croak
"Invalid reference" unless ref $manager;
my @zvars = map $_->{'node'}, (@
$zref);
my @xvars = map $_->{'node'}, (@
$xref);
my @yvars = map $_->{'node'}, (@
$yref);
my $node = Cudd
::Xgty
($$manager,\
@zvars,\
@xvars,\
@yvars);
my $BDD = new Cudd
::BDD
($manager,$node);
Applies the C-Projection to a relation R.
my $manager = $R->{'manager'};
croak
"Invalid reference" unless ref $manager;
my $node = Cudd
::CProjection
($$manager,$R->{'node'},$Y->{'node'});
my $BDD = new Cudd
::BDD
($manager,$node);
my $manager = $first->{'manager'};
croak
"Invalid reference" unless ref $manager;
my $index = Cudd
::NodeReadIndex
($var->{node
});
push(@permutation,$index);
return Cudd
::ShuffleHeap
($$manager,\
@permutation);
# Autoload methods go after =cut, and are processed by the autosplit program.
Package Cudd:BDD overloads common operators as follows:
The following code fragment creates a manager, two variables C<$x> and
C<$y> in it, and then builds and prints the conjunction of the two
my $x = $manager->BddVar;
my $y = $manager->BddVar;
$z->Print(2,1); # (2 variables, verbosity 1)
Fabio Somenzi, Fabio@Colorado.EDU