# AlgebraicDecisionDiagrams

AlgebraicDecisionDiagrams.MonomialType
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.

AlgebraicDecisionDiagrams.MultilinearExpressionType
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) 

AlgebraicDecisionDiagrams.applyMethod
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
AlgebraicDecisionDiagrams.reduceMethod
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
AlgebraicDecisionDiagrams.reduceMethod

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.
AlgebraicDecisionDiagrams.restrictFunction
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`