BDD

Module summary

Implements the Binary Decision Diagram data type.

Defines the “original” BDD-related machinery (as opposed to the simplification defined in varseq.VarSeq), including actual simultaneous variable reordering (inspired by Rudell’93) and other BDD alignment-related functions, along with technical utilities (such as load/save to file, etc.). A simple auxiliary class node keeps the necessary data related to BDD nodes.

Tests coverage: BDD_test

(In the implementation details below, click on class/function names for additional documentation and links to the source code.)

❖❖❖

Implements classes:

`BDD`([N, vars, weighted])	Encodes a BDD and implements layer-ordering (revision) methods.
`node`(id[, hi, lo, layer])	Represents a BDD node, with the following attributes.

Implements functions (outside the classes above):

`intersect`(A, B)	Produces an intersection BDD of `A` and `B`.
`simscore`(seq_A, seq_B[, p_B])	Calculates a 'similarity score' between A and B.

❖❖❖

Implementation details

❖❖❖

BDD

class BDD.BDD(N=2, vars=None, weighted=False)[source]

Encodes a BDD and implements layer-ordering (revision) methods.

N

number of variables (equals number of layers - 1)

Type: int

layers

a list of layers (sets/hashes), including {T, F}-nodes

Type: list

nodes

a set/hash of nodes, key by node ID

Type: dict

vars

variables associated with layers

Type: list

T,F

pointers to True and False sink nodes

Type: node

weighted

a flag whether arcs have weights

Type: bool

weights

arc weights, keys: (id_from, id_to, arc_type) (with the latter either ‘hi’, or ‘lo’)

Type: dict

Public Methods:

