AI-PBDD
view release on metacpan or search on metacpan
2) build and install buddy-2.4 as follows:
export CFLAGS='-fPIC -O2'
export CXXFLAGS='-fPIC -O2'
./configure --prefix=/my/buddy/home --disable-shared
make
make install
NOTE: /my/buddy/home stands for the directory where you unzipped buddy-2.4
INSTALLATION
First of all set the environment variable BUDDYPATH to the directory where you unzipped buddy-2.4, e.g.:
export BUDDYPATH=/my/buddy/home
Then type the following:
perl Makefile.PL
make
make test
make install
int len = size;
int *old_vars = (int *)old;
int *new_vars = (int *)new_;
for (i = 0; i < len; i++)
{
/*
* XXX - not bdd_var() call for new_vars[i] ??
*/
bdd_setbddpair (pair, bdd_var(old_vars[i]), new_vars[i]);
}
return (long)pair;
}
int makeSet(int *vars, int size, int offset)
{
BDD tmp, ret = 1;
int i;
int *body = (int *)vars;
// DONT USE ´ret = bdd_makeset(body + offset, size);´ (it uses index
// not variables)
bdd_addref (ret);
for (i = size - 1; i >= 0; i--)
{
CHECK_BDD (body[offset + i]);
tmp = bdd_apply (ret, body[offset + i], bddop_and);
bdd_addref (tmp);
bdd_delref (ret);
ret = tmp;
}
return ret;
}
int checkBuddy() {
int i;
// -----------------------------------------------------------------------------------
static int current_reordering_method = BDD_REORDER_NONE;
MODULE = AI::PBDD PACKAGE = AI::PBDD
PROTOTYPES: DISABLE
void
reorder_setMethod(method)
int method
PPCODE:
{
if (method >= 0 && method < MAX_REORDERING_METHODS)
current_reordering_method = reordering_method_table[method];
}
void reorder_now()
PPCODE:
{
exit (20);
}
ok = bdd_init (nodenum, cachesize);
if (ok == 0)
{
varnum = varnum_;
varcount = 0;
bdd_setmaxincrease (MAX_NODE_INCREASE);
bdd_setvarnum (2 + 2 * varnum);
has_bdd = 1;
if (bdd_false () != 0 || bdd_true () != 1)
{
fprintf (stderr, " INTERNAL ERROR : false = %d, true = %d\n",
bdd_false (), bdd_true ());
exit (20);
}
{
BDD ret;
if (varcount >= varnum)
{
fprintf (stderr, "Maximum var count (%d) reached!!\n", varnum);
exit (20);
}
ret = bdd_ithvar (varcount++);
// bddnodes[ret].refcou = 1; // why does BuDDy sets the initial
// refcount to MAXREF (0x3FF) ?
RETVAL=ret;
}
OUTPUT:
RETVAL
int getVarCount()
CODE:
{
for (i=0; i<=av_len(vars); i++) {
SV** elem = av_fetch(vars, i, 0);
varsarr[i] = SvNV(*elem);
}
RETVAL = makeSet(varsarr, size, 0);
}
OUTPUT:
RETVAL
int makeSetII(vars, size, offset)
AV *vars
int size
int offset
CODE:
{
int *varsarr = malloc(av_len(vars)*sizeof(int));
int i;
for (i=0; i<=av_len(vars); i++) {
SV** elem = av_fetch(vars, i, 0);
varsarr[i] = SvNV(*elem);
}
RETVAL = makeSet(varsarr, size, offset);
}
OUTPUT:
RETVAL
int debugBDD(bdd)
int bdd
CODE:
{
CHECK_BDD (bdd);
lib/AI/PBDD.pm view on Meta::CPAN
@EXPORT = qw(
BDD_REORDER_NONE
BDD_REORDER_WIN2
BDD_REORDER_WIN3
BDD_REORDER_SIFT
BDD_REORDER_RANDOM
);
@EXPORT_OK = qw(
// setup and cleanup
init
gc
verbose
kill
// simple BDD operations
getOne
getZero
createBDD
getVarCount
getBDD
lib/AI/PBDD.pm view on Meta::CPAN
debugBDD
// low-level access
internal_index
internal_refcount
internal_isconst
internal_constvalue
internal_iscomplemented
internal_then
internal_else
// dynamic variable ordering
reorder_setMethod
reorder_now
reorder_enableDynamic
reorder_createVariableGroup
);
$VERSION = '0.01';
bootstrap AI::PBDD $VERSION;
sub satCount {
lib/AI/PBDD.pm view on Meta::CPAN
my ($bdd, $filename) = @_;
if (!defined($filename)) {
printDot__I($bdd);
} else {
printDot__II($bdd, $filename);
}
}
sub makeSet {
my ($vars, $size, $offset) = @_;
if (!defined($offset)) {
return makeSetI($vars, $size);
} else {
return makeSetII($vars, $size, $offset);
}
}
sub createPair {
my ($old, $new) = @_;
my $size = @$old;
return createPairI($old, $new, $size);
}
lib/AI/PBDD.pm view on Meta::CPAN
my $var2 = createBDD();
my $bdd = and($var1, $var2);
printDot($bdd);
kill();
=head1 DESCRIPTION
Binary Decision Diagrams (BDDs) are used for efficient computation of many common problems. This is done by giving a compact representation and a set of efficient operations on boolean functions f: {0,1}^n --> {0,1}.
It turns out that this representation is good enough to solve a huge amount of problems in Artificial Intelligence and other areas of computing such as hardware verification.
This is a Perl interface to the popular BDD package BuDDy. The interface is largely inspired by JBDD, a Java common interface for the two BDD packages BuDDy and CUDD written by Arash Vahidi, which can be found at L<http://javaddlib.sourceforge.net/jb...
PBDD allows you to combine the power of Perl with an efficient BDD package written in highly optimized C.
=head1 FUNCTIONS
=head2 SETUP AND CLEANUP
lib/AI/PBDD.pm view on Meta::CPAN
=item B<$bdd = biimp($bdd1,$bdd2)>
BDD BIIMPlication operation. The returned result is already referenced.
=item B<$bdd = not($bdd1)>
BDD NOT operation. The returned result is already referenced.
=item B<$cube = makeSet($vars,$size)>
=item B<$cube = makeSet($vars,$size,$offset)>
Create a cube (all-true minterm, e.g. C<$v1 AND $v2 AND $v3> where each C<$vi> is a BDD variable) of C<$size> variables from the array referenced by C<$vars>, starting at position 0 (or C<$offset>).
=item B<$bdd = exists($bdd1,$cube)>
BDD existential quantification. Parameter C<$cube> is an all-true minterm. The returned result is already referenced.
=item B<$bdd = forall($bdd1,$cube)>
BDD universal quantification. Parameter C<$cube> is an all-true minterm. The returned result is already referenced.
=item B<$bdd = relProd($bdd_left,$bdd_right,$cube)>
BDD relation-product (quantification and product computation in one pass): C<EXISTS $cube: $bdd_left AND $bdd_right>. The returned result is already referenced.
=item B<$bdd = restrict($bdd1,$minterm)>
Restrict a set of variables to constant values. The returned result is already referenced.
=item B<$bdd = constrain($bdd1,$bdd2)>
Compute the generalized co-factor of C<$bdd1> w.r.t. C<$bdd2>. The returned result is already referenced.
=back
=head2 VARIABLES REPLACEMENT
=over 4
lib/AI/PBDD.pm view on Meta::CPAN
Print a pair.
=back
=head2 BDD ANALYSIS
=over 4
=item B<$cube = support($bdd)>
BDD support set as a cube.
=item B<$cnt = nodeCount($bdd)>
Number of nodes a BDD.
=item B<$minterm = satOne($bdd)>
One arbitrary minterm (satisfying variable assignment), unless C<$bdd> equals 0.
=item B<$cnt = satCount($bdd)>
lib/AI/PBDD.pm view on Meta::CPAN
=item B<$bdd_else = internal_else($bdd)>
Get the ELSE-node of a BDD.
=back
=head2 DYNAMIC VARIABLE ORDERING
=over 4
=item B<reorder_setMethod($method)>
Set dynamic reordering heuristic. The possible values are:
=over 4
=item BDD_REORDER_NONE
No reordering.
=item BDD_REORDER_WIN2
my @vars;
my %names = ();
AI::PBDD::init(100,1000000);
my $bdd1 = AI::PBDD::createBDD();
$names{AI::PBDD::internal_index($bdd1)} = 'A';
push @vars, $bdd1;
my $bdd2 = AI::PBDD::createBDD();
$names{AI::PBDD::internal_index($bdd2)} = 'B';
push @vars, $bdd2;
my $set = AI::PBDD::makeSet(\@vars, 2);
my $dmp = DumpBDD($set, \%names);
is($dmp, "A (B (T) (F)) (F)", "first makeSet()");
$set = AI::PBDD::makeSet(\@vars, 1, 1);
$dmp = DumpBDD($set, \%names);
is($dmp, "B (T) (F)", "second makeSet()");
AI::PBDD::kill();
}
{
#
# exists
#
( run in 0.954 second using v1.01-cache-2.11-cpan-49f99fa48dc )