LogicCircuits.UtilsModule

Module with general utilities and missing standard library features that could be useful in any Julia project

LogicCircuits.Utils.LitType

Literals are represented as 32-bit signed integers. Positive literals are positive integers identical to their variable. Negative literals are their negations. Integer 0 should not be used to represent literals.

Base.eltypeMethod

Find a type that can capture all column values

Base.isdisjointMethod

Are the given sets disjoint (no shared elements)?

LogicCircuits.Utils.imputeMethod

Return a copy of Imputed values of X (potentially statistics from another DataFrame)

For example, to impute using same DataFrame:

impute(X; method=:median)

If you want to use another DataFrame to provide imputation statistics:

impute(test_x, train_x; method=:mean)

Supported methods are :median, :mean, :one, :zero

LogicCircuits.Utils.make_missing_mcarMethod
make_missing_mcar(d::DataFrame; keep_prob::Float64=0.8)

Returns a copy of dataframe with making some features missing as MCAR, with keep_prob as probability of keeping each feature.

LogicCircuits.BddType

A Binary Decision Diagram.

  • index: the vertex variable (-1 if terminal vertex
  • low: low child vertex of BDD (undef if terminal vertex)
  • high: high child vertex of BDD (undef if terminal vertex)
  • value: terminal boolean value
  • id: unique identifier
LogicCircuits.BitCircuitType

A bit circuit is a low-level representation of a logical circuit structure.

They are a "flat" representation of a circuit, essentially a bit string, that can be processed by lower level code (e.g., GPU kernels)

The wiring of the circuit is captured by two matrices: nodes and elements.

  • Nodes are either leafs or decision (disjunction) nodes in the circuit.
  • Elements are conjunction nodes in the circuit.
  • In addition, there is a vector of layers, where each layer is a list of node ids. Layer 1 is the leaf/input layer. Layer end is the circuit root.
  • And there is a vector of parents, pointing to element id parents of decision nodes.

Nodes are represented as a 4xN matrix where

  • nodes[1,:] is the first element id belonging to this decision
  • nodes[2,:] is the last element id belonging to this decision
  • nodes[3,:] is the first parent index belonging to this decision
  • nodes[4,:] is the last parent index belonging to this decision

Elements belonging to node i are elements[:, nodes[1,i]:nodes[2,i]] Parents belonging to node i are parents[nodes[3,i]:nodes[4,i]]

Elements are represented by a 3xE matrix, where

  • elements[1,:] is the decision node id (parents of the element),
  • elements[2,:] is the prime node id (child of the element)
  • elements[3,:] is the sub node id (child of the element)
LogicCircuits.GateTypeType

A trait hierarchy denoting types of nodes GateType defines an orthogonal type hierarchy of node types, not circuit types, so we can dispatch on node type regardless of circuit type. See @ref{https://docs.julialang.org/en/v1/manual/methods/#Trait-based-dispatch-1}

LogicCircuits.PlainStructConstantNodeType

A plain structured logical constant leaf node, representing true or false. These are the only structured nodes that don't have an associated vtree node (cf. SDD file format)

LogicCircuits.SddConstantNodeType

A SDD logical constant leaf node, representing true or false. These are the only structured nodes that don't have an associated vtree node (cf. SDD file format)

Base.:!=Method

Returns whether the two given boolean functions are not equivalent.

Base.:==Method

Returns whether the two given boolean functions are equivalent.

Base.:|Method

Returns a new reduced Bdd restricted to instantiation X.

Base.:⊻Method

Returns a xor of the given boolean functions.

Base.deepcopyFunction
deepcopy(n::LogicCircuit, depth::Int64)

Recursively create a copy circuit rooted at n to a certain depth depth

Base.hashMethod
hash(α::Bdd, h::UInt)::UInt

Returns a unique hash for the whole BDD.

Base.mergeMethod
merge(root::LogicCircuit, or1::LogicCircuit, or2::LogicCircuit)

Merge two circuits.

Base.readMethod
Base.read(io::IO, ::Type{PlainLogicCircuit}, ::FnfFormat)

Read CNF/DNF from file.

Base.readMethod
Base.read(file::AbstractString, ::Type{C}) where C <: LogicCircuit

Reads circuit from file; uses extension to detect format type, for example ".sdd" for SDDs.

Base.signMethod

Returns 0 if x is not a literal; else returns the literal's sign.

Base.sizeMethod

Returns the number of nodes in the BDD graph.

Base.splitMethod
split(root::LogicCircuit, (or, and)::Tuple{LogicCircuit, LogicCircuit}, var::Var; depth=0, sanity_check=true)

Return the circuit after spliting on edge edge and variable var

Base.stringMethod

Return string representation of Bdd α.

Base.writeMethod
Base.write(file::AbstractString, circuit::LogicCircuit)

Writes circuit to file; uses file name extention to detect file format.

Base.writeMethod
write(file::AbstractString, vtree::PlainVtree)

Saves a vtree in the given file path based on file format. Supported formats:

  • ".vtree" for Vtree files
  • ".dot" for dot files
Base.writeMethod
Base.write(io::IO, fnf::LogicCircuit, ::FnfFormat)

Write CNF/DNF to file.

Base.writeMethod
Base.write(files::Tuple{AbstractString,AbstractString}, circuit::StructLogicCircuit)

Saves circuit and vtree to file.

Base.xorMethod

Exclusive logical disjunction (XOR)

DirectedAcyclicGraphs.find_inodeMethod

Find an inner vtree node that has left in its left subtree and right in its right subtree. Supports nothing as a catch-all for any node

DirectedAcyclicGraphs.foldupMethod
foldup(node::LogicCircuit, 
    f_con::Function, 
    f_lit::Function, 
    f_a::Function, 
    f_o::Function)::T where {T}

Compute a function bottom-up on the circuit. f_con is called on constant gates, f_lit is called on literal gates, f_a is called on conjunctions, and f_o is called on disjunctions. Values of type T are passed up the circuit and given to f_a and f_o through a callback from the children.

DirectedAcyclicGraphs.foldup_aggregateMethod
foldup_aggregate(node::LogicCircuit, 
    f_con::Function, 
    f_lit::Function, 
    f_a::Function, 
    f_o::Function, 
    ::Type{T})::T where T

Compute a function bottom-up on the circuit. f_con is called on constant gates, f_lit is called on literal gates, f_a is called on conjunctions, and f_o is called on disjunctions. Values of type T are passed up the circuit and given to f_a and f_o in an aggregate vector from the children.

DirectedAcyclicGraphs.lcaMethod

Compute the lowest common ancestor of two vtree nodes Warning: this method uses an incomplete varsubset check for descends_from and is only correct when v and w are part of the same larger vtree.

LogicCircuits.:¬Method
(¬)(α::Bdd)::Bdd
(¬)(x::Integer)::Bdd
(¬)(x::Bool)::Bool

Negates this boolean function.

LogicCircuits.:∧Method
(∧)(α::Bdd, β::Bdd)::Bdd
(∧)(x::Integer, β::Bdd)::Bdd
(∧)(α::Bdd, x::Integer)::Bdd
(∧)(x::Integer, y::Integer)::Bdd
(∧)(x::Bool, y::Bool)::Bool

Returns a conjunction over the given boolean functions.

LogicCircuits.:∨Method
(∨)(α::Bdd, β::Bdd)::Bdd
(∨)(x::Integer, β::Bdd)::Bdd
(∨)(α::Bdd, x::Integer)::Bdd
(∨)(x::Integer, y::Integer)::Bdd
(∨)(x::Bool, y::Bool)::Bool

Returns a disjunction over the given boolean functions.

LogicCircuits.andMethod
and(α::Bdd, β::Bdd)::Bdd
and(x::Integer, β::Bdd)::Bdd
and(α::Bdd, x::Integer)::Bdd
and(x::Integer, y::Integer)::Bdd
and(Φ::Vararg{Bdd})::Bdd
and(Φ::AbstractVector{Bdd})::Bdd
and(Φ::Vararg{T})::Bdd where T <: Integer
and(Φ::AbstractVector{T})::Bdd where T <: Integer
and(Φ::Vararg{Union{T, Bdd}})::Bdd where T <: Integer

Returns a conjunction over the given boolean functions.

LogicCircuits.applyMethod

Returns a Bdd canonical representation of α ⊕ β, where ⊕ is some binary operator.

LogicCircuits.apply_stepMethod

Recursively computes α ⊕ β. If the result was already computed as an intermediate result, return the cached result in T.

LogicCircuits.atleast!Method

Constructs a BDD mapping to true if at least n literals in L are in the input; otherwise false.

LogicCircuits.atleastMethod

Constructs a BDD mapping to true if at least n literals in L are in the input; otherwise false.

LogicCircuits.atmost!Method

Constructs a BDD mapping to true if at most n literals in L are in the input; otherwise false.

LogicCircuits.atmostMethod

Constructs a BDD mapping to true if at most n literals in L are in the input; otherwise false.

LogicCircuits.bdd_varMethod

Returns a Bdd representing a single variable. If negative, negate variable.

LogicCircuits.cloneMethod

Clone the or node and redirect one of its parents to the new copy

LogicCircuits.conjoinMethod
conjoin(root::LogicCircuit, lit::Lit; callback::Function)

Return the circuit conjoined with th given literal constrains callback is called after modifying conjunction node

LogicCircuits.conjoinMethod
conjoin(s::SddLiteralNode, t::SddLiteralNode)::Sdd

Conjoin SDD Literal Nodes.

LogicCircuits.conjoinMethod
conjoin(arguments::Vector{<:PlainLogicCircuit})

Conjoins Plain LogicCircuits.

LogicCircuits.conjoinMethod
conjoin(arguments::Vector{<:PlainStructLogicCircuit})

Conjoins Structered LogicCircuits

LogicCircuits.convalsMethod

Computes all possible valuations of scope V as both conjunctions and instantiation values.

LogicCircuits.culledfreqsMethod

Returns an approximation (does not account for some repeated nodes) of how many times each variable is mentioned in α.

LogicCircuits.eliminateMethod

Eliminate a variable through disjunction. Equivalent to the expression (ϕ|x ∨ ϕ|¬x).

LogicCircuits.exactly!Method

Constructs a BDD mapping to true if exactly n literals in L are in the input; otherwise false.

LogicCircuits.exactlyMethod

Constructs a BDD mapping to true if exactly n literals in L are in the input; otherwise false.

LogicCircuits.forgetMethod
forget(α::Bdd, x::Integer)::Bdd = eliminate(α, x)
forget(α::Bdd, X::Union{Set, BitSet, AbstractVector{T}}) where T <: Integer

Returns the resulting BDD after applying the forget operation. Equivalent to $\phi|_x \vee \phi|_{\neg x}$.

LogicCircuits.forgetMethod
forget(root::LogicCircuit, is_forgotten::Function)

Forget variables from the circuit. Warning: this may or may not destroy the determinism property.

LogicCircuits.from_npbcMethod

Translates a cardinality constraint in normal pseudo-boolean constraint form into a BDD.

Since cardinality constraints correspond to having coefficients set to one, we ignore the C's.

Argument L corresponds to the vector of literals to be chosen from; b is how many literals in L are selected.

See Eén and Sörensson 2006.

LogicCircuits.implied_literalsFunction
implied_literals(root::LogicCircuit)::Union{BitSet, Nothing}

Compute at each node literals that are implied by the formula. nothing at a node means all literals are implied (i.e. the node's formula is false)

This algorithm is sound but not complete - all literals returned are correct, but some true implied literals may be missing.

LogicCircuits.infer_vtreeFunction
infer_vtree(root::LogicCircuit)::Vtree

Infer circuits vtree if the circuit is struct-decomposable. Otherwise return nothing.

LogicCircuits.is_atomMethod
is_atom(α::Bdd)::Bool

Returns whether the given Bdd node is an atomic formula (i.e. a variable, ⊥, ⊤, or literal).

LogicCircuits.is_litMethod
is_lit(α::Bdd)::Bool

Returns whether the given Bdd node represents a literal.

LogicCircuits.is_varMethod
is_var(α::Bdd)::Bool

Returns whether the given Bdd node represents a variable.

LogicCircuits.is_⊤Method
is_⊤(α::Bdd)::Bool

Returns whether the given Bdd node represents a ⊤.

LogicCircuits.is_⊥Method
is_⊥(α::Bdd)::Bool

Returns whether the given Bdd node represents a ⊥.

LogicCircuits.iscanonicalMethod
iscanonical(circuit::LogicCircuit, k::Int; verbose = false)

Does the given circuit have canonical Or gates, as determined by a probabilistic equivalence check?

LogicCircuits.isdeterministicFunction
isdeterministic(root::LogicCircuit)::Bool

Is the circuit determinstic? Note: this function is generally intractable for large circuits.

LogicCircuits.issatisfiableMethod
issatisfiable(root::LogicCircuit)::Bool

Determine whether the logical circuit is satisfiable (has a satisfying assignment). Requires decomposability of the circuit.

LogicCircuits.istautologyMethod

istautology(root::LogicCircuit)::Bool

Determine whether the logical circuit is a tautology (every assignment satisfies it; the sentence is valid). Requires decomposability and determinism of the circuit.

LogicCircuits.lit_valMethod

Returns whether a variable x appears as a positive literal in α, given that α is a conjunction of literals.

LogicCircuits.lit_vecMethod

Assumes ϕ is a full conjunction of literals. Returns ϕ as a zero-one vector and its scope.

LogicCircuits.loadMethod

Loads a BDD from given file.

Supported file formats:

  • CNF (.cnf);
  • DNF (.dnf);
  • BDD (.bdd).

To load as any of these file formats, simply set the filename with the desired extension.

Keyword arguments are passed down to the open function.

LogicCircuits.model_countFunction
model_count(root::LogicCircuit, num_vars_in_scope::Int = num_variables(root))::BigInt

Get the model count of the circuit. The num_vars_in_scope is set to number of variables in the circuit, but sometimes need to set different values, for example, if not every variable is mentioned in the circuit.

LogicCircuits.normal_formMethod

Runs a BFS on the mapping of parents, starting from either a ⊤ (true) or ⊥ (false) in order to find the corresponding CNF or DNF encoding.

LogicCircuits.orMethod
or(α::Bdd, β::Bdd)::Bdd 
or(x::Integer, β::Bdd)::Bdd
or(α::Bdd, x::Integer)::Bdd
or(x::Integer, y::Integer)::Bdd
or(Φ::Vararg{Bdd})::Bdd
or(Φ::AbstractVector{Bdd})::Bdd
or(Φ::Vararg{T})::Bdd where T <: Integer
or(Φ::AbstractVector{T})::Bdd where T <: Integer
or(Φ::Vararg{Union{T, Bdd}})::Bdd where T <: Integer

Returns a disjunction over the given boolean functions.

LogicCircuits.print_nfMethod

Pretty print BDD as a normal form (CNF or DNF).

Caution: may exponentially explode.

Alternatively, pretty prints using the given glyphs (default , and ¬).

ϕ = (1 ∧ ¬2) ∨ (2 ∧ 3)
print_nf(α; out = false)
ϕ = (1 ∧ ¬2) ∨ (2 ∧ 3)
print_nf(α; out = false, which = "dnf", glyphs = ['+', '*', '-'])
LogicCircuits.prob_equivMethod

Check equivalence using probabilistic equivalence checking. Note that this implentation may not have any formal guarantees as such.

LogicCircuits.prob_equiv_signatureFunction
prob_equiv_signature(circuit::LogicCircuit, k::Int)

Get a signature for each node using probabilistic equivalence checking. Note that this implentation may not have any formal guarantees as such.

LogicCircuits.process_mnistFunction

Processes the mnist dataset using the MNIST object from MLDataSets package MLDS_MNIST = the MNIST from MLDataSets labeled = whether to return the lables

LogicCircuits.reduce!Method

Reduce a Bdd rooted at α inplace, removing duplicate nodes and redundant sub-trees. Returns canonical representation of α.

LogicCircuits.respects_vtreeMethod

Does the circuit respect the given vtree? This function allows for constants in conjunctions, but only when a vtree node can be found where the left and right conjunct can be assigned to the left and right vtree.

LogicCircuits.sat_probFunction
sat_prob(root::LogicCircuit; varprob::Function)::Rational{BigInt}

Get the probability that a random world satisties the circuit. Probability of each variable is given by varprob Function which defauls to 1/2 for every variable.

LogicCircuits.save_bddMethod

Saves a BDD as a file.

Supported file formats:

  • CNF (.cnf);
  • DNF (.dnf);
  • BDD (.bdd).

To save as any of these file formats, simply set the filename with the desired extension.

Keyword arguments are passed down to the open function.

LogicCircuits.shallowhashFunction
shallowhash(α::Bdd, h::UInt = UInt64(0))

Returns a shallow hash for the given node (not BDD as a whole).

LogicCircuits.shannon!Method

Performs Shannon's Decomposition on the Bdd α, given a set of variables to isolate. Any decomposition that results in a ⊥ is discarded.

LogicCircuits.shannonMethod

Performs Shannon's Decomposition on the Bdd α, given a variable to isolate.

LogicCircuits.shannonMethod

Performs Shannon's Decomposition on the Bdd α, given a set of variables to isolate.

LogicCircuits.smoothMethod
smooth(root::LogicCircuit)

Create an equivalent smooth circuit from the given circuit.

LogicCircuits.smoothMethod
smooth(root::StructLogicCircuit)::StructLogicCircuit

Create an equivalent smooth circuit from the given circuit.

LogicCircuits.smooth_nodeMethod
smooth_node(node::LogicCircuit, missing_scope, lit_nodes)

Return a smooth version of the node where the missing_scope variables are added to the scope, using literals from lit_nodes

LogicCircuits.smooth_nodeMethod
smooth_node(node::StructLogicCircuit, parent_scope, scope, lit_nodes, vtree_leaves)

Return a smooth version of the node where the are added to the scope by filling the gap in vtrees, using literals from lit_nodes

LogicCircuits.split_candidatesMethod
split_candidates(circuit::LogicCircuit)::Tuple{Vector{Tuple{LogicCircuit, LogicCircuit}}, Dict{LogicCircuit, BitSet}}

Return the edges and variables which can be splited on

LogicCircuits.standardize_circuitMethod

Standardize the circuit:

  1. Children of or nodes are and nodes.
  2. Children of and nodes are or nodes.
  3. Each and node has exactly two children.

Note: for circuits with parameters this function will not keep the parameters equavalent.

LogicCircuits.to_intMethod

Returns 0 if x is not a literal; else returns an integer representation of x.

LogicCircuits.twenty_datasetsMethod
train, valid, test = twenty_datasets(name)

Load a given dataset from the density estimation datasets. Automatically downloads the files as julia Artifacts. See https://github.com/UCLA-StarAI/Density-Estimation-Datasets for a list of avaialble datasets.

LogicCircuits.zoo_cnfMethod
zoo_cnf(name)

Loads CNF file with given name from model zoo. See https://github.com/UCLA-StarAI/Circuit-Model-Zoo.

LogicCircuits.zoo_dnfMethod
zoo_dnf(name)

Loads DNF file with given name from model zoo. See https://github.com/UCLA-StarAI/Circuit-Model-Zoo.

LogicCircuits.zoo_jlcMethod
zoo_jlc(name)

Loads JLC file with given name from model zoo. See https://github.com/UCLA-StarAI/Circuit-Model-Zoo.

LogicCircuits.zoo_nnfMethod
zoo_nnf(name)

Loads NNF file with given name from model zoo. See https://github.com/UCLA-StarAI/Circuit-Model-Zoo.

LogicCircuits.zoo_sddMethod
zoo_sdd(name)

Loads SDD file with given name from model zoo. See https://github.com/UCLA-StarAI/Circuit-Model-Zoo.

LogicCircuits.zoo_vtreeMethod
zoo_vtree(name)

Loads Vtree file with given name from model zoo. See https://github.com/UCLA-StarAI/Circuit-Model-Zoo.

TikzGraphs.plotMethod
TikzGraphs.plot(lc::LogicCircuit; simplify=false)

Plots a LogicCircuit using TikzGraphs. Needt o have LaTeX installed.

TikzGraphs.plotMethod
TikzGraphs.plot(vtree::Vtree)

Plots a vtree using TikzGraphs. Need to have LaTeX installed.