AI-PBDD
view release on metacpan or search on metacpan
},
"name" : "AI-PBDD",
"no_index" : {
"directory" : [
"t",
"inc"
]
},
"prereqs" : {
"build" : {
"requires" : {
"ExtUtils::MakeMaker" : 0
}
},
"configure" : {
"requires" : {
"ExtUtils::MakeMaker" : 0
}
},
"runtime" : {
"requires" : {}
}
},
"release_status" : "stable",
"version" : "0.01"
}
---
abstract: unknown
author:
- 'Gianluca Torta <torta@di.unito.it>'
build_requires:
ExtUtils::MakeMaker: 0
configure_requires:
ExtUtils::MakeMaker: 0
dynamic_config: 1
generated_by: 'ExtUtils::MakeMaker version 6.59, CPAN::Meta::Converter version 2.112150'
license: unknown
meta-spec:
url: http://module-build.sourceforge.net/META-spec-v1.4.html
version: 1.4
name: AI-PBDD
no_index:
directory:
- t
- inc
requires: {}
version: 0.01
CHECK_BDD (l);
CHECK_BDD (r);
bdd = bdd_appex (l, r, bddop_and, cube);
bdd_addref (bdd);
RETVAL=bdd;
}
OUTPUT:
RETVAL
int restrict(r, var)
int r
int var
CODE:
{
BDD bdd;
CHECK_BDD (r);
CHECK_BDD (var);
bdd = bdd_restrict (r, var);
bdd_addref (bdd);
RETVAL=bdd;
}
OUTPUT:
RETVAL
int constrain(f, c)
int f
int c
CODE:
lib/AI/PBDD.pm view on Meta::CPAN
nor
xor
ite
imp
biimp
not
makeSet
exists
forall
relProd
restrict
constrain
// variables replacement
createPair
deletePair
replace
showPair
// BDD analysis
support
nodeCount
satOne
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
=over 4
lib/AI/PBDD.pm view on Meta::CPAN
Same as C<deref>, since BuDDy does not distinguish between local and recursive derefs.
=back
=head2 BDD OPERATIONS
=over 4
=item B<$bdd = and($bdd1,$bdd2)>
BDD AND operation. The returned result is already referenced.
=item B<$bdd = or($bdd1,$bdd2)>
BDD OR operation. The returned result is already referenced.
=item B<$bdd1new = andTo($bdd1,$bdd2)>
BDD cumulative AND operation. The returned result is already referenced, while $bdd1 is de-referenced.
=item B<$bdd1new = orTo($bdd1,$bdd2)>
BDD cumulative OR operation. The returned result is already referenced, while $bdd1 is de-referenced.
=item B<$bdd = nand($bdd1,$bdd2)>
BDD NAND operation. The returned result is already referenced.
=item B<$bdd = nor($bdd1,$bdd2)>
BDD NOR operation. The returned result is already referenced.
=item B<$bdd = xor($bdd1,$bdd2)>
BDD XOR operation. The returned result is already referenced.
=item B<$bdd = ite($bdd_if,$bdd_then,$bdd_else)>
BDD ITE (If-Then-Else) operation, i.e. C<($bdd_if AND $bdd_then) OR (NOT $bdd_if AND $bdd_else)>. The returned result is already referenced.
=item B<$bdd = imp($bdd1,$bdd2)>
BDD IMPlication operation. The returned result is already referenced.
=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
=item B<$pair = createPair($vars_old,$vars_new)>
Create a function C<$pair: BDD variable -E<gt> BDD variable> that maps C<$vars_old-E<gt>[i]> to C<$vars_new-E<gt>[i]>.
=item B<deletePair($pair)>
Free the memory occupied by C<$pair>.
=item B<$bdd = replace($bdd1,$pair)>
Replace the variables in a BDD according to the given pair. The returned result is already referenced.
=item B<showPair($pair)>
Print a pair.
=back
=head2 BDD ANALYSIS
=over 4
lib/AI/PBDD.pm view on Meta::CPAN
=item B<printDot($bdd,$filename)>
Print the BDD as a Graphviz DOT model to STDOUT (or the given C<$filename>).
=item B<printSet($bdd)>
Print the BDD minterms to STDOUT.
=item B<print($bdd)>
Print the BDD in the native BuDDy representation to STDOUT.
=back
=head2 DEBUGGING
=over 4
=item B<printStats>
Print package statistics to STDOUT.
lib/AI/PBDD.pm view on Meta::CPAN
Set dynamic reordering heuristic. The possible values are:
=over 4
=item BDD_REORDER_NONE
No reordering.
=item BDD_REORDER_WIN2
Reordering using a sliding window of size 2. This algorithm swaps two adjacent variable blocks and if this results in more nodes then the two blocks are swapped back again. Otherwise the result is kept in the variable order. This is then repeated for...
=item BDD_REORDER_WIN3
Same as above but with a window size of 3.
=item BDD_REORDER_SIFT
Each block is moved through all possible positions. The best of these is then used as the new position. Potentially a very slow but good method.
=item BDD_REORDER_RANDOM
lib/AI/PBDD.pm view on Meta::CPAN
This man page documents "PBDD" version 0.01.
=head1 AUTHOR
Gianluca Torta
mailto:torta@di.unito.it
=head1 COPYRIGHT
Copyright (c) 2011 by Gianluca Torta. All rights reserved.
=head1 LICENSE
This package is free software; you can use, modify and redistribute
it under the same terms as Perl itself, i.e., at your option, under
the terms either of the "Artistic License" or the "GNU General Public
License".
The interface design and part of the C code and documentation are modifications of the JBDD package by Arash Vahidi. A copy of the JBDD licence can be found in the C<licences> directory of this package.
licences/license.JBDD view on Meta::CPAN
JBDD uses a public domain license based on zlib:
/*
JBDD -- a Java interface to CUDD and BuDDY
Copyright (C) 2003-2004 Arash Vahidi
This software is provided 'as-is', without any express or implied
warranty. In no event will the authors be held liable for any damages
arising from the use of this software.
Permission is granted to anyone to use this software for any purpose,
including commercial applications, and to alter it and redistribute it
freely, subject to the following restrictions:
1. The origin of this software must not be misrepresented; you must not
claim that you wrote the original software. If you use this software
in a product, an acknowledgment in the product documentation would be
appreciated but is not required.
2. Altered source versions must be plainly marked as such, and must not be
misrepresented as being the original software.
3. This notice may not be removed or altered from any source distribution.
Arash Vahidi (vahidi [at] users.sourceforge.net)
*/
my $bdd = AI::PBDD::relProd($bdd4, $bdd5, $bdd2);
my $dmp = DumpBDD($bdd, \%names);
is($dmp, "A (C (T) (F)) (F)", "relProd()");
AI::PBDD::kill();
}
{
#
# restrict
#
AI::PBDD::init(100,1000000);
my %names = ();
my $bdd1 = AI::PBDD::createBDD();
$names{AI::PBDD::internal_index($bdd1)} = 'A';
my $bdd2 = AI::PBDD::createBDD();
$names{AI::PBDD::internal_index($bdd2)} = 'B';
my $bdd3 = AI::PBDD::and($bdd1,$bdd2);
my $bdd = AI::PBDD::restrict($bdd3, $bdd1);
my $dmp = DumpBDD($bdd, \%names);
is($dmp, "B (T) (F)", "first restrict()");
$bdd = AI::PBDD::restrict($bdd3, AI::PBDD::not($bdd1));
$dmp = DumpBDD($bdd, \%names);
is($dmp, "F", "second restrict()");
AI::PBDD::kill();
}
{
#
# constrain
#
AI::PBDD::init(100,1000000);
my %names = ();
( run in 0.592 second using v1.01-cache-2.11-cpan-49f99fa48dc )