AlgebraicDecisionDiagrams

Monomial

Specifies a monomial as a coefficient of numeric type T and a sorted list of variable indices. We assume the index 0 represents the constant (variable-free) monomial.

MultilinearExpression

Implements a multilinear expression data type as a dictionary of monoids to coefficients.

Examples

```julia

Creates a constant expression

@show c = MultilinearExpression(7.4)

Creates expressions with single term

@show e1 = MultilinearExpression(4.0,1) @show e2 = MultilinearExpression(3.0,1,3) ````

Creates an expression with given coefficient and variables (indices).

Creates an expression with a single constant c

Creates an expression with a single term (given as a pair monomial => coefficient

Implements a generic decision diagram whose leaves are of given type T

We can't know the number of nodes in advance (to traversing the diagram).

Returns the complement of the function.

Returns the conjunction of the Boolean functions.

Returns the disjunction of the Boolean functions.

apply(OP,α,β,opcache,vcache)

Recursively computes α OP β and cache results.

Parameters

• OP: operation to apply to leaves
• α,β: decision diagrams
• opcache: cache of applied operations
• vcache: cache of terminal values

Returns a Diagram canonical representation of α OP β, where OP is some binary operator.

apply(f::Function, α::DecisionDiagram)

Returns the application of function f to α.

Creates Diagram representing indicator function on given variable. If complement is true, then returns complement indicator.

Marginalize a variable var from function α.

" nliteral(index::Int)

Creates a negated literal (an indicator over Boolean constants) for variable index.

" pliteral(index::Int)

Creates a positive literal (an indicator over Boolean constants) for variable index.

reduce(α::DecisionDiagram)

Returns the canonical form of the decision diagram α. A diagram is canonical iff:

• no two terminals are assigned to the same value
• no two nodes have are labeled by the same variable and have the same two reduced children low and high with identical ids

reduce(α::DecisionDiagram{T}, cache::Dict{Tuple{Int,Int,Int},DecisionDiagram{T}}, vcache::Dict{T,DecisionDiagram{T}})

Returns the canonical form of decision diagram α using node and value caches. A diagram is canonical iff: - no two terminals are assigned to the same value - no two nodes have are labeled by the same variable and have the same two reduced children low and high with identical ids

Arguments

• α: decision diagram to reduce.
• cache: cache of inner nodes (identified by ids of variable, low and high children).
• vcache::Dict{T,DecisionDiagram{T}}: cache of terminal nodes identified by the associated value.

restrict(α::DecisionDiagram, var::Int, value::Bool=true)

Returns the canonical form of the function α constrained at variable var=value.

Example

x, y = variable(1), variable(2)
f = (one(x)-x)*(one(y)-1) + x*y
g = Terminal(4)*(one(x)-x) + Terminal(2)*x
h = f + g
r1 = restrict(h,1,false)
r2 = h | (2 => true) # shorthand for restrict(h,2,true)
r3 = h | (y => true) # same as above

Returns the product of the respective functions.

Returns the subtraction of the respective functions.

A decision diagram is composed of other decision diagrams.

Iterate over the pairs monomials => coeeficient in the expression.

Depth-first search traversal.

Returns the number of monomials in the expression.

Returns the number of nodes in the diagram.

Returns the multiplicative identity expression.

Multiplicative identity for terminals of type T

Returns the aditivity identity expression.

Additive identity for terminals of type T