boofun.core.representations.bdd

Binary Decision Diagram (BDD) representation for Boolean functions.

This module implements Reduced Ordered Binary Decision Diagrams (ROBDDs) for efficient representation and manipulation of Boolean functions.

Classes

BDD(n_vars)

Reduced Ordered Binary Decision Diagram.

BDDNode([var, low, high, value])

Node in a Binary Decision Diagram.

BDDRepresentation()

BDD representation for Boolean functions.
class boofun.core.representations.bdd.BDDNode(var: int | None = None, low: BDDNode | None = None, high: BDDNode | None = None, value: bool | None = None)[source]

Node in a Binary Decision Diagram.

var

Variable index (None for terminal nodes)

low

Low branch (False branch)

high

High branch (True branch)

is_terminal

Whether this is a terminal node

value

Terminal value (only for terminal nodes)

__init__(var: int | None = None, low: BDDNode | None = None, high: BDDNode | None = None, value: bool | None = None)[source]
class boofun.core.representations.bdd.BDD(n_vars: int)[source]

Reduced Ordered Binary Decision Diagram.

Implements a canonical representation of Boolean functions with efficient operations for evaluation, manipulation, and analysis.

__init__(n_vars: int)[source]

Initialize BDD.

Parameters:

n_vars – Number of variables

create_terminal(value: bool) → BDDNode[source]

Create terminal node.

create_node(var: int, low: BDDNode, high: BDDNode) → BDDNode[source]

Create or retrieve BDD node (with reduction).

Parameters:

  • var – Variable index

  • low – Low branch

  • high – High branch

Returns:

BDD node

evaluate(inputs: List[bool]) → bool[source]

Evaluate BDD with given inputs.

Parameters:

inputs – Boolean input values

Returns:

Boolean result

get_node_count() → int[source]

Get total number of nodes in BDD.

class boofun.core.representations.bdd.BDDRepresentation[source]

BDD representation for Boolean functions.

evaluate(inputs: ndarray, data: BDD, space: Space, n_vars: int) → bool | ndarray[source]

Evaluate BDD representation.

Parameters:

  • inputs – Input values (integer indices or binary vectors)

  • data – BDD

  • space – Evaluation space

  • n_vars – Number of variables

Returns:

Boolean result(s)

dump(data: BDD, space=None, **kwargs) → Dict[str, Any][source]

Export BDD representation.

convert_from(source_repr: BooleanFunctionRepresentation, source_data: Any, space: Space, n_vars: int, **kwargs) → BDD[source]

Convert from another representation to BDD.

Uses truth table to build BDD.

convert_to(target_repr: BooleanFunctionRepresentation, source_data: Any, space: Space, n_vars: int, **kwargs) → ndarray[source]

Convert BDD to another representation.

create_empty(n_vars: int, **kwargs) → BDD[source]

Create empty BDD (constant False).

is_complete(data: BDD) → bool[source]

Check if BDD is complete (has root node).

time_complexity_rank(n_vars: int) → Dict[str, int][source]

Return time complexity for BDD operations.

get_storage_requirements(n_vars: int) → Dict[str, int][source]

Return storage requirements for BDD representation.