view release on metacpan or  search on metacpan

lib/AI/PBDD.pm  view on Meta::CPAN

use constant BDD_REORDER_WIN2 => 1;
use constant BDD_REORDER_WIN3 => 2;
use constant BDD_REORDER_SIFT => 3;
use constant BDD_REORDER_RANDOM => 4;


@ISA = qw(Exporter DynaLoader);

@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
// ref counting
		 ref
		 deref
		 localDeref
// BDD operations
		 and
		 or
		 andTo
		 orTo
		 nand
		 nor
		 xor
		 ite
		 imp
		 biimp
		 not
                 makeSet
		 exists
		 forall
		 relProd
		 restrict
		 constrain
// variables replacement
		 createPair
		 deletePair
		 replace
		 showPair
// BDD analysis
		 support
		 nodeCount
		 satOne
		 satCount
// printing
		 printDot
		 printSet
		 print
// debugging
		 printStats                 
		 checkPackage
		 debugPackage
		 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 {
  my ($bdd, $vars_ignored) = @_;

  if (!defined($vars_ignored)) {
    return satCount__I($bdd);
  } else {
    return satCount__II($bdd, $vars_ignored);
  }
}

sub printDot {
  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);
}

1;

__END__

=head1 AI::PBDD

Perl wrapper for the BuDDy C library

=head1 SYNOPSIS

  use AI::PBDD qw(init createBDD and printDot kill);

  init(100, 100000);

  my $var1 = createBDD();
  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 

=item B<init($nvars, $nnodes))>

Initialize the BDD package using the given number of variables and nodes.

=item B<gc>

Invoke garbage collection.

=item B<verbose($be_verbose)>

Make the BDD package verbose or non-verbose.

=item B<kill>

Close the BDD package and cleanup.

=back

=head2 SIMPLE BDD OPERATIONS

=over 4

=item B<$bddone = getOne>

Returns the BDD constant 1.

=item B<$bddzero = getZero>

Returns the BDD constant 0.

=item B<$bdd = createBDD>

Returns a new BDD variable.

=item B<$nvars = getVarCount>

Returns the number of BDD variables currently in the system.

=item B<$bdd = getBDD($idx)>

Returns the BDD at the given index C<$idx> (ranked after calling C<createBDD>).

lib/AI/PBDD.pm  view on Meta::CPAN

=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

=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)>

=item B<$cnt = satCount($bdd,$nvars)>

Number of minterms that satisfy C<$bdd>. The number of minterms is computed by considering all of the variables in the package (defined with the call to the C<init> function), but it is possible to specify the number of variables C<$nvars> to be igno...

=back

=head2 PRINTING

=over 4

=item B<printDot($bdd)>

=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.

=item B<$ok = checkPackage>

Return 0 if something is wrong.

=item B<debugPackage>

Debug the BDD package.

=item B<$ok = debugBDD($bdd)>

Debug C<$bdd> in the BDD package. Return 0 if something is wrong.

=back

=head2 LOW LEVEL ACCESS

=over 4

=item B<$idx = internal_index($bdd)>

Get the index of a BDD variable.

=item B<$cnt = internal_refcount($bdd)>

Get the number of references to a BDD variable.

=item B<$bool = internal_isconst($bdd)>

Returns 1 if the BDD is either 0 or 1.

=item B<$bool = internal_constvalue($bdd)>

If C<$bdd> is either 0 or 1, it returns that value.

=item B<$bool = internal_iscomplemented($bdd)>

Returns 1 if the BDD is complemented.

=item B<$bdd_then = internal_then($bdd)>

Get the THEN-node of a BDD.

=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