44#include <boost/archive/text_oarchive.hpp>
45#include <boost/archive/text_iarchive.hpp>
61static constexpr std::size_t max_rendering_size = std::size_t(1) << 30;
66 "the Boolean expression is too large to print (over 1 GB): a sub-circuit "
67 "shared by several gates is written out at each of them";
77enum levels {ERROR, NOTICE};
78#define elog(level, ...) {fprintf(stderr, __VA_ARGS__); if(level==ERROR) exit(EXIT_FAILURE);}
79#define CHECK_FOR_INTERRUPTS() ((void)0)
82#define check_stack_depth() ((void)0)
86#include "utils/elog.h"
115double parse_wmc_value(
const std::string &line,
const char *tool) {
116 std::vector<std::string> tokens;
117 std::stringstream ss(line);
119 while(ss >> tok) tokens.push_back(tok);
121 for(
auto it = tokens.rbegin(); it != tokens.rend(); ++it) {
122 const std::string &t = *it;
124 auto slash = t.find(
'/');
125 if(slash != std::string::npos) {
126 size_t pn = 0, pd = 0;
127 double num = std::stod(t.substr(0, slash), &pn);
128 double den = std::stod(t.substr(slash + 1), &pd);
129 if(pn != slash || pd != t.size() - slash - 1)
continue;
130 return (den == 0.0) ? 0.0 : num / den;
133 double v = std::stod(t, &p);
134 if(p == t.size())
return v;
135 }
catch(
const std::exception &) {
139 throw CircuitException(std::string(tool) +
": could not parse '" + line +
"'");
201 const std::unordered_map<gate_t, std::string> &labels)
const
209 const std::unordered_map<gate_t, std::string> *labels)
const
225 auto it = labels->find(g);
226 if(it != labels->end())
232 auto it = labels->find(g);
233 if(it != labels->end())
235 "}[" + std::to_string(
getProb(g)) +
"]";
265 else if(!result.empty())
269 if(result.size() > max_rendering_size)
287 return "("+result+
")";
292 std::stringstream ss;
294 std::unordered_set<gate_t> processed;
295 std::stack<gate_t> to_process;
296 to_process.push(root);
298 while(!to_process.empty()) {
299 auto g=to_process.top();
302 if(processed.find(g)!=processed.end())
339 if(processed.find(s)==processed.end())
354 std::vector<signed char> memo(
gates.size(), -1);
359 std::vector<signed char> &memo)
const
362 auto &m = memo[
static_cast<std::size_t
>(g)];
368 bool disjunction=
false;
373 value = sampled.find(g)!=sampled.end();
378 throw CircuitException(
"Monte-Carlo sampling not implemented on multivalued inputs");
381 memo[
static_cast<std::size_t
>(g)] = value;
395 value = !disjunction;
397 if(
evaluate(s, sampled, memo) == disjunction) {
401 memo[
static_cast<std::size_t
>(g)] = value;
415 std::random_device rd;
416 rng.seed((
static_cast<uint64_t
>(rd()) << 32) | rd());
418 std::uniform_real_distribution<double> uniform01(0.0, 1.0);
422 for(
unsigned i=0; i<samples; ++i) {
423 std::unordered_set<gate_t> sampled;
425 if(uniform01(rng) <
getProb(in)) {
434 throw CircuitException(
"Interrupted after "+std::to_string(i+1)+
" samples");
437 return success*1./samples;
442 std::vector<gate_t> &clauses,
443 std::vector<std::set<gate_t> > &supports)
const
451 std::vector<gate_t> clause_roots;
454 clause_roots.push_back(c);
456 clause_roots.push_back(g);
459 for(
auto root: clause_roots) {
464 std::set<gate_t> support;
465 std::unordered_set<gate_t> seen;
466 std::stack<gate_t> st;
471 if(!seen.insert(cur).second)
485 clauses.push_back(root);
486 supports.push_back(std::move(support));
495 std::vector<gate_t> clause_roots;
498 clause_roots.push_back(c);
500 clause_roots.push_back(g);
501 num_clauses = clause_roots.size();
506 std::unordered_set<gate_t> seen;
507 std::stack<gate_t> st;
508 for(
auto r: clause_roots)
513 if(!seen.insert(cur).second)
538struct KarpLubyState {
539 std::vector<double> p;
540 std::vector<double> cumulative;
542 std::vector<gate_t> relevant;
545KarpLubyState karpLubyState(
547 const std::vector<std::set<gate_t> > &supports)
550 const size_t m = supports.size();
552 st.cumulative.resize(m);
553 std::set<gate_t> rel;
554 for(
size_t i=0; i<m; ++i) {
556 for(
gate_t leaf: supports[i]) {
562 st.cumulative[i] = st.S;
564 st.relevant.assign(rel.begin(), rel.end());
570std::mt19937_64 karpLubySeededRNG()
576 std::random_device rd;
577 rng.seed((
static_cast<uint64_t
>(rd()) << 32) | rd());
583size_t karpLubyDrawClause(
const KarpLubyState &st,
584 std::mt19937_64 &rng,
585 std::uniform_real_distribution<double> &u01)
587 double u = u01(rng) * st.S;
588 size_t i =
static_cast<size_t>(
589 std::upper_bound(st.cumulative.begin(), st.cumulative.end(), u)
590 - st.cumulative.begin());
591 if(i >= st.cumulative.size())
592 i = st.cumulative.size() - 1;
606 const std::vector<std::set<gate_t> > &supports,
607 const KarpLubyState &st,
size_t i,
608 std::mt19937_64 &rng,
609 std::uniform_real_distribution<double> &u01,
610 std::unordered_set<gate_t> &trueLeaves)
613 for(
gate_t leaf: st.relevant) {
614 if(supports[i].count(leaf) || u01(rng) < c.
getProb(leaf))
615 trueLeaves.insert(leaf);
617 const size_t m = supports.size();
618 for(
size_t j=0; j<m; ++j) {
620 for(
gate_t leaf: supports[j]) {
621 if(trueLeaves.find(leaf)==trueLeaves.end()) { sat =
false;
break; }
632 const std::vector<gate_t> &clauses,
633 const std::vector<std::set<gate_t> > &supports,
634 unsigned long samples)
const
636 const size_t m = clauses.size();
637 if(m==0 || samples==0)
640 KarpLubyState st = karpLubyState(*
this, supports);
644 std::mt19937_64 rng = karpLubySeededRNG();
645 std::uniform_real_distribution<double> u01(0.0, 1.0);
646 std::unordered_set<gate_t> trueLeaves;
653 unsigned long accepts = 0;
654 for(
unsigned long s=0; s<samples; ++s) {
655 size_t i = karpLubyDrawClause(st, rng, u01);
656 if(karpLubyCovers(*
this, supports, st, i, rng, u01, trueLeaves))
659 throw CircuitException(
"Interrupted after "+std::to_string(s+1)+
" samples");
661 return st.S * accepts /
static_cast<double>(samples);
671 std::vector<unsigned long> n(m, 1);
672 const unsigned long rest = samples - m;
673 std::vector<double> frac(m);
674 unsigned long base_sum = 0;
675 for(
size_t i=0; i<m; ++i) {
676 double want =
static_cast<double>(rest) * st.p[i] / st.S;
677 unsigned long fl =
static_cast<unsigned long>(want);
680 frac[i] = want -
static_cast<double>(fl);
682 unsigned long leftover = rest - base_sum;
684 std::vector<size_t> idx(m);
685 for(
size_t i=0; i<m; ++i) idx[i] = i;
686 std::partial_sort(idx.begin(), idx.begin()+leftover, idx.end(),
687 [&](
size_t a,
size_t b){ return frac[a] > frac[b]; });
688 for(
unsigned long k=0; k<leftover; ++k)
693 for(
size_t i=0; i<m; ++i) {
694 unsigned long accepts = 0;
695 for(
unsigned long k=0; k<n[i]; ++k) {
696 if(karpLubyCovers(*
this, supports, st, i, rng, u01, trueLeaves))
702 est += st.p[i] *
static_cast<double>(accepts) /
static_cast<double>(n[i]);
708 const std::vector<gate_t> &clauses,
709 const std::vector<std::set<gate_t> > &supports,
710 double eps,
double delta,
711 unsigned long max_samples,
712 unsigned long &samples_used,
713 bool &reached_target)
const
716 reached_target =
false;
717 const size_t m = clauses.size();
718 if(m==0 || max_samples==0)
721 KarpLubyState st = karpLubyState(*
this, supports);
731 const double e = exp(1.0);
732 const double Y = 4.0 * (e - 2.0) * log(2.0/delta) / (eps*eps);
733 const double Y1 = 1.0 + (1.0 + eps) * Y;
735 std::mt19937_64 rng = karpLubySeededRNG();
736 std::uniform_real_distribution<double> u01(0.0, 1.0);
737 std::unordered_set<gate_t> trueLeaves;
739 unsigned long accepts = 0;
740 for(
unsigned long s=0; s<max_samples; ++s) {
741 size_t i = karpLubyDrawClause(st, rng, u01);
742 if(karpLubyCovers(*
this, supports, st, i, rng, u01, trueLeaves)) {
744 if(
static_cast<double>(accepts) >= Y1) {
745 samples_used = s + 1;
746 reached_target =
true;
747 return st.S * Y1 /
static_cast<double>(samples_used);
751 throw CircuitException(
"Interrupted after "+std::to_string(s+1)+
" samples");
757 samples_used = max_samples;
758 return st.S *
static_cast<double>(accepts) /
static_cast<double>(max_samples);
765 const std::vector<gate_t> &clauses,
766 const std::vector<std::set<gate_t> > &supports)
const
768 const size_t m = clauses.size();
773 "sieve: too many clauses (" + std::to_string(m) +
" > "
775 +
"); inclusion-exclusion is 2^m -- use another method");
779 std::unordered_set<gate_t> u;
780 for(
unsigned long long s = 1; s < (1ULL << m); ++s) {
783 for(
size_t i = 0; i < m; ++i)
784 if(s & (1ULL << i)) {
786 for(
gate_t leaf : supports[i])
792 if(bits & 1) total += p;
else total -= p;
801 const std::vector<std::set<gate_t> > &clauses,
802 double &lower,
double &upper)
const
804 const size_t m = clauses.size();
812 std::vector<double> clause_prob(m);
813 for(
size_t i = 0; i < m; ++i) {
815 for(
gate_t leaf : clauses[i])
822 std::vector<size_t> order(m);
823 for(
size_t i = 0; i < m; ++i)
825 std::sort(order.begin(), order.end(),
826 [&](
size_t a,
size_t b) {
827 return clause_prob[a] > clause_prob[b];
834 std::vector<std::set<gate_t> > bucket_support;
835 std::vector<double> bucket_prob;
836 for(
size_t idx : order) {
837 const std::set<gate_t> &sup = clauses[idx];
838 size_t target = bucket_support.size();
839 for(
size_t b = 0; b < bucket_support.size(); ++b) {
840 bool disjoint =
true;
842 if(bucket_support[b].count(leaf)) {
851 if(target == bucket_support.size()) {
852 bucket_support.emplace_back();
853 bucket_prob.push_back(0.);
855 bucket_prob[target] =
856 1. - (1. - bucket_prob[target]) * (1. - clause_prob[idx]);
857 bucket_support[target].insert(sup.begin(), sup.end());
865 double L = 0., U = 0.;
866 for(
double bp : bucket_prob) {
872 upper = (U > 1.) ? 1. : U;
884 std::set<gate_t> rinputs;
886 std::unordered_set<gate_t> seen;
887 std::stack<gate_t> stk;
889 while(!stk.empty()) {
890 gate_t u = stk.top(); stk.pop();
891 if(!seen.insert(u).second)
continue;
897 if(rinputs.size()>=8*
sizeof(
unsigned long long))
900 unsigned long long nb=(1ULL<<rinputs.size());
903 for(
unsigned long long i=0; i < nb; ++i) {
904 std::unordered_set<gate_t> s;
908 for(
gate_t in : rinputs) {
909 if(i & (1ULL << j)) {
929 std::vector<std::vector<int> > clauses;
936 int id{
static_cast<int>(i)+1};
937 std::vector<int> c = {
id};
939 clauses.push_back({-id,
static_cast<int>(s)+1});
940 c.push_back(-
static_cast<int>(s)-1);
942 clauses.push_back(c);
948 int id{
static_cast<int>(i)+1};
949 std::vector<int> c = {-
id};
951 clauses.push_back({id, -
static_cast<int>(s)-1});
952 c.push_back(
static_cast<int>(s)+1);
954 clauses.push_back(c);
960 int id=
static_cast<int>(i)+1;
962 clauses.push_back({-id,-
static_cast<int>(s)-1});
963 clauses.push_back({id,
static_cast<int>(s)+1});
968 throw CircuitException(
"Multivalued inputs should have been removed by then.");
975 clauses.push_back({(int)g+1});
977 std::ostringstream oss;
984 oss <<
"c input " << m.variable <<
" "
985 << (m.uuid.empty() ?
"?" : m.uuid) <<
" "
986 << m.probability <<
"\n";
989 oss <<
"p cnf " <<
gates.size() <<
" " << clauses.size() <<
"\n";
990 for(
unsigned i=0; i<clauses.size(); ++i) {
991 for(
int x : clauses[i]) {
998 oss <<
"w " << (
static_cast<std::underlying_type<gate_t>::type
>(in)+1) <<
" " <<
getProb(in) <<
"\n";
999 oss <<
"w -" << (
static_cast<std::underlying_type<gate_t>::type
>(in)+1) <<
" " << (1. -
getProb(in)) <<
"\n";
1005std::vector<BooleanCircuit::CNFInputMapping>
1007 std::vector<CNFInputMapping> mapping;
1011 auto id =
static_cast<std::underlying_type<gate_t>::type
>(in);
1012 mapping.push_back({
static_cast<int>(id) + 1,
getUUID(in),
getProb(in)});
1019 auto idOf = [](
gate_t x) {
1020 return static_cast<std::underlying_type<gate_t>::type
>(x);
1023 std::set<gate_t> seenInputs;
1024 std::set<gate_t> internalGates;
1027 std::function<std::string(
gate_t)> lit = [&](
gate_t w) -> std::string {
1030 return "in" + std::to_string(idOf(w));
1033 return "g" + std::to_string(idOf(w));
1035 std::string inner = lit(*
getWires(w).begin());
1036 return inner[0]==
'-' ? inner.substr(1) :
"-"+inner;
1049 if(seenInputs.insert(w).second)
1050 inputOrder.push_back(w);
1057 if(internalGates.insert(w).second)
1067 std::ostringstream oss;
1068 oss <<
"c BC-S1.2\n";
1070 for(
gate_t in : inputOrder)
1071 oss <<
"I in" << idOf(in) <<
"\n";
1072 for(
gate_t w : internalGates) {
1076 oss <<
"G g" << idOf(w) <<
" := ";
1083 oss <<
" " << lit(c);
1086 oss <<
"T " << lit(g) <<
"\n";
1110 std::ifstream ifs(outfilename.c_str());
1118 bool found_data =
false;
1119 while (std::getline(ifs, line)) {
1120 if (line.rfind(
"0:", 0) == 0) { found_data =
true;
break; }
1128 std::vector<gate_t> id_to_gate;
1131 if (line.empty())
continue;
1132 auto colon_pos = line.find(
':');
1133 if (colon_pos == std::string::npos)
continue;
1137 int panini_id = std::stoi(line.substr(0, colon_pos));
1138 if (
static_cast<size_t>(panini_id) != id_to_gate.size())
1140 "Panini output: out-of-order node id "
1141 + std::to_string(panini_id));
1143 std::stringstream ss(line.substr(colon_pos + 1));
1151 }
else if (first ==
"T") {
1154 }
else if (first ==
"C" || first ==
"D") {
1164 while (ss >> child) {
1165 if (child == 0)
break;
1166 if (child < 0 ||
static_cast<size_t>(child) >= id_to_gate.size())
1168 "Panini output: forward / invalid child reference "
1169 + std::to_string(child));
1170 dnnf.
addWire(this_gate, id_to_gate[child]);
1172 }
else if (first ==
"K") {
1174 "Panini output: unexpected K (kernelize) node; ProvSQL "
1175 "does not support Panini target languages that emit K "
1176 "nodes (R2-D2, CCDD).");
1182 int var = std::stoi(first);
1183 int f_child, t_child;
1184 if (!(ss >> f_child >> t_child))
1186 "Panini output: malformed decision line at id "
1187 + std::to_string(panini_id));
1188 if (t_child < 0 || f_child < 0
1189 ||
static_cast<size_t>(t_child) >= id_to_gate.size()
1190 ||
static_cast<size_t>(f_child) >= id_to_gate.size())
1192 "Panini output: forward / invalid decision child at id "
1193 + std::to_string(panini_id));
1194 gate_t t_gate = id_to_gate[t_child];
1195 gate_t f_gate = id_to_gate[f_child];
1210 size_t var_idx =
static_cast<size_t>(var) - 1;
1216 dnnf.
addWire(neg_lit, pos_lit);
1224 dnnf.
addWire(this_gate, and_t);
1225 dnnf.
addWire(this_gate, and_f);
1228 dnnf.
addWire(this_gate, t_gate);
1229 dnnf.
addWire(this_gate, f_gate);
1232 id_to_gate.push_back(this_gate);
1233 }
while (std::getline(ifs, line));
1237 if (id_to_gate.empty())
1241 dnnf.
setRoot(id_to_gate.back());
1256 const std::string &preferred =
"") {
1257 if(!preferred.empty()) {
1280 std::string chosen =
selectTool(
"compile", fb);
1281 return chosen.empty() ? std::string(fb) : chosen;
1288 if(compiler.empty()) {
1290 if(compiler.empty())
1292 "no knowledge compiler is available; install one (d4, d4v2, "
1293 "c2d, minic2d, dsharp) or add its directory to "
1294 "provsql.tool_search_path");
1309 "Compiler '"+compiler+
"' is disabled in the tool registry");
1312 "Compiler '"+compiler+
"' uses output parser '"+rec->
parser
1313 +
"', which compilation() does not implement");
1318 std::string *resolved)
const {
1321 const std::string compiler_binary = rec->
binary;
1323 *resolved = compiler;
1330 if(rec->
kind ==
"kcmcp") {
1331 std::vector<gate_t> inputOrder;
1332 std::string content;
1333 uint8_t input_format = 0;
1336 content =
BCS12(g, inputOrder);
1348 std::string endpoint = rec->
endpoint;
1349 if(endpoint ==
"managed")
1351 if(endpoint.empty())
1353 "KCMCP tool '"+compiler+
"' has no endpoint (managed server not "
1354 "running, or provsql.kcmcp_server unset)");
1357 std::istringstream iss(nnf);
1361 }
catch(
const std::exception &e) {
1363 +
"' failed: "+e.what());
1373 bool circuit_input = rec->
acceptsInput(
"circuit-bcs12")
1377 compiler_binary +
" not found on PATH; install it or add its "
1378 "directory to provsql.tool_search_path");
1381 std::string filename = tmp.
file(
"input");
1382 std::string outfilename = tmp.
file(
"input.nnf");
1385 std::vector<gate_t> inputOrder;
1386 std::string content;
1389 content =
BCS12(g, inputOrder);
1392 circuit_input =
false;
1399 std::ofstream ofs(filename);
1413 std::string cmdline;
1416 compiler_binary, filename, outfilename);
1418 cmdline = rec->
buildCommand(filename, outfilename, compiler_binary);
1430 CHECK_FOR_INTERRUPTS();
1437 if(rec->
parser ==
"panini-dd")
1440 std::ifstream ifs(outfilename.c_str());
1455 const std::vector<gate_t> &inputOrder)
const {
1456 const bool circuit_input = !inputOrder.empty();
1469 if(line.rfind(
"nnf", 0) != 0) {
1478 unsigned nb_nodes, nb_edges, nb_variables;
1480 std::stringstream ss(line);
1481 ss >> nnf >> nb_nodes >> nb_edges >> nb_variables;
1483 if(nb_variables!=
gates.size())
1484 throw CircuitException(
"Unreadable d-DNNF (wrong number of variables: " + std::to_string(nb_variables) +
" vs " + std::to_string(
gates.size()) +
")");
1496 size_t k = inputOrder.size();
1497 auto resolveVar = [&](
int v) -> std::pair<bool, gate_t> {
1498 unsigned idx =
static_cast<unsigned>(abs(v));
1500 if(idx>=1 && idx<=k)
1501 return {
true, inputOrder[idx-1]};
1502 return {
false,
gate_t{}};
1505 return {
true,
static_cast<gate_t>(idx-1)};
1506 return {
false,
gate_t{}};
1511 std::stringstream ss(line);
1519 auto id=dnnf.
getGate(std::to_string(i));
1523 auto id2=dnnf.
getGate(std::to_string(g));
1529 auto id=dnnf.
getGate(std::to_string(i));
1533 auto id2=dnnf.
getGate(std::to_string(g));
1540 auto [is_in, in_gate] = resolveVar(leaf);
1542 auto pid =
static_cast<std::underlying_type<gate_t>::type
>(in_gate);
1546 dnnf.
addWire(not_gate, leaf_gate);
1547 dnnf.
addWire(and_gate, not_gate);
1549 dnnf.
addWire(and_gate, leaf_gate);
1554 }
else if(c==
"f" || c==
"o") {
1560 }
else if(c==
"t" || c==
"a") {
1570 auto id2=dnnf.
getGate(std::to_string(var));
1572 std::vector<int> decisions;
1574 while(ss >> decision) {
1581 if(resolveVar(decision).first)
1582 decisions.push_back(decision);
1585 if(decisions.empty()) {
1591 for(
auto leaf : decisions) {
1592 auto in_gate = resolveVar(leaf).second;
1593 auto pid =
static_cast<std::underlying_type<gate_t>::type
>(in_gate);
1597 dnnf.
addWire(not_gate, leaf_gate);
1598 dnnf.
addWire(and_gate, not_gate);
1600 dnnf.
addWire(and_gate, leaf_gate);
1605 throw CircuitException(std::string(
"Unreadable d-DNNF (unknown node type: ")+c+
")");
1608 }
while(getline(in, line));
1635 const std::string &opt)
const {
1638 std::string tool = requested;
1643 "no weighted model counter is available; install one (ganak, "
1644 "sharpsat-td, dpmc, weightmc) or add its directory to "
1645 "provsql.tool_search_path");
1652 throw CircuitException(
"Tool '" + tool +
"' is disabled in the tool registry");
1660 rec->
binary +
" not found on PATH; install it or add its "
1661 "directory to provsql.tool_search_path");
1665 tool +
" needs '" + dep +
"' on PATH; install it or add its "
1666 "directory to provsql.tool_search_path");
1668 const bool weightmc_io = (rec->
parser ==
"weightmc");
1671 const std::string &dirname = tmp.
path();
1672 std::string filename = tmp.
file(
"input");
1673 std::string outfilename = tmp.
file(
"input.out");
1675 std::ofstream ofs(filename);
1684 int id =
static_cast<int>(in) + 1;
1685 ofs <<
"c p weight " <<
id <<
' ' <<
getProb(in) <<
" 0\n";
1686 ofs <<
"c p weight -" <<
id <<
' ' << (1.0 -
getProb(in)) <<
" 0\n";
1694 double epsilon = 0.8;
1696 std::stringstream ssopt(opt);
1697 std::string delta_s, epsilon_s;
1698 getline(ssopt, delta_s,
';');
1699 getline(ssopt, epsilon_s,
';');
1700 try {
double e = stod(epsilon_s);
if(e != 0) epsilon = e; }
1701 catch(
const std::exception &) {}
1703 const double pivotAC = 2*ceil(exp(3./2)*(1+1/epsilon)*(1+1/epsilon));
1706 filename, outfilename, rec->
binary,
1707 {{
"tmpdir", dirname}, {
"pivotAC", std::to_string(pivotAC)}});
1710 CHECK_FOR_INTERRUPTS();
1714 std::ifstream ifs(outfilename.c_str());
1718 std::string line, prev_line;
1719 while(getline(ifs, line)) prev_line = line;
1720 std::stringstream ss(prev_line);
1722 ss >> result >> result >> result >> result >> result;
1723 std::istringstream iss(result);
1724 std::string val, exp;
1725 getline(iss, val,
'x');
1729 double value = stod(val);
1730 double exponent = stod(exp.substr(2));
1731 ret = value * pow(2.0, exponent);
1735 std::string line, matched;
1736 while(getline(ifs, line))
1737 if(line.rfind(
"c s exact", 0) == 0 || line.rfind(
"s wmc", 0) == 0)
1741 ret = parse_wmc_value(matched, tool.c_str());
1752 gate_t g, std::set<gate_t> &seen,
1753 std::unordered_map<gate_t, double> &memo)
const
1755 check_stack_depth();
1761 auto it = memo.find(g);
1762 if(it != memo.end())
1775 const std::size_t seen_before = seen.size();
1790 std::map<gate_t, double> groups;
1791 std::set<gate_t> local_mulins;
1792 std::set<std::pair<gate_t, unsigned> > mulin_seen;
1798 if(local_mulins.find(group)==local_mulins.end()) {
1799 if(seen.find(group)!=seen.end())
1803 local_mulins.insert(group);
1805 auto p = std::make_pair(group,
getInfo(c));
1806 if(mulin_seen.find(p)==mulin_seen.end()) {
1808 mulin_seen.insert(p);
1814 for(
const auto [k, v]: groups)
1836 if (p == 0.0 || p == 1.0) {
1840 if(seen.find(g)!=seen.end())
1850 if(seen.find(child)!=seen.end())
1863 if(seen.size() == seen_before)
1869 gate_t root, std::set<gate_t> &seen,
1870 std::unordered_map<gate_t, double> &memo)
const
1872 const std::size_t seen_before = seen.size();
1876 std::unordered_map<gate_t, double> val;
1881 std::unordered_set<gate_t> island_mulvars;
1882 std::vector<gate_t> stack{root};
1884 while(!stack.empty()) {
1885 const gate_t g = stack.back();
1886 if(val.find(g) != val.end()) {
1897 if(p != 0.0 && p != 1.0) {
1898 if(seen.find(g) != seen.end())
1908 if(island_mulvars.insert(child).second) {
1909 if(seen.find(child) != seen.end())
1927 if(val.find(c) == val.end()) {
1954 if(seen.size() == seen_before)
1955 memo[root] = val[root];
1961 std::set<gate_t> seen;
1962 std::unordered_map<gate_t, double> memo;
1973 auto it =
info.find(g);
1982 const std::vector<gate_t> &muls,
1983 const std::vector<double> &cumulated_probs,
1986 std::vector<gate_t> &prefix)
1993 unsigned mid = (start+end)/2;
1999 double prev_start = (start == 0) ? 0. : cumulated_probs[start - 1];
2002 (cumulated_probs[mid] - prev_start) /
2003 (cumulated_probs[end] - prev_start));
2007 prefix.push_back(g);
2010 prefix.push_back(not_g);
2023 double diff = a - b;
2024 constexpr double epsilon = std::numeric_limits<double>::epsilon() * 10;
2026 return (diff < epsilon && diff > -epsilon);
2031 std::map<gate_t,std::vector<gate_t> > var2mulinput;
2033 var2mulinput[*
getWires(mul).begin()].push_back(mul);
2037 for(
const auto &[var, muls]: var2mulinput)
2039 const unsigned n = muls.size();
2040 std::vector<double> cumulated_probs(n);
2041 double cumulated_prob=0.;
2043 for(
unsigned i=0; i<n; ++i) {
2044 cumulated_prob +=
getProb(muls[i]);
2045 cumulated_probs[i] = cumulated_prob;
2050 std::vector<gate_t> prefix;
2051 prefix.reserve(
static_cast<unsigned>(log(n)/log(2)+2));
2060 check_stack_depth();
2104 if(seen.find(g)!=seen.end())
2123 std::set<gate_t> &seen,
2130 std::unordered_map<gate_t, gate_t> val;
2131 std::vector<gate_t> stack{root};
2133 while(!stack.empty()) {
2134 const gate_t g = stack.back();
2135 if(val.find(g) != val.end()) {
2143 if(seen.find(g) != seen.end())
2162 if(val.find(c) == val.end()) {
2189 std::set<gate_t> seen;
2207 if(method==
"compilation") {
2209 }
else if(method==
"tree-decomposition") {
2213 *
this, g, td}.build();
2217 }
else if(method==
"interpret-as-dd") {
2229 *
this, g, td}.build();
2255 if(name==
"default" || name==
"tree-decomposition" || name==
"interpret-as-dd")
2256 return makeDD(g, name==
"default" ? std::string() : name,
"");
static constexpr const char * too_large_to_print
The error of toStringHelper past PG's limit for a text value.
static std::string selectTool(const std::string &operation, const std::string &preferred="")
static const size_t kSieveMaxClauses
Largest clause count for which the 2^m sieve enumeration is admitted.
static std::string chooseCompiler()
static constexpr bool almost_equals(double a, double b)
Check whether two double values are approximately equal.
Boolean provenance circuit with support for knowledge compilation.
constexpr unsigned DNNF_CERT_INFO
d-DNNF certificate value for the (gate-type-specific) per-gate info field.
BooleanGate
Gate types for a Boolean provenance circuit.
@ MULVAR
Auxiliary gate grouping all MULIN siblings.
@ NOT
Logical negation of a single child gate.
@ OR
Logical disjunction of child gates.
@ AND
Logical conjunction of child gates.
@ IN
Input (variable) gate representing a base tuple.
@ UNDETERMINED
Placeholder gate whose type has not been set yet.
@ MULIN
Multivalued-input gate (one of several options).
gate_t
Strongly-typed gate identifier.
std::string to_string(gate_t g)
Convert a gate_t to its decimal string representation.
Out-of-line template method implementations for Circuit<gateType>.
Boolean circuit for provenance formula evaluation.
std::vector< double > prob
Per-gate probability (for IN gates).
bool evaluate(gate_t g, const std::unordered_set< gate_t > &sampled) const
Evaluate the sub-circuit at g on one sampled world.
dDNNF interpretAsDD(gate_t g) const
Build a dDNNF directly from the Boolean circuit's structure.
double independentEvaluationInternal(gate_t g, std::set< gate_t > &seen, std::unordered_map< gate_t, double > &memo) const
Recursive helper for independentEvaluation().
double sieve(const std::vector< gate_t > &clauses, const std::vector< std::set< gate_t > > &supports) const
Exact probability of a monotone DNF by inclusion-exclusion (sieve).
double possibleWorlds(gate_t g) const
Compute the probability by exact enumeration of all possible worlds.
std::vector< CNFInputMapping > tseytinVariableMapping() const
Map each input gate to its DIMACS variable, UUID, probability.
double karpLubyStopping(const std::vector< gate_t > &clauses, const std::vector< std::set< gate_t > > &supports, double eps, double delta, unsigned long max_samples, unsigned long &samples_used, bool &reached_target) const
Karp-Luby FPRAS with the self-adjusting stopping rule (adaptive sample count for a relative (eps,...
void setProb(gate_t g, double p)
Set the probability for gate g and mark the circuit as probabilistic.
dDNNF parseDDNNF(std::istream &in, const std::vector< gate_t > &inputOrder) const
Parse a c2d/d4 NNF stream into a dDNNF over this circuit's input gates.
std::set< gate_t > inputs
Set of IN (input) gate IDs.
bool isDNNFCertified(gate_t g) const
Is gate g certified by the d-DNNF per-gate marking?
void rewriteMultivaluedGatesRec(const std::vector< gate_t > &muls, const std::vector< double > &cumulated_probs, unsigned start, unsigned end, std::vector< gate_t > &prefix)
Recursive helper for rewriteMultivaluedGates().
double evaluateCertifiedIsland(gate_t root, std::set< gate_t > &seen, std::unordered_map< gate_t, double > &memo) const
Iteratively evaluate a certified d-DNNF island.
std::string exportCircuit(gate_t g) const
Export the circuit in the textual format expected by external compilers.
std::string BCS12(gate_t g, std::vector< gate_t > &inputOrder) const
Serialise the sub-circuit at g in d4's BC-S1.2 circuit format.
std::string TseytinCNF(gate_t g, bool display_prob, bool mapping=false) const
Return the Tseytin transformation of the sub-circuit at g as a DIMACS string.
dDNNF parsePaniniDD(const std::string &outfilename) const
Parse a Panini (KCBox) DD output file into a ProvSQL d-DNNF.
std::string toStringHelper(gate_t g, BooleanGate parent, const std::unordered_map< gate_t, std::string > *labels) const
Internal recursive helper for the two toString() variants.
double karpLuby(const std::vector< gate_t > &clauses, const std::vector< std::set< gate_t > > &supports, unsigned long samples) const
Karp-Luby FPRAS estimate of a DNF-shaped circuit's probability (fixed sample budget,...
dDNNF compilation(gate_t g, std::string compiler, std::string *resolved=nullptr) const
Compile the sub-circuit rooted at g to a dDNNF via an external tool.
dDNNF makeDD(gate_t g, const std::string &method, const std::string &args) const
Dispatch to the appropriate d-DNNF construction method.
gate_t setGate(BooleanGate type) override
Allocate a new gate with type type and no UUID.
unsigned getInfo(gate_t g) const
Return the integer annotation for gate g.
friend class dDNNFTreeDecompositionBuilder
double wmcCount(gate_t g, const std::string &tool, const std::string &opt) const
Weighted model counting through a registered external counter.
gate_t addGate() override
Allocate a new gate with a default-initialised type.
double monteCarlo(gate_t g, unsigned samples) const
Estimate the probability via Monte Carlo sampling.
void rewriteMultivaluedGates()
Rewrite all MULVAR/MULIN gate clusters into standard AND/OR/NOT circuits.
double getProb(gate_t g) const
Return the probability stored for gate g.
bool dnfShapeInfo(gate_t g, std::size_t &num_clauses) const
Cheap shape test: is the circuit DNF-shaped, and how many clauses?
void setInfo(gate_t g, unsigned info)
Store an integer annotation on gate g.
void dnfBounds(const std::vector< std::set< gate_t > > &clauses, double &lower, double &upper) const
Cheap certified probability interval [lower,upper] of a monotone DNF, without compiling it (Olteanu-H...
virtual std::string toString(gate_t g) const override
Return a textual description of gate g for debugging.
bool dnfShape(gate_t g, std::vector< gate_t > &clauses, std::vector< std::set< gate_t > > &supports) const
Detect the DNF shape the Karp-Luby FPRAS requires.
std::map< gate_t, unsigned > info
Per-gate integer info (for MULIN gates).
gate_t interpretCertifiedIsland(gate_t root, std::set< gate_t > &seen, dDNNF &dd) const
Iteratively copy a certified island into dd.
dDNNF makeDDByName(gate_t g, const std::string &name) const
Build a dDNNF from a single compiler/route name.
gate_t interpretAsDDInternal(gate_t g, std::set< gate_t > &seen, dDNNF &dd) const
Recursive helper for interpretAsDD().
double independentEvaluation(gate_t g) const
Compute the probability exactly when inputs are independent.
std::set< gate_t > mulinputs
Set of MULVAR gate IDs.
static std::string checkCompiler(std::string compiler)
Exception type thrown by circuit operations on invalid input.
std::vector< gate_t > & getWires(gate_t g)
BooleanGate getGateType(gate_t g) const
virtual gate_t setGate(const uuid &u, gateType type)
Create or update the gate associated with UUID u.
void addWire(gate_t f, gate_t t)
Add a directed wire from gate f (parent) to gate t (child).
std::vector< BooleanGate > gates
uuid getUUID(gate_t g) const
gate_t getGate(const uuid &u)
Return (or create) the gate associated with UUID u.
bool hasGate(const uuid &u) const
Test whether a gate with UUID u exists.
std::vector< gate_t >::size_type getNbGates() const
Return the total number of gates in the circuit.
virtual gate_t addGate()
Allocate a new gate with a default-initialised type.
Exception thrown when a tree decomposition cannot be constructed.
Tree decomposition of a Boolean circuit's primal graph.
static constexpr int MAX_TREEWIDTH
Maximum supported treewidth.
A d-DNNF circuit supporting exact probabilistic and game-theoretic evaluation.
void setRoot(gate_t g)
Set the root gate.
void simplify()
Simplify the d-DNNF by removing redundant constants.
RAII guard around a freshly mkdtemp'd /tmp directory.
std::string file(const std::string &basename)
Build a path under the temp dir and register it for cleanup.
const std::string & path() const
void keep()
Leave the directory on disk; cleanup is skipped at scope exit.
Constructs a d-DNNF from a Boolean circuit and its tree decomposition.
In-extension KCMCP client: compile a Boolean problem on a warm, socket-attached knowledge compiler in...
const char * provsql_kcmcp_managed_endpoint(void)
Read the live endpoint of the managed KCMCP server from shared memory (e.g.
std::string kcmcp_compile(const std::string &endpoint, uint8_t input_format, const std::string &problem)
Compile problem on a KCMCP server and return its d-DNNF NNF text.
ToolRegistry & tool_registry()
Shorthand for ToolRegistry::instance().
std::string expandCommandTemplate(const std::string &tpl, const std::string &binary, const std::string &in, const std::string &out, const std::vector< std::pair< std::string, std::string > > &extra={})
Expand a command template into a runnable shell command line.
int provsql_verbose
Verbosity level; controlled by the provsql.verbose_level GUC.
int provsql_monte_carlo_seed
Seed for the Monte Carlo sampler; -1 means non-deterministic (std::random_device); controlled by the ...
bool provsql_interrupted
Set by provsql_sigint_handler: this backend received a cancel.
char * provsql_fallback_compiler
Compiler used by BooleanCircuit::makeDD as the final fallback after interpretAsDD and tree-decomposit...
Uniform error-reporting macros for ProvSQL.
#define provsql_error(fmt,...)
Report a fatal ProvSQL error and abort the current transaction.
#define provsql_notice(fmt,...)
Emit a ProvSQL informational notice (execution continues).
void provsql_check_result_size(size_t bytes, const char *message)
Throw if a text value of bytes is past what PostgreSQL can hold in a value (1 GB),...
Cancellation of the long C++ evaluation loops.
Core types, constants, and utilities shared across ProvSQL.