`__init__`([N, vars, weighted])	Defines an empty BDD with N variables.
`width`()	Returns BDD width (max no.
`link`(parent, child[, etype, edge_weight])	Creates a link between two nodes in the BDD.
`llink`(parent, child[, etype, edge_weight])	Creates a link between two nodes.
`__len__`()	Returns no of variables (layers, except the terminal).
`n`(i)	Returns size of the i-th layer.
`p`(a)	Returns position (0-based layer index) of variable `a`.
`size`()	Returns the size of the BDD (total no.
`new_node_name`()	Returns a unique name for the next node to be created.
`dump_gv`([layerCapt, x_prefix, node_labels])	Exports the BDD to the Graphviz format (`.dot`).
`addnode`(parent_node[, arc, node_id, edge_weight])	Adds a node and updates aux info as necessary.
`swap_up`(layer_idx)	Swaps the layer with the one immediately above it (in-place).
`sift`(var, pos)	Sifts variable `var` (by name) to (0-based) position `pos`.
`gsifts`(with_whom[, start_order])	Performs greedy sifts to align with `with_whom`.
`save`(filename)	Saves a BDD to a text file.
`load`(filename[, weighted])	Loads a BDD from a (text) file.
`random`([N, p, weighted])	Generates a random BDD with N variables (N+1 layers).
`profile`()	Returns a BDD "profile" -- an (almost) BFS-ordered list of nodes.
`show`([dir, filename, layerCapt, x_prefix, ...])	Shows the diagram on the screen (saving the auxiliary pdf).
`align_to`(vars_order[, inplace])	Revises the BDD to a given order.
`OA_bruteforce`(with_what[, LR])	Finds the best (smallest) alignment with BDD `with_what`.
`is_reduced`()	Checks if the BDD is quasi-reduced (no "redundant" nodes).
`make_reduced`()	Makes the BDD quasi-reduced.
`rename_vars`(ren_dict)	Helper function: renames variables.
`shuffle_vars`()	Randomly renames the variables (shuffles their order).
`is_aligned`(to_what)	Checks if the BDD is aligned with `to_what`.
`get_value`(x)	Finds the terminal node (T or F) -- an endpoint for `x`.
`truth_table`()	Returns a "truth table" for the encoded Boolean function.
`is_equivalent`(B)	Checks if two BDDs (A and B) are equivalent.
`shortest_path`()	Finds a shortest-path in O(no-of-nodes) time.
`simscore`(B)	Computes a simscore with another diagram, B (see `simscore()`).

OA_bruteforce(with_what, LR=False)[source]

Finds the best (smallest) alignment with BDD with_what.

Uses brute-force enumeration of all possible orders.

Parameters

with_what (BDD) – target diagram.
LR (bool) – if set, layer-reduces each candidate BDD.

Returns

A tuple of values

alternatives (int): number of alternative optima

A_aligned (list): of A-aligned (in each optimum)

B_aligned (list): of B-aligned (in respective optimum)

addnode(parent_node, arc='hi', node_id=None, edge_weight=0.0)[source]

Adds a node and updates aux info as necessary.

Parameters

parent_node (node) – parent node pointer,
arc (str) – arc type, hi or lo,
node_id – node name. If None is provided, the value is derived from BDD.BDD.new_node_name(),
edge_weight (float) – edge weight

Returns

The created node as a BDD.node object.

align_to(vars_order, inplace=False)[source]

Revises the BDD to a given order.

(with a series of consecutive sifts)

dump_gv(layerCapt=True, x_prefix='x', node_labels=None)[source]

Exports the BDD to the Graphviz format (.dot).

Parameters

layerCapt (bool) – whether to generate layer captions.
x_prefix (str) – a prefix to be shown for layer name (default ‘x’)

Returns

a Digraph object (see graphviz package).

get_value(x)[source]

Finds the terminal node (T or F) – an endpoint for x.

Returns a terminal node ID corresponding to the variable choices in x.

Parameters

x (dict) – of {var_name: value}, where value is in {0,1}.

Returns

A tuple of values

terminal (bool or -1):
terminal node corresponding to the path implied by x, encoded as Boolean (or -1 if error)

cost (float):
if the BDD is weighted, cost of the path.

gsifts(with_whom, start_order=None)[source]

Performs greedy sifts to align with with_whom.

Runs a simplistic implementation of Rudell’93 sifting alorithm extension to minimize |A|+|B|

starts with aligning to self or start_order (if given)

is_aligned(to_what)[source]: Checks if the BDD is aligned with to_what.

is_equivalent(B)[source]

Checks if two BDDs (A and B) are equivalent.

Equivalent in the sense that they define the same Boolean function and the corresponding path costs coincide. Checks:

if the corresponding truth tables coincide.

(if the BDD is weighted) if all paths have the same costs.

Returns

A tuple of

result (bool): whether the diagrams are equivalent,

message (str): information regarding the difference, if found.

is_reduced()[source]: Checks if the BDD is quasi-reduced (no “redundant” nodes).

link(parent, child, etype='hi', edge_weight=0.0)[source]

Creates a link between two nodes in the BDD.

(Saving auxiliary info as appropriate)

Parameters

parent (int) – parent node id
child (int) – child node id
etype (str) – edge type, hi or lo (default hi)
edge_weight (float) – edge weight (default 0.0)

llink(parent, child, etype='hi', edge_weight=0.0)[source]

Creates a link between two nodes.

A version of BDD.BDD.link() that takes BDD.node objects as arguments instead of node IDs.

load(filename, weighted=False)[source]: Loads a BDD from a (text) file.

Note

The format is described in save().

make_reduced()[source]

Makes the BDD quasi-reduced.

Swaps each layer back and forth, starting from the last one, (which makes sure the results is quasi-reduced due to BDD.BDD.swap() implementation.)

n(i)[source]: Returns size of the i-th layer.

new_node_name()[source]

Returns a unique name for the next node to be created.

Picks the one to re-cycle after some node deletions, when available; when it is not – just takes the max_id+1 (adjusting the max_id)

p(a)[source]: Returns position (0-based layer index) of variable a.

profile()[source]

Returns a BDD “profile” – an (almost) BFS-ordered list of nodes.

Note

This is used to determine, e.g., if the generated instance is unique. A ‘profile’ is a string of the format <vars>:<BFS-nodes>, where:

<vars> : comma-separated variable names by layer;
<BFS-nodes> : comma-separated list of node-numbers (not IDs!) in a BFS-traverse order

classmethod random(N=5, p=0.5, weighted=False)[source]

Generates a random BDD with N variables (N+1 layers).

Layers are numbered with consecutive integers by default, starting with 1.

Parameters

N (int) – number of variables (results in N+1 layers, incl. T,F)
p (float) – tree size parameter 0 will generate a non-random exponential-sized diagram, 1 will result in a single node per layer.
weighted (bool) – whether to generate a weighted diagram.

Returns

A generated BDD.

rename_vars(ren_dict)[source]

Helper function: renames variables.

Parameters: ren_dict (dict) – a dict of <= BDD.N labels in the form {before: after}

save(filename)[source]

Saves a BDD to a text file.

Parameters: filename (string) – destination file name.

Note

File format is as follows.

File header, the first two lines

N= <no-of-layers>

vars= <comma-separated layer labels>

Then, one node description = one line of the format:
id : hi , lo

where id is node’s ID, hi and lo are IDs of the nodes corresponding to one- and zero- pointers of the node ID. The procedure performs breadth-first search and just saves all the nodes.

Three nodes have reserved ID values:

Root node: 0

True terminal: -1

False terminal: -2

shortest_path()[source]

Finds a shortest-path in O(no-of-nodes) time.

Returns: node labels (using node IDs as keys) corresponding to a shortest path from the current node to True terminal.
Return type: dict

Note

Expects the diagram to be BDD.weighted. (An unweighted version, in terms of ‘number of hops’, does not make any sense for a quasi-reduced BDD: the answer would be len(self).)

show(dir='tmp', filename='showfunc.dot', layerCapt=True, x_prefix='x', node_labels=None)[source]

Shows the diagram on the screen (saving the auxiliary pdf).

Generates a .dot file and compiles it to .pdf. Requires graphviz (dot program)

Parameters

dir (str) – directory to place files (default: tmp)
filename (str) – .dot filename (default: showfunc.dot)
layerCapt (bool) – whether to show layer caption (default: True)
x_prefix (str) – a prefix for variable captions (default: x)
node_labels (dict) – node labels to display (optional).

shuffle_vars()[source]: Randomly renames the variables (shuffles their order).

sift(var, pos)[source]

Sifts variable var (by name) to (0-based) position pos.

Uses BDD.sift() under the hood, in-place operation.

simscore(B)[source]: Computes a simscore with another diagram, B (see simscore()).

size()[source]: Returns the size of the BDD (total no. of nodes).

swap_up(layer_idx)[source]

Swaps the layer with the one immediately above it (in-place).

(by index ! in-place operation)

Parameters: layer_idx (int) – number (0-based index) of the layer to be ‘’bubbled up’’

Note

Operation takes O (no-of-nodes in the upper layer) time. Drops the layer being swapped. Then iterates through the nodes of the layer immediately above it and creates nodes as necessary (re-cycling new nodes to avoid redundancy: a quasi-reduced BDD keeps this property)

truth_table()[source]

Returns a “truth table” for the encoded Boolean function.

Returns:

pandas dataframe: column numbers correspond to variable names with two additional columns: Terminal for the function value (of Boolean type) and Cost if the diagram is BDD.weighted.

width()[source]: Returns BDD width (max no. nodes in a layer).

❖❖❖

node

class BDD.node(id, hi=None, lo=None, layer=-1)[source]

Represents a BDD node, with the following attributes.

id: an integer node ID

hi: a pointer to the hi-node

lo: a pointer to the lo-node

layer: layer number (id)

Note

There are special node IDs: 0 for the root, -1 for True sink, -2 for the False sink.

Public Methods:

`__init__`(id[, hi, lo, layer])	A simple class constructor.
`link`(to_whom[, arc])	Helper function: links the node to another one.

link(to_whom, arc='hi')[source]: Helper function: links the node to another one.

❖❖❖

Functions

BDD.intersect(A, B)[source]

Produces an intersection BDD of A and B.

Notes

BDDs need to be order-associated (same vars in the same order).

Returns: an intersection BDD.
Return type: BDD

BDD.simscore(seq_A, seq_B, p_B=None)[source]

Calculates a ‘similarity score’ between A and B.

The function has nothing to do with other data structures, technically: it just calculates the normalized number of inversions between the two ordered lists of variables (which we call ‘similarity score’).

Parameters

seq_A (list) – sequence A
seq_B (list) – sequence B to compare
p_B (dict) – dict of element positions in B (default: None, will be built)

Returns

share of possible inversions.

Return type

number (between 0 and 1)

Examples

>>> simscore([1,2,3], [1,2,3])
1.0

>>> simscore([1,2,3], [3,2,1])
0.0

>>> simscore([1,2,3], [1,3,2])
0.6666666666666667

>>> simscore([1,2,3,4,5,6,7], [5,6,3,4,2,7,1])
0.33333333333333337