LogicCircuits.Utils
— ModuleModule with general utilities and missing standard library features that could be useful in any Julia project
LogicCircuits.Utils.AbstractBitVector
— TypeRetro-fitted super type of all bit vectors
LogicCircuits.Utils.CuBitVector
— TypeCustom CUDA version of BitVector (lacking lots of functionality, just a container for now).
LogicCircuits.Utils.Lit
— TypeLiterals 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.
LogicCircuits.Utils.Var
— TypeVariables are represented as 32-bit unsigned integers
Base.eltype
— MethodFind a type that can capture all column values
Base.isdisjoint
— MethodAre the given sets disjoint (no shared elements)?
LogExpFunctions.logsumexp
— MethodMarginalize out dimensions dims
from log-probability tensor
LogicCircuits.Utils.always
— MethodAn array of 100% probabilities for the given element type
LogicCircuits.Utils.bagging_dataset
— MethodReturns an array of DataFrames where each DataFrame is randomly sampled from the original dataset data
LogicCircuits.Utils.batch
— FunctionCreate mini-batches
LogicCircuits.Utils.batch_size
— MethodBatch size of the dataset
LogicCircuits.Utils.bits_per_pixel
— MethodNormalize the given log-likelihood as bits per pixel in data
LogicCircuits.Utils.chunks
— MethodRetrieve chunks of bit vector
LogicCircuits.Utils.eachcol_unweighted
— MethodIterate over columns, excluding the sample weight column
LogicCircuits.Utils.example
— MethodGet the ith example
LogicCircuits.Utils.feature_values
— MethodGet the ith feature values
LogicCircuits.Utils.fully_factorized_log_likelihood
— MethodComputer the per-example log-likelihood of a fully factorized ML model on Bool data
LogicCircuits.Utils.get_bit
— MethodRetrieve the jth bit from a BitVector
chunk
LogicCircuits.Utils.get_weights
— MethodGet the weights from a weighted dataset.
LogicCircuits.Utils.impute
— MethodReturn 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.init_array
— MethodAn array of undetermined values (fast) for the given element type
LogicCircuits.Utils.isbatched
— MethodIs the dataset batched?
LogicCircuits.Utils.isbinarydata
— MethodIs the dataset binary?
LogicCircuits.Utils.iscomplete
— MethodIs the data complete (no missing values)?
LogicCircuits.Utils.iscomplete_col
— MethodIs the data column complete (no missing values)?
LogicCircuits.Utils.isfpdata
— MethodIs the dataset consisting of floating point data?
LogicCircuits.Utils.isgpu
— MethodCheck whether data resides on the GPU
LogicCircuits.Utils.issomething
— MethodIs the argument not nothing
?
LogicCircuits.Utils.isweighted
— MethodIs the dataset weighted?
LogicCircuits.Utils.lit2var
— MethodConvert a literal its variable, removing the sign of the literal
LogicCircuits.Utils.ll_per_example
— MethodNormalize the given log-likelihood by the number of examples in data
LogicCircuits.Utils.make_missing_mcar
— Methodmake_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.Utils.marginal_prob
— MethodCompute the marginal prob of each feature in a binary dataset.
LogicCircuits.Utils.never
— MethodAn array of 0% probabilities for the given element type
LogicCircuits.Utils.noop
— MethodFunction that does nothing
LogicCircuits.Utils.num_chunks
— MethodFor binary complete data, how many UInt64
bit strings are needed to store one feature?
LogicCircuits.Utils.num_examples
— Methodnum_examples(df::DataFrame)
Number of examples in data
LogicCircuits.Utils.num_features
— Methodnum_features(df::DataFrame)
Number of features in the data
LogicCircuits.Utils.num_variables
— MethodNumber of variables in the data structure
LogicCircuits.Utils.order_asc
— MethodOrder the arguments in a tuple in ascending order
LogicCircuits.Utils.pushrand!
— MethodPush element
into random position in vectorv
LogicCircuits.Utils.random_sample
— FunctionRandomly draw samples from the dataset with replacement
LogicCircuits.Utils.same_device
— MethodEnsure that x
resides on the same device as data
LogicCircuits.Utils.shuffle_examples
— Methodshuffle_examples(df::DataFrame)
Shuffle the examples in the data
LogicCircuits.Utils.similar!
— MethodReuse a given array if it has the right type and size, otherwise make a new one
LogicCircuits.Utils.soften
— FunctionTurn binary data into floating point data close to 0 and 1.
LogicCircuits.Utils.split_sample_weights
— MethodSplit a weighted dataset into unweighted dataset and its corresponding weights.
LogicCircuits.Utils.subseteq_fast
— MethodReplacement for BitSet.⊆ that does not allocate a new BitSet
LogicCircuits.Utils.threshold
— MethodThreshold a numeric dataset making it binary
LogicCircuits.Utils.to_cpu
— MethodMove data to the CPU
LogicCircuits.Utils.to_gpu
— MethodMove data to the GPU
LogicCircuits.Utils.uniform
— MethodAn array of uniform probabilities
LogicCircuits.Utils.var2lit
— MethodConvert a variable to the corresponding positive literal
LogicCircuits.Utils.variables
— FunctionGet the BitSet
of variables in the data structure
LogicCircuits.Utils.weigh_samples
— MethodCreate a weighted copy of the data set
LogicCircuits.false_sdd
— ConstantCanonical false Sdd node
LogicCircuits.structfalse
— ConstantThe unique splain tructured logical false constant
LogicCircuits.structtrue
— ConstantThe unique plain structured logical true constant
LogicCircuits.true_sdd
— ConstantCanonical true Sdd node
LogicCircuits.ApplyArgs
— TypeRepresentation of the arguments of an Apply call
LogicCircuits.ApplyCache
— TypeApply cache for the result of conjunctions and disjunctions
LogicCircuits.Bdd
— TypeA Binary Decision Diagram.
index
: the vertex variable (-1 if terminal vertexlow
: low child vertex of BDD (undef if terminal vertex)high
: high child vertex of BDD (undef if terminal vertex)value
: terminal boolean valueid
: unique identifier
LogicCircuits.BitCircuit
— TypeA 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.BitCircuit
— Methodconstruct a new BitCircuit
accomodating the given number of features
LogicCircuits.ConstantGate
— TypeA trait denoting constant leaf nodes of any type
LogicCircuits.Element
— TypeRepresents elements that are not yet compiled into conjunctions
LogicCircuits.GateType
— TypeA 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.GateType
— MethodGet the gate type trait of the given LogicCircuit
LogicCircuits.InnerGate
— TypeA logical gate that is an inner node
LogicCircuits.LeafGate
— TypeA logical gate that is a leaf node
LogicCircuits.LiteralGate
— TypeA trait denoting literal leaf nodes of any type
LogicCircuits.LogicCircuit
— TypeRoot of the logic circuit node hierarchy
LogicCircuits.NodeId
— TypeInteger identifier for a circuit node
LogicCircuits.NodeIds
— TypeThe BitCircuit ids associated with a node
LogicCircuits.PlainConstantNode
— TypeA plain logical constant leaf node, representing true or false
LogicCircuits.PlainLiteralNode
— TypeA plain logical literal leaf node, representing the positive or negative literal of its variable
LogicCircuits.PlainLogicCircuit
— TypeRoot of the plain logic circuit node hierarchy
LogicCircuits.PlainLogicInnerNode
— TypeA plain logical inner node
LogicCircuits.PlainLogicLeafNode
— TypeA plain logical leaf node
LogicCircuits.PlainStructConstantNode
— TypeA 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.PlainStructLiteralNode
— TypeA plain structured logical literal leaf node, representing the positive or negative literal of its variable
LogicCircuits.PlainStructLogicCircuit
— TypeRoot of the plain structure logic circuit node hierarchy
LogicCircuits.PlainStructLogicInnerNode
— TypeA plain structured logical inner node
LogicCircuits.PlainStructLogicLeafNode
— TypeA plain structured logical leaf node
LogicCircuits.PlainStruct⋀Node
— TypeA plain structured logical conjunction node
LogicCircuits.PlainStruct⋁Node
— TypeA plain structured logical disjunction node
LogicCircuits.PlainVtree
— TypeRoot of the plain vtree node hierarchy
LogicCircuits.Plain⋀Node
— TypeA plain logical conjunction node (And node)
LogicCircuits.Plain⋁Node
— TypeA plain logical disjunction node (Or node)
LogicCircuits.Sdd
— TypeRoot of the trimmed Sdd circuit node hierarchy
LogicCircuits.SddConstantNode
— TypeA 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)
LogicCircuits.SddInnerNode
— TypeA SDD logical inner node
LogicCircuits.SddLeafNode
— TypeA SDD logical leaf node
LogicCircuits.SddLiteralNode
— TypeA SDD logical literal leaf node, representing the positive or negative literal of its variable
LogicCircuits.SddMgr
— TypeRoot of the SDD manager node hierarchy
LogicCircuits.SddMgrInnerNode
— TypeSDD manager inner vtree node for trimmed SDD nodes
LogicCircuits.SddMgrLeafNode
— TypeSDD manager leaf vtree node for trimmed SDD nodes
LogicCircuits.Sdd⋀Node
— TypeA SDD logical conjunction node
LogicCircuits.Sdd⋁Node
— TypeA SDD logical disjunction node
LogicCircuits.StructLogicCircuit
— TypeRoot of the structure logic circuit node hierarchy
LogicCircuits.Unique⋁Cache
— TypeUnique nodes cache for decision nodes
LogicCircuits.Vtree
— TypeRoot of the vtree node hiearchy
LogicCircuits.XYPartition
— TypeRepresent an XY-partition that has not yet been compiled into a disjunction
LogicCircuits.⋀Gate
— TypeA trait denoting conjuction nodes of any type
LogicCircuits.⋁Gate
— TypeA trait denoting disjunction nodes of any type
Base.:!=
— MethodReturns whether the two given boolean functions are not equivalent.
Base.:==
— MethodReturns whether the two given boolean functions are equivalent.
Base.:|
— MethodReturns a new reduced Bdd restricted to instantiation X.
Base.:⊻
— MethodReturns a xor of the given boolean functions.
Base.deepcopy
— Functiondeepcopy(n::LogicCircuit, depth::Int64)
Recursively create a copy circuit rooted at n
to a certain depth depth
Base.hash
— Methodhash(α::Bdd, h::UInt)::UInt
Returns a unique hash for the whole BDD.
Base.merge
— Methodmerge(root::LogicCircuit, or1::LogicCircuit, or2::LogicCircuit)
Merge two circuits.
Base.read
— MethodBase.read(io::IO, ::Type{PlainLogicCircuit}, ::FnfFormat)
Read CNF/DNF from file.
Base.read
— MethodBase.read(file::AbstractString, ::Type{C}) where C <: LogicCircuit
Reads circuit from file; uses extension to detect format type, for example ".sdd" for SDDs.
Base.sign
— MethodReturns 0 if x is not a literal; else returns the literal's sign.
Base.size
— MethodReturns the number of nodes in the BDD graph.
Base.split
— Methodsplit(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.string
— MethodReturn string representation of Bdd α.
Base.write
— MethodBase.write(file::AbstractString, circuit::LogicCircuit)
Writes circuit to file; uses file name extention to detect file format.
Base.write
— Methodwrite(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.write
— MethodBase.write(io::IO, fnf::LogicCircuit, ::FnfFormat)
Write CNF/DNF to file.
Base.write
— MethodBase.write(files::Tuple{AbstractString,AbstractString}, circuit::StructLogicCircuit)
Saves circuit and vtree to file.
Base.xor
— MethodExclusive logical disjunction (XOR)
DirectedAcyclicGraphs.children
— MethodGet the children of a given inner node
DirectedAcyclicGraphs.depth
— MethodCompute the path length from vtree node n
to leaf node for variable var
DirectedAcyclicGraphs.find_inode
— MethodFind 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.find_leaf
— MethodFind the leaf in the vtree that represents the given variable
DirectedAcyclicGraphs.foldup
— Methodfoldup(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_aggregate
— Methodfoldup_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.lca
— MethodCompute 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.
DirectedAcyclicGraphs.num_nodes
— MethodHow many nodes are indexed by a given bit circuit?
LogicCircuits.:¬
— Method(¬)(α::Bdd)::Bdd
(¬)(x::Integer)::Bdd
(¬)(x::Bool)::Bool
Negates this boolean function.
LogicCircuits.:¬
— MethodLogical negation
LogicCircuits.:⇐
— MethodMaterial logical implication (reverse)
LogicCircuits.:⇒
— MethodMaterial logical implication
LogicCircuits.:⇔
— MethodBidirectional logical implication
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.:∧
— MethodLogical conjunction
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.:∨
— MethodLogical disjunction
LogicCircuits.Utils.variables
— Functionvariables(root::LogicCircuit)::BitSet
Get a bitset of variables mentioned in the circuit root
.
LogicCircuits.all_valuations
— MethodComputes all possible valuations of scope V and returns as a BitMatrix. Up to 64 variables.
LogicCircuits.and
— Methodand(α::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.and_nodes
— MethodGet the list of And nodes in a given circuit
LogicCircuits.apply
— MethodReturns a Bdd canonical representation of α ⊕ β, where ⊕ is some binary operator.
LogicCircuits.apply_step
— MethodRecursively computes α ⊕ β. If the result was already computed as an intermediate result, return the cached result in T.
LogicCircuits.atleast!
— MethodConstructs a BDD mapping to true if at least n literals in L are in the input; otherwise false.
LogicCircuits.atleast
— MethodConstructs a BDD mapping to true if at least n literals in L are in the input; otherwise false.
LogicCircuits.atmost!
— MethodConstructs a BDD mapping to true if at most n literals in L are in the input; otherwise false.
LogicCircuits.atmost
— MethodConstructs a BDD mapping to true if at most n literals in L are in the input; otherwise false.
LogicCircuits.balance_threads
— Methodassign threads to examples and decision nodes so that everything is a power of 2
LogicCircuits.balance_threads_2d
— MethodLogicCircuits.bdd_var
— MethodReturns a Bdd representing a single variable. If negative, negate variable.
LogicCircuits.canonical_constants
— MethodConstruct a mapping from constants to their canonical node representation
LogicCircuits.canonical_literals
— MethodConstruct a mapping from literals to their canonical node representation
LogicCircuits.canonicalize
— MethodGet the canonical compilation of the given XY Partition
LogicCircuits.canonicalize_compressed
— MethodGet the canonical compilation of the given compressed XY Partition
LogicCircuits.clone
— MethodClone the or
node and redirect one of its parents to the new copy
LogicCircuits.compile
— FunctionCreate new circuit nodes in the given context.
LogicCircuits.compile
— MethodCompile a given variable, literal, or constant
LogicCircuits.compress
— MethodCompress a given XY Partition (merge elements with identical subs)
LogicCircuits.conjoin
— FunctionConjoin nodes into a single circuit
LogicCircuits.conjoin
— Methodconjoin(root::LogicCircuit, lit::Lit; callback::Function)
Return the circuit conjoined with th given literal constrains callback
is called after modifying conjunction node
LogicCircuits.conjoin
— Methodfunction conjoin(s::Sdd, t::Sdd)::Sdd
Conjoins two SDDs.
LogicCircuits.conjoin
— MethodConjoin two SDDs
LogicCircuits.conjoin
— Methodconjoin(s::SddLiteralNode, t::SddLiteralNode)::Sdd
Conjoin SDD Literal Nodes.
LogicCircuits.conjoin
— Methodconjoin(arguments::Vector{<:PlainLogicCircuit})
Conjoins Plain LogicCircuits.
LogicCircuits.conjoin
— Methodconjoin(arguments::Vector{<:PlainStructLogicCircuit})
Conjoins Structered LogicCircuits
LogicCircuits.conjoin_cartesian
— MethodConjoin two SDDs when they respect the same vtree node
LogicCircuits.conjoin_descendent
— MethodConjoin two SDDs when one descends from the other
LogicCircuits.conjoin_indep
— MethodConjoin two SDDs in separate parts of the vtree
LogicCircuits.conjunctions
— MethodComputes all possible valuations of scope V as conjunctions.
LogicCircuits.constant
— MethodGet the logical constant in a given constant leaf node
LogicCircuits.construct_new_sdd_literal
— MethodHelper function to construct new SDD literal objects in SddMgrLeafNode constructor
LogicCircuits.convals
— MethodComputes all possible valuations of scope V as both conjunctions and instantiation values.
LogicCircuits.culledfreqs
— MethodReturns an approximation (does not account for some repeated nodes) of how many times each variable is mentioned in α.
LogicCircuits.disjoin
— FunctionDisjoin nodes into a single circuit
LogicCircuits.eliminate
— MethodEliminate a variable through disjunction. Equivalent to the expression (ϕ|x ∨ ϕ|¬x).
LogicCircuits.entails
— MethodDecide whether one sentence logically entails another
LogicCircuits.equivalent
— MethodDecide whether two sentences are logically equivalent
LogicCircuits.exactly!
— MethodConstructs a BDD mapping to true if exactly n literals in L are in the input; otherwise false.
LogicCircuits.exactly
— MethodConstructs a BDD mapping to true if exactly n literals in L are in the input; otherwise false.
LogicCircuits.fill_missing_vtree
— MethodConstruct a smoothed node from startvtr, when you get to endvtr insert the original node
LogicCircuits.forget
— Methodforget(α::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.forget
— Methodforget(root::LogicCircuit, is_forgotten::Function)
Forget variables from the circuit. Warning: this may or may not destroy the determinism property.
LogicCircuits.from_npbc
— MethodTranslates 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.fully_factorized_circuit
— FunctionGenerate a fully factorized circuit over the given range of variables
LogicCircuits.global_scope
— MethodGet the variable scope of the root of this vtree
LogicCircuits.has_single_child
— MethodDoes the bitcircuit node have a single child?
LogicCircuits.has_vars_contiguous
— MethodDoes the circuit have a contiguously indexed set of variables
LogicCircuits.implied_literals
— Functionimplied_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_vtree
— Functioninfer_vtree(root::LogicCircuit)::Vtree
Infer circuits vtree if the circuit is struct-decomposable. Otherwise return nothing
.
LogicCircuits.init_satisfies
— MethodInitialize values from the data (data frames)
LogicCircuits.is_atom
— Methodis_atom(α::Bdd)::Bool
Returns whether the given Bdd node is an atomic formula (i.e. a variable, ⊥, ⊤, or literal).
LogicCircuits.is_lit
— Methodis_lit(α::Bdd)::Bool
Returns whether the given Bdd node represents a literal.
LogicCircuits.is_term
— Methodis_term(α::Bdd)::Bool
Returns whether this Bdd node is terminal.
LogicCircuits.is_var
— Methodis_var(α::Bdd)::Bool
Returns whether the given Bdd node represents a variable.
LogicCircuits.is_⊤
— Methodis_⊤(α::Bdd)::Bool
Returns whether the given Bdd node represents a ⊤.
LogicCircuits.is_⊥
— Methodis_⊥(α::Bdd)::Bool
Returns whether the given Bdd node represents a ⊥.
LogicCircuits.iscanonical
— Methodiscanonical(circuit::LogicCircuit, k::Int; verbose = false)
Does the given circuit have canonical Or gates, as determined by a probabilistic equivalence check?
LogicCircuits.iscnf
— MethodIs the circuit a conjunction of disjunctive clauses?
LogicCircuits.isconstantgate
— MethodIs the node a constant gate?
LogicCircuits.isdecomposable
— Functionisdecomposable(root::LogicCircuit)::Bool
Is the circuit decomposable?
LogicCircuits.isdeterministic
— Functionisdeterministic(root::LogicCircuit)::Bool
Is the circuit determinstic? Note: this function is generally intractable for large circuits.
LogicCircuits.isdnf
— MethodIs the circuit a disjunction of conjunctive clauses?
LogicCircuits.isfalse
— MethodIs the circuit syntactically equal to false?
LogicCircuits.isflat
— MethodIs the circuit a flat DNF or CNF structure?
LogicCircuits.isinnergate
— MethodIs the node an inner gate?
LogicCircuits.isleafgate
— MethodIs the node a leaf gate?
LogicCircuits.isliteralgate
— MethodIs the node a literal gate?
LogicCircuits.ispositive
— MethodGet the sign of the literal leaf node
LogicCircuits.issatisfiable
— Methodissatisfiable(root::LogicCircuit)::Bool
Determine whether the logical circuit is satisfiable (has a satisfying assignment). Requires decomposability of the circuit.
LogicCircuits.issmooth
— Functionissmooth(root::LogicCircuit)::Bool
Is the circuit smooth?
LogicCircuits.isstruct_decomposable
— Methodisstruct_decomposable(root::LogicCircuit)::Bool
Is the circuit structured-decomposable?
LogicCircuits.istautology
— Methodistautology(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.istrue
— MethodIs the circuit syntactically equal to true?
LogicCircuits.is⋀gate
— MethodIs the node an And gate?
LogicCircuits.is⋁gate
— MethodIs the node an Or gate?
LogicCircuits.lit_val
— MethodReturns whether a variable x appears as a positive literal in α, given that α is a conjunction of literals.
LogicCircuits.lit_vec
— MethodAssumes ϕ is a full conjunction of literals. Returns ϕ as a zero-one vector and its scope.
LogicCircuits.literal
— MethodGet the logical literal in a given literal leaf node
LogicCircuits.literal_nodes
— MethodGet the list of literal nodes in a given circuit
LogicCircuits.literals
— MethodGet a sequence of positive and negative literals
LogicCircuits.load
— MethodLoads 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.load_bdd
— MethodLoads a BDD from a file. Use load
instead.
LogicCircuits.load_cnf
— MethodLoads a CNF as a BDD. Use load
instead.
LogicCircuits.load_dnf
— MethodLoads a CNF as a BDD. Use load
instead.
LogicCircuits.make_vars_contiguous
— MethodMake all variables in this circuit contiguously numbered. Return new circuit and the variable mapping.
LogicCircuits.map_parents
— MethodComputes a mapping of the parents of each node.
LogicCircuits.marginalize
— MethodMarginalize a variable through some binary operation.
LogicCircuits.max_variable
— FunctionGet the variable in the circuit with the largest index
LogicCircuits.mentions
— MethodReturns whether the formula (i.e. BDD) mentions a variable.
LogicCircuits.mgr
— MethodGet the manager of a Sdd
node, which is its SddMgr
vtree
LogicCircuits.model_count
— Functionmodel_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.model_var_prob
— MethodCompute the probability of each variable for a random satisfying assignment of the logical circuit
LogicCircuits.neg_literals
— MethodGet a sequence of negative literals
LogicCircuits.negate
— MethodNegate an SDD
LogicCircuits.normal_form
— MethodRuns 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.num_elements
— MethodNumber of elements (conjunctions) in layer or bit circuit
LogicCircuits.or
— Methodor(α::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.or_nodes
— MethodGet the list of or nodes in a given circuit
LogicCircuits.pos_literals
— MethodGet a sequence of positive literals
LogicCircuits.postorder
— MethodReturns a Vector{Bdd}
containing all nodes in α
in post-order.
LogicCircuits.prime
— MethodGet the prime, that is, the first conjunct
LogicCircuits.print_conjunction
— MethodPretty print a conjunction of literals BDD.
LogicCircuits.print_nf
— MethodPretty 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_equiv
— MethodCheck equivalence using probabilistic equivalence checking. Note that this implentation may not have any formal guarantees as such.
LogicCircuits.prob_equiv_signature
— Functionprob_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_mnist
— FunctionProcesses the mnist dataset using the MNIST object from MLDataSets package MLDS_MNIST
= the MNIST from MLDataSets labeled
= whether to return the lables
LogicCircuits.propagate_constants
— Methodpropagate_constants(root::LogicCircuit)
Remove all constant leafs from the circuit
LogicCircuits.random_split
— MethodRandomly picking egde and variable from candidates
LogicCircuits.reduce!
— MethodReduce a Bdd rooted at α inplace, removing duplicate nodes and redundant sub-trees. Returns canonical representation of α.
LogicCircuits.replace_node
— MethodReplace node old
with node new
in circuit root
LogicCircuits.respects_vtree
— MethodDoes 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.restrict
— MethodReturns a new reduced Bdd restricted to instantiation X.
LogicCircuits.restrict_step
— MethodReturns a new Bdd restricted to instantiation X.
LogicCircuits.restrict_step
— MethodReturns a new Bdd restricted to instantiation X.
LogicCircuits.sat_prob
— Functionsat_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.satisfies
— MethodEvaluate satisfaction of the circuit bottom-up for a given input
LogicCircuits.satisfies_all
— FunctionEvaluate the circuit bottom-up for a given input and return the value of all nodes
LogicCircuits.satisfies_flows
— FunctionCompute the value and flow of each node
LogicCircuits.satisfies_flows_down
— FunctionWhen values of nodes have already been computed, do a downward pass computing the flows at each node
LogicCircuits.satisfies_flows_down_layers
— MethodPass flows down the layers of a bit circuit on the GPU
LogicCircuits.satisfies_flows_down_layers
— MethodEvaluate the layers of a bit circuit on the CPU (SIMD & multi-threaded)
LogicCircuits.satisfies_flows_down_layers_cuda
— MethodCUDA kernel for passing flows down circuit
LogicCircuits.satisfies_layers
— MethodEvaluate the layers of a bit circuit on the GPU
LogicCircuits.satisfies_layers
— MethodEvaluate the layers of a bit circuit on the CPU (SIMD & multi-threaded)
LogicCircuits.satisfies_layers_cuda
— MethodCUDA kernel for circuit evaluation
LogicCircuits.save_bdd
— MethodSaves 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.save_bdd_
— MethodSave as BDD. Use the save_bdd
function instead.
LogicCircuits.save_cnf
— MethodSave as CNF. Use the save
function instead.
LogicCircuits.save_dnf
— MethodSave as DNF. Use the save
function instead.
LogicCircuits.scope
— MethodReturns all variables in this formula as a Vector{Int}.
LogicCircuits.scopeset
— MethodReturns all variables in this formula as a Set{Int}.
LogicCircuits.sdd_mgr_for
— MethodObtain an SDD manager that can support compiling the given circuit
LogicCircuits.sdd_num_nodes
— MethodCount the number of decision nodes in the SDD
LogicCircuits.sdd_num_nodes_leafs
— MethodCount the number of decision and leaf nodes in the SDD
LogicCircuits.sdd_size
— MethodCount the number of elements in the decision nodes of the SDD
LogicCircuits.shallowhash
— Functionshallowhash(α::Bdd, h::UInt = UInt64(0))
Returns a shallow hash for the given node (not BDD as a whole).
LogicCircuits.shannon!
— MethodPerforms Shannon's Decomposition on the Bdd α, given a set of variables to isolate. Any decomposition that results in a ⊥ is discarded.
LogicCircuits.shannon
— MethodPerforms Shannon's Decomposition on the Bdd α, given a variable to isolate.
LogicCircuits.shannon
— MethodPerforms Shannon's Decomposition on the Bdd α, given a set of variables to isolate.
LogicCircuits.sibling
— MethodGet the other child of a parent element
LogicCircuits.smooth
— Methodsmooth(root::LogicCircuit)
Create an equivalent smooth circuit from the given circuit.
LogicCircuits.smooth
— MethodSmooth an sdd to a StructLogicCircuit
LogicCircuits.smooth
— Methodsmooth(root::StructLogicCircuit)::StructLogicCircuit
Create an equivalent smooth circuit from the given circuit.
LogicCircuits.smooth_node
— Methodsmooth_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_node
— Methodsmooth_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_candidates
— Methodsplit_candidates(circuit::LogicCircuit)::Tuple{Vector{Tuple{LogicCircuit, LogicCircuit}}, Dict{LogicCircuit, BitSet}}
Return the edges and variables which can be splited on
LogicCircuits.split_step
— MethodSplit step
LogicCircuits.standardize_circuit
— MethodStandardize the circuit:
- Children of or nodes are and nodes.
- Children of and nodes are or nodes.
- Each and node has exactly two children.
Note: for circuits with parameters this function will not keep the parameters equavalent.
LogicCircuits.struct_learn
— MethodStructure learning manager
LogicCircuits.sub
— MethodGet the sub, that is, the second and last conjunct
LogicCircuits.terminal
— MethodReturns a new terminal node of given boolean value.
LogicCircuits.to_int
— MethodReturns 0 if x is not a literal; else returns an integer representation of x.
LogicCircuits.to_lit
— MethodReturns α as an integer literal. Assumes α is a leaf node.
LogicCircuits.tree_formula_string
— MethodGet the formula of a given circuit as a string, expanding the formula into a tree
LogicCircuits.twenty_datasets
— Methodtrain, 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.unique⋁
— MethodConstruct a unique decision gate for the given vtree
LogicCircuits.valuations
— MethodCompute all possible valuations of scope V.
LogicCircuits.variable
— FunctionGet the variable in a vtree leaf
LogicCircuits.variable
— MethodGet the logical variable in a given literal leaf node
LogicCircuits.varsubset
— MethodAre the variables in n
contained in the variables in m
?
LogicCircuits.varsubset_left
— MethodAre the variables in n
contained in the left branch of m
?
LogicCircuits.varsubset_right
— MethodAre the variables in n
contained in the right branch of m
?
LogicCircuits.vtree
— MethodGet the vtree corresponding to the argument
LogicCircuits.vtree_safe
— MethodGet the vtree corresponding to the argument, or nothing if the node has no vtree
LogicCircuits.zoo_cnf
— Methodzoo_cnf(name)
Loads CNF file with given name from model zoo. See https://github.com/UCLA-StarAI/Circuit-Model-Zoo.
LogicCircuits.zoo_dnf
— Methodzoo_dnf(name)
Loads DNF file with given name from model zoo. See https://github.com/UCLA-StarAI/Circuit-Model-Zoo.
LogicCircuits.zoo_jlc
— Methodzoo_jlc(name)
Loads JLC file with given name from model zoo. See https://github.com/UCLA-StarAI/Circuit-Model-Zoo.
LogicCircuits.zoo_nnf
— Methodzoo_nnf(name)
Loads NNF file with given name from model zoo. See https://github.com/UCLA-StarAI/Circuit-Model-Zoo.
LogicCircuits.zoo_sdd
— Methodzoo_sdd(name)
Loads SDD file with given name from model zoo. See https://github.com/UCLA-StarAI/Circuit-Model-Zoo.
LogicCircuits.zoo_vtree
— Methodzoo_vtree(name)
Loads Vtree file with given name from model zoo. See https://github.com/UCLA-StarAI/Circuit-Model-Zoo.
LogicCircuits.⋀_nodes
— MethodGet the list of conjunction nodes in a given circuit
LogicCircuits.⋁_nodes
— MethodGet the list of disjunction nodes in a given circuit
TikzGraphs.plot
— MethodTikzGraphs.plot(lc::LogicCircuit; simplify=false)
Plots a LogicCircuit using TikzGraphs. Needt o have LaTeX installed.
TikzGraphs.plot
— MethodTikzGraphs.plot(vtree::Vtree)
Plots a vtree using TikzGraphs. Need to have LaTeX installed.