23#ifndef GENERIC_CIRCUIT_H
24#define GENERIC_CIRCUIT_H
30#include <boost/archive/binary_oarchive.hpp>
31#include <boost/serialization/unordered_map.hpp>
32#include <boost/serialization/map.hpp>
33#include <boost/serialization/set.hpp>
34#include <boost/serialization/vector.hpp>
63 std::vector<std::vector<std::vector<gate_t> > >
b;
64 std::vector<std::vector<std::pair<std::size_t, std::vector<gate_t> > > >
in;
65 std::vector<std::vector<std::pair<std::size_t, std::vector<gate_t> > > >
out;
71std::map<gate_t, std::pair<unsigned,unsigned> >
infos;
72std::map<gate_t, std::string>
extra;
88mutable std::vector<std::pair<gate_t, std::shared_ptr<void> > >
solved_systems;
97 return "<GenericCircuit>";
108 infos[g]=std::make_pair(info1, info2);
118 auto it =
infos.find(g);
120 return std::make_pair(-1, -1);
141 auto it =
extra.find(g);
178 std::vector<std::string> r;
193 prob[
static_cast<std::underlying_type<gate_t>::type
>(g)]=p;
202 return prob[
static_cast<std::underlying_type<gate_t>::type
>(g)];
236 }
else if (p == 1.0) {
275 w.reserve(ks.size());
276 for (
gate_t k : ks) w.push_back(k);
574 std::string u =
"dec-in-" + std::to_string(
static_cast<size_t>(
id));
594 unsigned value_index) {
600 std::string u =
"dec-mul-" + std::to_string(
static_cast<size_t>(
id));
618 std::vector<gate_t> wires_) {
621 setInfos(
id,
static_cast<int>(op), 0);
623 std::string u =
"dec-arith-" + std::to_string(
static_cast<size_t>(
id));
643 std::string u =
"dec-gate-" + std::to_string(
static_cast<size_t>(
id));
665 std::string u =
"dec-value-" + std::to_string(
static_cast<size_t>(
id));
687 std::vector<gate_t> w;
689 w.push_back(p_token);
690 w.push_back(x_token);
691 w.push_back(y_token);
708 unsigned value_index,
709 const std::string &value_text) {
752 if (w.size() < 2)
return false;
754 for (std::size_t i = 1; i < w.size(); ++i) {
765template<
class Archive>
766void serialize (Archive & ar,
const unsigned int version)
809template<
typename S, std::enable_if_t<std::is_base_of_v<semiring::Semiring<
typename S::value_type>, S>,
int> = 0>
810const typename S::value_type &
evaluate(
gate_t g, std::unordered_map<gate_t, typename S::value_type> &provenance_mapping, S
semiring)
const;
853template<
typename S, std::enable_if_t<std::is_base_of_v<semiring::Semiring<
typename S::value_type>, S>,
int> = 0>
854std::vector<typename S::value_type>
solveFixSystem(
gate_t sys, std::unordered_map<gate_t, typename S::value_type> &provenance_mapping, S
semiring)
const;
gate_t
Strongly-typed gate identifier.
Out-of-line template method implementations for Circuit<gateType>.
Abstract semiring interface for provenance evaluation.
std::vector< unsigned char > name_kind
std::vector< gate_t > & getWires(gate_t g)
gate_type getGateType(gate_t g) const
std::unordered_map< gate_uuid, gate_t, gate_uuid_hash > uuid2id
std::unordered_map< gate_t, std::string > id2name
void setGateType(gate_t g, gate_type t)
std::vector< gate_type > gates
std::vector< gate_uuid > id2uuid
uuid getUUID(gate_t g) const
std::vector< std::vector< gate_t > > wires
void bindName(gate_t g, const gate_uuid &u)
std::vector< gate_t >::size_type getNbGates() const
std::unordered_map< std::string, gate_t > name2id
void resolveToPlus(gate_t g, std::vector< gate_t > w)
Rewrite an arbitrary gate as a gate_plus over w.
std::vector< typename S::value_type > solveFixSystem(gate_t sys, std::unordered_map< gate_t, typename S::value_type > &provenance_mapping, S semiring) const
Least solution of the equation system of a gate_fixsystem.
void resolveToCategoricalMixture(gate_t g, std::vector< gate_t > wires_)
Rewrite g in place as a categorical-form gate_mixture over wires ([key, mul_1, ......
void resolveGateToZero(gate_t g)
Replace an arbitrary gate (typically gate_times) by gate_zero.
void setWires(gate_t g, std::vector< gate_t > w)
Replace the wires of g with w.
std::map< gate_t, std::pair< unsigned, unsigned > > infos
Per-gate (info1, info2) annotations.
std::vector< std::pair< gate_t, std::shared_ptr< void > > > solved_systems
Equation systems solved by evaluate, with their solutions.
void markAbsorptiveAssumed(gate_t g)
Mark gate g as absorptive-assumed (in-memory side band).
void resolveCmpToPlusOfKGates(gate_t g, const std::vector< gate_t > &ks)
Replace a gate_cmp by a gate_plus over the given per-row K-gates (the OR of the agg's row-presence in...
void resolveGateToOne(gate_t g)
Rewrite a gate as gate_one, the event that holds in every world.
const S::value_type & evaluate(gate_t g, std::unordered_map< gate_t, typename S::value_type > &provenance_mapping, S semiring) const
Evaluate the sub-circuit rooted at gate g over semiring semiring.
gate_t addAnonymousMulinputGateWithValue(gate_t key, double p, unsigned value_index, const std::string &value_text)
Allocate a fresh gate_mulinput labelled with a numeric outcome value carried in extra.
void resolveToRv(gate_t g, const std::string &s)
Rewrite an arbitrary gate as a gate_rv carrying the distribution-spec extra s.
bool foldSemiringIdentities()
Drop semiring identity wires and collapse single-wire gate_times / gate_plus to their lone non-identi...
void resolveToCase(gate_t g, std::vector< gate_t > w)
Rewrite a gate as the gate_case over w (guards and values, then the default).
void foldAbsorptiveIdentities()
Absorptive-rules-only variant of foldBooleanIdentities(): the joint fixpoint of the absorptive fold r...
void resolveToMixture(gate_t g, gate_t p_token, gate_t x_token, gate_t y_token)
Rewrite g in place as a gate_mixture over the wires [p_token, x_token, y_token].
std::map< gate_t, std::string > extra
Per-gate string extras.
gate_t addGate() override
Allocate a new gate with a default-initialised type.
std::set< gate_t > inputs
Set of input (leaf) gate IDs.
gate_t addAnonymousArithGate(provsql_arith_op op, std::vector< gate_t > wires_)
Allocate a fresh gate_arith gate with operator tag op and the given wires.
gate_t addAnonymousValueGate(const std::string &text)
Allocate a fresh gate_value gate carrying the textual scalar text.
void serialize(Archive &ar, const unsigned int version)
Boost serialisation support.
friend class dDNNFTreeDecompositionBuilder
std::set< gate_t > absorptive_assumed_gates
Side-band absorptive-assumption marker set by the absorptive fold rules (plus-idempotence,...
std::vector< std::string > getMappableUUIDs() const
The UUIDs a provenance mapping can label: those of the input gates, and of the mulinput gates,...
bool isCategoricalMixture(gate_t g) const
Test whether g is a categorical-form gate_mixture (the explicit provsql.categorical output).
std::vector< double > prob
Per-gate probability values.
FixSystemLinear linearizeFixSystem(gate_t sys) const
The equations of the gate_fixsystem sys, as linear forms over the gates that do not depend on its unk...
void setInfos(gate_t g, unsigned info1, unsigned info2)
Set the integer annotation pair for gate g.
std::string getExtra(gate_t g) const
Return the string extra for gate g.
gate_t setGate(gate_type type) override
Allocate a new gate with type type and no UUID.
void markBooleanAssumed(gate_t g)
Mark gate g as Boolean-assumed (in-memory side band).
std::set< gate_t > boolean_assumed_gates
Side-band Boolean-assumption marker set by the Boolean-only fold rules ; an evaluator visiting a gate...
gate_t addAnonymousGate(gate_type type, std::vector< gate_t > wires_)
Allocate a fresh gate of type type over wires_.
double getProb(gate_t g) const
Return the probability for gate g.
bool isAbsorptiveAssumed(gate_t g) const
Report whether g carries the absorptive-assumption flag.
void resolveCmpToBernoulli(gate_t g, double p)
Replace a gate_cmp by a constant Boolean leaf (gate_one for p == 1, gate_zero for p == 0) or by a Ber...
void redirectGates(std::unordered_map< gate_t, gate_t > subst)
Make every reference to a gate of subst point to its target instead.
gate_t addAnonymousInputGate(double p)
Allocate a fresh gate_input gate carrying probability p, with a unique synthetic UUID so subsequent B...
friend class boost::serialization::access
const std::set< gate_t > & getInputs() const
Return the set of input (leaf) gates.
bool isBooleanAssumed(gate_t g) const
Report whether g carries the Boolean-assumption flag.
std::pair< unsigned, unsigned > getInfos(gate_t g) const
Return the integer annotation pair for gate g.
void liftConditionedToTarget(gate_t g, gate_t target)
Replace a gate_conditioned g by a transparent passthrough to its target child (a single-child gate_ar...
void setExtra(gate_t g, const std::string &ex)
Attach a string extra to gate g.
virtual std::string toString(gate_t g) const override
Return a placeholder debug string (not intended for display).
gate_t addAnonymousMulinputGate(gate_t key, double p, unsigned value_index)
Allocate a fresh gate_mulinput gate with key key, probability p, and value index value_index.
bool applyFoldRuleSweep(bool boolean_level)
One pass of the fold rules over every gate_plus / gate_times.
void resolveToValue(gate_t g, const std::string &s)
Rewrite an arbitrary gate as a gate_value carrying the textual extra s.
void setGate(gate_t g, gate_type type)
Set the type of the existing gate g, as setGate does for a UUID, without looking the UUID up.
void foldBooleanIdentities()
Apply the Boolean-only AND the absorptive simplification rules to gate_plus and gate_times,...
void setProb(gate_t g, double p)
Set the probability for gate g.
Core types, constants, and utilities shared across ProvSQL.
provsql_arith_op
Arithmetic operator tags used by gate_arith.
@ PROVSQL_ARITH_PLUS
n-ary, sum of children
@ gate_rv
Continuous random-variable leaf (extra encodes distribution).
@ gate_case
N-ary guarded selection over scalar (RV) children: wires are [guard_1, value_1, .....
@ gate_mixture
Probabilistic mixture: three wires [p_token (gate_input Bernoulli), x_token, y_token]; samples x when...
@ gate_arith
n-ary arithmetic gate over scalar-valued children (info1 holds operator tag)
In-memory provenance circuit with semiring-generic evaluation.
std::vector< std::vector< std::vector< gate_t > > > b
Constant part of each equation.
std::size_t n
Number of unknowns.
std::vector< std::vector< std::pair< std::size_t, std::vector< gate_t > > > > in
Terms of each equation.
std::vector< std::vector< std::pair< std::size_t, std::vector< gate_t > > > > out
Terms, by unknown read.