ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
BooleanCircuit.h
Go to the documentation of this file.
1/**
2 * @file BooleanCircuit.h
3 * @brief Boolean provenance circuit with support for knowledge compilation.
4 *
5 * @c BooleanCircuit represents the provenance formula of a query result
6 * as a Boolean circuit (AND/OR/NOT/IN gates). It supports multiple
7 * methods for computing the probability of the formula being true under
8 * tuple-independent probabilistic databases:
9 *
10 * | Method | Description |
11 * |------------------------|----------------------------------------------------------|
12 * | @c possibleWorlds() | Exact enumeration over all 2^n possible worlds |
13 * | @c compilation() | Knowledge compilation to d-DNNF via an external tool |
14 * | @c monteCarlo() | Monte Carlo sampling approximation |
15 * | @c WeightMC() | Weighted model counting via weightmc |
16 * | @c independentEvaluation() | Exact evaluation for read-once circuits |
17 * | @c interpretAsDD() | Direct tree-decomposition-based compilation |
18 * | @c makeDD() | Generic d-DNNF construction dispatcher |
19 *
20 * ### Multivalued inputs (@c MULIN / @c MULVAR)
21 * Multivalued input gates model tuples drawn from a discrete probability
22 * distribution. @c rewriteMultivaluedGates() rewrites them into standard
23 * AND/OR/NOT circuits before knowledge compilation.
24 *
25 * The circuit is Boost-serialisable for transmission to external processes.
26 */
27#ifndef BOOLEAN_CIRCUIT_H
28#define BOOLEAN_CIRCUIT_H
29
30#include <unordered_map>
31#include <unordered_set>
32#include <set>
33#include <map>
34#include <vector>
35#include <iosfwd>
36
37#include <boost/archive/binary_oarchive.hpp>
38#include <boost/serialization/unordered_map.hpp>
39#include <boost/serialization/map.hpp>
40#include <boost/serialization/set.hpp>
41#include <boost/serialization/vector.hpp>
42
43#include "Circuit.hpp"
44
45/**
46 * @brief Gate types for a Boolean provenance circuit.
47 *
48 * - @c UNDETERMINED Placeholder for a gate whose type has not been set yet.
49 * - @c AND Logical conjunction of child gates.
50 * - @c OR Logical disjunction of child gates.
51 * - @c NOT Logical negation of a single child gate.
52 * - @c IN An input (variable) gate representing a base tuple.
53 * - @c MULIN A multivalued-input gate (one of several options).
54 * - @c MULVAR Auxiliary gate grouping all @c MULIN siblings.
55 */
56enum class BooleanGate {
57 UNDETERMINED, ///< Placeholder gate whose type has not been set yet
58 AND, ///< Logical conjunction of child gates
59 OR, ///< Logical disjunction of child gates
60 NOT, ///< Logical negation of a single child gate
61 IN, ///< Input (variable) gate representing a base tuple
62 MULIN, ///< Multivalued-input gate (one of several options)
63 MULVAR ///< Auxiliary gate grouping all MULIN siblings
64};
65class dDNNF;
66
67/**
68 * @brief d-DNNF certificate value for the (gate-type-specific) per-gate
69 * info field.
70 *
71 * On an OR (@c gate_plus) gate, info = @c DNNF_CERT_INFO asserts
72 * **determinism**: the children are mutually exclusive. On an AND
73 * (@c gate_times) gate it asserts **decomposability**: the children
74 * mention disjoint sets of variables. Both are semantic properties of
75 * the gate's (content-addressed) children, so a truthfully-set mark
76 * remains true however the gate is later re-derived. Set by
77 * constructions that establish the property structurally (the
78 * decomposition-aligned reachability compilation); trusted by
79 * @c independentEvaluation() and @c interpretAsDD(), the same trust
80 * model as the planner-asserted inversion-free certificate.
81 */
82constexpr unsigned DNNF_CERT_INFO = 1;
83
84/**
85 * @brief Boolean circuit for provenance formula evaluation.
86 *
87 * Inherits the gate/wire infrastructure from @c Circuit<BooleanGate> and
88 * adds probability annotation, info integers (for multivalued inputs), and
89 * a rich set of evaluation algorithms.
90 */
91class BooleanCircuit : public Circuit<BooleanGate> {
92private:
93/**
94 * @brief Evaluate the sub-circuit at @p g on one sampled world.
95 *
96 * Each gate in @p sampled is treated as @c true; all other @c IN gates
97 * are @c false.
98 *
99 * @param g Root gate to evaluate.
100 * @param sampled Set of input gates that are @c true in this world.
101 * @return Boolean value of the circuit at gate @p g.
102 */
103bool evaluate(gate_t g, const std::unordered_set<gate_t> &sampled) const;
104
105/**
106 * @brief Memoised helper for @c evaluate(): @p memo holds, per gate, -1
107 * while unevaluated, else its value in the sampled world.
108 */
109bool evaluate(gate_t g, const std::unordered_set<gate_t> &sampled,
110 std::vector<signed char> &memo) const;
111
112/**
113 * @brief Recursive helper for @c interpretAsDD().
114 *
115 * A certified (d-DNNF-marked) gate is handed to
116 * @c interpretCertifiedIsland(); the recursion only walks the
117 * uncertified region.
118 *
119 * @param g Current gate to process.
120 * @param seen Set of variable gates already consumed (read-once check in
121 * the uncertified region; per-island registration inside
122 * certified islands).
123 * @param dd The d-DNNF being constructed.
124 * @return Gate ID in @p dd corresponding to @p g.
125 */
126gate_t interpretAsDDInternal(gate_t g, std::set<gate_t> &seen, dDNNF &dd) const;
127/**
128 * @brief Iteratively copy a certified island into @p dd.
129 *
130 * Island twin of @c evaluateCertifiedIsland() (same discipline, same
131 * iterative post-order): certified ORs are copied as native
132 * deterministic ORs (no De Morgan rewriting), certified ANDs as-is,
133 * shared sub-DAGs map to shared @p dd gates. An uncertified AND/OR
134 * inside the island falls back to @c interpretAsDDInternal().
135 *
136 * @param root Certified gate the island is rooted at.
137 * @param seen Global variable registration (see
138 * @c evaluateCertifiedIsland()).
139 * @param dd The d-DNNF being constructed.
140 * @return Gate ID in @p dd corresponding to @p root.
141 */
142gate_t interpretCertifiedIsland(gate_t root, std::set<gate_t> &seen,
143 dDNNF &dd) const;
144/**
145 * @brief Recursive helper for @c independentEvaluation().
146 *
147 * A certified (d-DNNF-marked) gate is handed to
148 * @c evaluateCertifiedIsland(); the recursion only walks the
149 * uncertified region.
150 *
151 * @param g Current gate to evaluate.
152 * @param seen Set of variable gates (IN / MULVAR) already consumed; a second
153 * occurrence means the circuit is not read-once.
154 * @param memo Memoised probability of variable-free (constant-only) gates, so a
155 * shared constant subgraph is evaluated once -- this is what keeps
156 * the whole evaluation @c O(circuit) rather than re-traversing
157 * shared subgraphs. Variable-bearing gates are never memoised (a
158 * re-visit must reach @p seen and throw).
159 * @return Probability at gate @p g.
160 */
162 gate_t g, std::set<gate_t> &seen,
163 std::unordered_map<gate_t, double> &memo) const;
164/**
165 * @brief Iteratively evaluate a certified d-DNNF island.
166 *
167 * Walks the maximal region of certified AND/OR gates (plus the NOT and
168 * input gates they reach) under @p root with an explicit post-order
169 * stack -- certified circuits can be as deep as the data (e.g. the
170 * decomposition-aligned reachability circuits of path-like graphs), so
171 * recursion would overflow the stack. Within the island every gate is
172 * computed once (sharing is licensed by the certificate): certified OR
173 * = sum (determinism), certified AND = product (decomposability), and
174 * each variable registers once in @p seen, so entanglement with the
175 * outside -- or with another island -- throws like a read-once
176 * violation. An uncertified AND/OR inside the island falls back to
177 * @c independentEvaluationInternal() (standard read-once rules).
178 *
179 * @param root Certified gate the island is rooted at.
180 * @param seen Global variable registration shared with the uncertified
181 * region.
182 * @param memo Constant-only global memo (used by the uncertified
183 * fallback).
184 * @return Probability at @p root.
185 */
187 gate_t root, std::set<gate_t> &seen,
188 std::unordered_map<gate_t, double> &memo) const;
189
190public:
191/**
192 * @brief Is gate @p g certified by the d-DNNF per-gate marking?
193 *
194 * @c true iff @p g is an OR marked deterministic or an AND marked
195 * decomposable (info = @c DNNF_CERT_INFO); see @c DNNF_CERT_INFO for the
196 * semantics and trust model.
197 *
198 * @param g Gate to test.
199 * @return Whether the gate carries the d-DNNF certificate.
200 */
201bool isDNNFCertified(gate_t g) const {
202 const auto t = getGateType(g);
203 return (t == BooleanGate::AND || t == BooleanGate::OR) &&
205}
206
207private:
208/**
209 * @brief Recursive helper for @c rewriteMultivaluedGates().
210 * @param muls Gates in the MULVAR group being rewritten.
211 * @param cumulated_probs Cumulative probability thresholds for each MULIN.
212 * @param start First index in @p muls to process.
213 * @param end One past the last index in @p muls to process.
214 * @param prefix Current AND-chain prefix being built.
215 */
217 const std::vector<gate_t> &muls,
218 const std::vector<double> &cumulated_probs,
219 unsigned start,
220 unsigned end,
221 std::vector<gate_t> &prefix);
222
223protected:
224std::set<gate_t> inputs; ///< Set of IN (input) gate IDs
225std::set<gate_t> mulinputs; ///< Set of MULVAR gate IDs
226std::vector<double> prob; ///< Per-gate probability (for IN gates)
227std::map<gate_t, unsigned> info; ///< Per-gate integer info (for MULIN gates)
228bool probabilistic=false; ///< @c true if any gate has a non-unit probability
229
230public:
231/** @brief Construct an empty Boolean circuit. */
239}
240
241/** @copydoc Circuit::addGate() */
242gate_t addGate() override;
243/** @copydoc Circuit::setGate(gateType) */
244gate_t setGate(BooleanGate type) override;
245/** @copydoc Circuit::setGate(const uuid&, gateType) */
246gate_t setGate(const uuid &u, BooleanGate type) override;
247
248/**
249 * @brief Create a new gate with a probability annotation.
250 * @param t Gate type (typically @c BooleanGate::IN).
251 * @param p Probability of this gate being @c true.
252 * @return Gate identifier.
253 */
254gate_t setGate(BooleanGate t, double p);
255
256/**
257 * @brief Create (or update) a gate with a UUID and probability.
258 * @param u UUID string.
259 * @param t Gate type.
260 * @param p Probability of this gate being @c true.
261 * @return Gate identifier.
262 */
263gate_t setGate(const uuid &u, BooleanGate t, double p);
264
265/**
266 * @brief Return the set of input (IN) gate IDs.
267 * @return Const reference to the set of IN gate identifiers.
268 */
269const std::set<gate_t> &getInputs() const {
270 return inputs;
271}
272
273/**
274 * @brief Return @c true if the circuit contains any MULIN gates.
275 *
276 * Multivalued inputs are normally rewritten into AND/OR/NOT/IN gates by
277 * @c rewriteMultivaluedGates() before the circuit is consumed by an
278 * evaluation method. Algorithms that cannot handle multivalued inputs
279 * directly can use this as a precondition check.
280 *
281 * @return @c true iff at least one @c MULIN gate is present.
282 */
284 return !mulinputs.empty();
285}
286
287/**
288 * @brief Set the probability for gate @p g and mark the circuit as probabilistic.
289 * @param g Gate identifier.
290 * @param p Probability value in [0, 1].
291 */
292void setProb(gate_t g, double p) {
293 if(!probabilistic && p!=1.)
294 probabilistic=true;
295 prob[static_cast<std::underlying_type<gate_t>::type>(g)]=p;
296}
297
298/**
299 * @brief Return the probability stored for gate @p g.
300 * @param g Gate identifier.
301 * @return Probability value.
302 */
303double getProb(gate_t g) const {
304 return prob[static_cast<std::underlying_type<gate_t>::type>(g)];
305}
306
307/**
308 * @brief Return @c true if any gate has a non-trivial (< 1) probability.
309 * @return @c true iff at least one gate has a probability strictly less than 1.
310 */
311bool isProbabilistic() const {
312 return probabilistic;
313}
314
315/**
316 * @brief Store an integer annotation on gate @p g.
317 *
318 * Used to record the index of a @c MULIN gate within its @c MULVAR group.
319 *
320 * @param g Gate identifier.
321 * @param info Integer to store.
322 */
323void setInfo(gate_t g, unsigned info);
324
325/**
326 * @brief Return the integer annotation for gate @p g.
327 * @param g Gate identifier.
328 * @return Stored integer, or 0 if not set.
329 */
330unsigned getInfo(gate_t g) const;
331
332/**
333 * @brief Compute the probability by exact enumeration of all possible worlds.
334 *
335 * Only tractable for circuits with a small number of input gates.
336 *
337 * @param g Root gate.
338 * @return Exact probability.
339 */
340double possibleWorlds(gate_t g) const;
341
342/**
343 * @brief Compile the sub-circuit rooted at @p g to a @c dDNNF via an external tool.
344 *
345 * Writes the circuit in DIMACS/DNNF format, invokes @p compiler as a
346 * subprocess, and parses the resulting d-DNNF.
347 *
348 * @param g Root gate.
349 * @param compiler Command to invoke (e.g. "d4", "c2d", "minic2d"). Empty
350 * auto-selects the highest-preference available tool.
351 * @param resolved If non-null, set to the tool actually used (after the
352 * empty -> auto-select resolution), so callers can report
353 * WHICH compiler ran rather than just "compilation".
354 * @return The compiled @c dDNNF.
355 */
356dDNNF compilation(gate_t g, std::string compiler,
357 std::string *resolved = nullptr) const;
358
359static std::string checkCompiler(std::string compiler);
360
361/**
362 * @brief Parse a c2d/d4 NNF stream into a @c dDNNF over this circuit's input
363 * gates.
364 *
365 * Shared by the CLI @c compilation() path and the KCMCP client: both obtain
366 * the same NNF text (from a temp file or a socket @c RESULT) and parse it
367 * identically. @p inputOrder maps d4 circuit-mode variables (1..k) to IN
368 * gates; an empty vector means CNF mode, where d-DNNF variable @c v stands
369 * for gate id @c v-1 (real only for IN gates, every other being a Tseytin
370 * auxiliary that is projected out).
371 *
372 * @param in NNF text stream.
373 * @param inputOrder Circuit-mode input-variable to IN-gate map (empty = CNF).
374 * @return The compiled @c dDNNF (empty if the formula is unsat).
375 */
376dDNNF parseDDNNF(std::istream &in,
377 const std::vector<gate_t> &inputOrder) const;
378
379/**
380 * @brief Estimate the probability via Monte Carlo sampling.
381 *
382 * @param g Root gate.
383 * @param samples Number of independent worlds to sample.
384 * @return Estimated probability.
385 */
386double monteCarlo(gate_t g, unsigned samples) const;
387
388/**
389 * @brief Detect the DNF shape the Karp-Luby FPRAS requires.
390 *
391 * Recognises the two tractable regimes: (a) a single AND-of-leaves
392 * clause, or (b) a top-level @c OR whose every child is an AND-only
393 * sub-circuit over @c IN leaves (no @c OR below the root, no @c NOT, no
394 * multivalued input). Cross-clause leaf sharing is allowed and is the
395 * normal Karp-Luby setting.
396 *
397 * On success, @p clauses receives one root per top-level disjunct (or the
398 * singleton root @p g in regime (a)) and @p supports[i] the set of @c IN
399 * leaves reachable from @p clauses[i] through its AND-only stratum -- the
400 * support determines @c Pr[C_i] (the product of leaf marginals) and the
401 * conditional sampler.
402 *
403 * @param g Root gate.
404 * @param clauses Output: the top-level clause roots.
405 * @param supports Output: per-clause set of reachable @c IN leaves.
406 * @return @c true iff the circuit is DNF-shaped (regime (a)/(b)).
407 */
408bool dnfShape(gate_t g,
409 std::vector<gate_t> &clauses,
410 std::vector<std::set<gate_t> > &supports) const;
411
412/**
413 * @brief Cheap shape test: is the circuit DNF-shaped, and how many clauses?
414 *
415 * The @c O(circuit) half of @c dnfShape -- validates the OR-of-ANDs-of-leaves
416 * shape with a single global visited-set (no per-clause re-walk) and returns the
417 * clause count, WITHOUT materialising the per-clause supports (whose total size
418 * can be @c O(m*N)). Used by the chooser to rank @c sieve; the supports are
419 * built only if @c sieve / @c karp-luby actually runs (via @c dnfShape).
420 *
421 * @param g Root gate.
422 * @param num_clauses Output: number of top-level clauses.
423 * @return @c true iff DNF-shaped.
424 */
425bool dnfShapeInfo(gate_t g, std::size_t &num_clauses) const;
426
427/**
428 * @brief Karp-Luby FPRAS estimate of a DNF-shaped circuit's probability
429 * (fixed sample budget, stratified).
430 *
431 * Implements the Karp-Luby coverage estimator for the DNF-counting problem
432 * (@c \#DNF) under tuple-independent inputs: with @c p_i the product of the
433 * marginals of @p supports[i] and @c S the sum of the @c p_i (so @c S in
434 * @c [Pr[F], m*Pr[F]]), the estimator over clause @c i samples a satisfying
435 * assignment of @c C_i (its support forced true, every other leaf drawn from
436 * its marginal), finds the smallest clause index @c j the assignment
437 * satisfies, and accepts iff @c j == i; @c Pr[F] is then @c sum_i p_i times
438 * the per-clause acceptance rate. The acceptance probability is @c Pr[F]/S in
439 * @c [1/m, 1], so the sample count for an @c (eps,delta) guarantee is
440 * independent of @c Pr[F], unlike naive Monte Carlo.
441 *
442 * The @p samples rounds are spread across clauses by *stratified* allocation
443 * (@c n_i proportional to @c p_i/S, every clause sampled at least once),
444 * estimating each clause's acceptance rate separately and combining
445 * @c sum_i p_i * acceptRate_i. This removes the variance of the categorical
446 * clause draw used by the textbook estimator (between-strata variance),
447 * tightening the estimate at the same budget by up to a factor @c m. When
448 * @p samples @c < @c m there are too few rounds for one per clause, so the
449 * method falls back to the unstratified categorical-draw estimator (still
450 * unbiased for any budget).
451 *
452 * The @p clauses / @p supports are those returned by @c dnfShape. The
453 * @c mt19937_64 is seeded from @c provsql.monte_carlo_seed exactly as
454 * @c monteCarlo, so the estimate is reproducible under a pinned seed.
455 *
456 * @param clauses Top-level clause roots (from @c dnfShape).
457 * @param supports Per-clause reachable @c IN leaves (from @c dnfShape).
458 * @param samples Resolved number of sampling rounds.
459 * @return The Karp-Luby probability estimate.
460 */
461double karpLuby(const std::vector<gate_t> &clauses,
462 const std::vector<std::set<gate_t> > &supports,
463 unsigned long samples) const;
464
465/**
466 * @brief Exact probability of a monotone DNF by inclusion-exclusion (sieve).
467 *
468 * @c Pr[∨_i c_i] = Σ_{∅≠S⊆clauses} (-1)^{|S|+1} Pr[∧_{i∈S} c_i]. Each clause is
469 * a conjunction of positive input leaves, so the conjunction of a set @c S of
470 * clauses is the AND of the union of their supports, and over independent
471 * inputs @c Pr[∧_{i∈S} c_i] = ∏_{leaf ∈ ∪supports(S)} getProb(leaf). Exact, and
472 * @c O(2^m) in the clause count @c m -- the portfolio member to pick when @c m
473 * is small (a handful of clauses), where it beats the general compilers.
474 *
475 * @p clauses / @p supports are those returned by @c dnfShape (monotone DNF over
476 * input leaves). Throws when @c m exceeds @c kSieveMaxClauses (the @c 2^m
477 * enumeration would be impractical) so the caller can pick another method.
478 *
479 * @param clauses Top-level clause roots (from @c dnfShape).
480 * @param supports Per-clause reachable @c IN leaves (from @c dnfShape).
481 * @return The exact probability.
482 */
483double sieve(const std::vector<gate_t> &clauses,
484 const std::vector<std::set<gate_t> > &supports) const;
485
486/**
487 * @brief Cheap certified probability interval @c [lower,upper] of a monotone
488 * DNF, without compiling it (Olteanu-Huang-Koch d-tree leaf bound).
489 *
490 * Implements the @c Independent heuristic of Olteanu, Huang & Koch,
491 * "Approximate Confidence Computation in Probabilistic Databases" (ICDE 2010,
492 * Fig. 3). The clauses are greedily partitioned into @e buckets of pairwise
493 * independent clauses (disjoint supports), clauses taken in descending
494 * marginal-probability order so the most probable clauses anchor the buckets.
495 * Each bucket's clauses are mutually independent, so its probability is the
496 * independent-or @c 1-∏(1-P(d)) with @c P(d)=∏_{leaf∈supports[d]} getProb(leaf).
497 * Then, since @c Φ is the disjunction of all buckets:
498 *
499 * - @c lower = max_i P(B_i): a sub-disjunction is a lower bound;
500 * - @c upper = min(1, Σ_i P(B_i)): the union bound.
501 *
502 * Both bounds are sound for @e any partition (the greedy one only affects
503 * tightness), so @c lower ≤ Pr[Φ] ≤ upper always holds. When the clauses are
504 * mutually independent (disjoint supports) they all land in a single bucket and
505 * @c lower=upper=Pr[Φ], i.e. the interval collapses to the exact value.
506 * @c O(m^2) in the clause count @c m.
507 *
508 * A monotone DNF is fully determined (for probability) by its per-clause input
509 * supports, so this takes only the @c supports (the @c set per clause returned
510 * by @c dnfShape, or a cofactor's residual clause set in the @c DTree engine);
511 * the clause root gates are not needed.
512 *
513 * @param clauses Per-clause input-leaf supports (a monotone DNF as a set of
514 * clauses, each a set of @c IN leaves).
515 * @param lower [out] Certified lower bound on @c Pr[Φ].
516 * @param upper [out] Certified upper bound on @c Pr[Φ].
517 */
518void dnfBounds(const std::vector<std::set<gate_t> > &clauses,
519 double &lower, double &upper) const;
520
521/**
522 * @brief Karp-Luby FPRAS with the self-adjusting stopping rule (adaptive
523 * sample count for a relative @c (eps,delta) guarantee).
524 *
525 * The Dagum-Karp-Luby-Ross stopping rule (SICOMP 2000, the optimal form of
526 * the Karp-Luby-Madras 1989 self-adjusting rule): rather than fixing the
527 * number of rounds from the worst-case acceptance probability @c 1/m, draw
528 * coverage trials (clause @c i with probability @c p_i/S, then the
529 * smallest-index coverage test of @c karpLuby) until the *accept count*
530 * reaches the deterministic threshold
531 * @c Y1 = 1 + (1+eps) * 4*(e-2)*ln(2/delta)/eps^2, then return
532 * @c S * Y1 / N over the @c N rounds actually run. That estimate is a
533 * relative @c (eps,delta) approximation of @c Pr[F], and @c N adapts to the
534 * true acceptance probability @c Pr[F]/S (expected @c N is @c Y1*S/Pr[F],
535 * i.e. up to @c m times fewer rounds than the fixed bound when the clauses
536 * barely overlap).
537 *
538 * Sampling stops early at @p max_samples rounds; @p reached_target is then
539 * @c false and the return is the plain unbiased @c S*accepts/N estimate over
540 * the spent budget (the @c (eps,delta) target was not met -- the caller
541 * reports the weaker guarantee actually achieved).
542 *
543 * @param clauses Top-level clause roots (from @c dnfShape).
544 * @param supports Per-clause reachable @c IN leaves (from @c dnfShape).
545 * @param eps Target relative error (in @c (0,1]).
546 * @param delta Target failure probability (in @c (0,1)).
547 * @param max_samples Hard cap on the number of rounds.
548 * @param samples_used Output: rounds actually run.
549 * @param reached_target Output: whether the stopping threshold was reached
550 * before @p max_samples (i.e. the guarantee holds).
551 * @return The Karp-Luby probability estimate.
552 */
553double karpLubyStopping(const std::vector<gate_t> &clauses,
554 const std::vector<std::set<gate_t> > &supports,
555 double eps, double delta,
556 unsigned long max_samples,
557 unsigned long &samples_used,
558 bool &reached_target) const;
559
560/**
561 * @brief Weighted model counting through a registered external counter.
562 *
563 * Generic over the counter: @p tool names a registry record with the @c "wmc"
564 * operation (today @c weightmc, @c ganak, @c sharpsat-td, @c dpmc, or any
565 * tool an administrator registers). The record's @c binary, @c dependencies,
566 * @c argtpl and @c parser drive the whole call -- which weighted-CNF dialect
567 * to write, the command to run, and how to read the count back -- so there is
568 * no per-counter code path. Two output/input conventions are understood, by
569 * @c parser: @c "wmc-line" (MCC-2024 weighted DIMACS in, a @c "c s exact" /
570 * @c "s wmc" count line out) and @c "weightmc" (weightmc's own dialect in, a
571 * @c "mantissa x 2^exp" line out).
572 *
573 * @param g Root gate of the sub-circuit.
574 * @param tool Logical name of the wmc tool to use.
575 * @param opt Tool options; for the approximate counters of the form
576 * @c "delta;epsilon" (drives the @c {pivotAC} placeholder).
577 * @return The weighted model count = P(formula).
578 */
579double wmcCount(gate_t g, const std::string &tool, const std::string &opt) const;
580
581/**
582 * @brief Compute the probability exactly when inputs are independent.
583 *
584 * Applicable when the circuit has no shared input gate (i.e., each
585 * input appears at most once).
586 *
587 * @param g Root gate.
588 * @return Exact probability.
589 */
590double independentEvaluation(gate_t g) const;
591
592/**
593 * @brief Rewrite all MULVAR/MULIN gate clusters into standard AND/OR/NOT circuits.
594 *
595 * Must be called before any evaluation method when the circuit contains
596 * multivalued input gates.
597 */
599
600/**
601 * @brief Build a @c dDNNF directly from the Boolean circuit's structure.
602 *
603 * Used as a fallback when no external compiler is available and the
604 * circuit is already in a form that can be interpreted as a d-DNNF.
605 *
606 * @param g Root gate.
607 * @return A @c dDNNF wrapping the same structure.
608 */
609dDNNF interpretAsDD(gate_t g) const;
610
611/**
612 * @brief Dispatch to the appropriate d-DNNF construction method.
613 *
614 * @param g Root gate.
615 * @param method Compilation method name (e.g. "tree-decomposition",
616 * "d4", "c2d"…).
617 * @param args Additional arguments forwarded to the chosen method.
618 * @return The constructed @c dDNNF.
619 */
620dDNNF makeDD(gate_t g, const std::string &method, const std::string &args) const;
621
622/**
623 * @brief Build a @c dDNNF from a single compiler/route name.
624 *
625 * Resolves the name the way a user (or Studio) thinks of it, with no
626 * separate @c method / @c args split:
627 * - the in-process meta-routes @c "tree-decomposition",
628 * @c "interpret-as-dd", @c "default" (and the empty string) go
629 * through @c makeDD;
630 * - any other name is an external compiler (@c "d4", @c "d4v2",
631 * @c "c2d", @c "minic2d", @c "dsharp", @c "panini-*") and is passed
632 * straight to @c compilation.
633 *
634 * This is the single dispatch point shared by @c compile_to_ddnnf_dot,
635 * @c compile_to_ddnnf (NNF) and @c ddnnf_stats, so they cannot drift on
636 * which names they accept.
637 *
638 * @param g Root gate.
639 * @param name Compiler or meta-route name.
640 * @return The constructed @c dDNNF.
641 */
642dDNNF makeDDByName(gate_t g, const std::string &name) const;
643
644/** @copydoc Circuit::toString() */
645virtual std::string toString(gate_t g) const override;
646
647/**
648 * @brief Render the sub-circuit at @p g, labelling input gates from a map.
649 *
650 * Same as @c toString(gate_t), but @c IN and @c MULIN gates whose
651 * gate identifier is present in @p labels are rendered using the
652 * mapped string instead of the default @c x@<id@> placeholder. Gates
653 * not found in @p labels fall back to the default rendering.
654 *
655 * @param g Gate to render.
656 * @param labels Optional mapping from input/mulinput gate IDs to
657 * user-supplied labels.
658 * @return Human-readable string.
659 */
660std::string toString(
661 gate_t g,
662 const std::unordered_map<gate_t, std::string> &labels) const;
663
664private:
665/**
666 * @brief Internal recursive helper for the two @c toString() variants.
667 *
668 * The @p parent parameter carries the gate type of the immediate
669 * caller. It drives parenthesis elision in two cases: at the root
670 * (parent set to @c UNDETERMINED) the outer wrap is omitted, and
671 * when @p parent matches the current gate type (associative
672 * AND/OR) the wrap is omitted to flatten same-op nesting. A 1-wire
673 * AND/OR also bypasses the wrap and delegates to its child since
674 * such single-element joins carry no information.
675 *
676 * @param g Gate to render.
677 * @param parent Gate type of the caller, or @c UNDETERMINED at the root.
678 * @param labels Pointer to a label map, or @c nullptr for the
679 * unlabelled rendering.
680 */
681std::string toStringHelper(
682 gate_t g,
683 BooleanGate parent,
684 const std::unordered_map<gate_t, std::string> *labels) const;
685
686public:
687
688/**
689 * @brief Export the circuit in the textual format expected by external compilers.
690 *
691 * Produces a multi-line string encoding all gates reachable from the
692 * circuit in the format used by the standalone @c tdkc tool and external
693 * model counters.
694 *
695 * @param g Root gate.
696 * @return Circuit description string.
697 */
698std::string exportCircuit(gate_t g) const;
699
700/**
701 * @brief Return the Tseytin transformation of the sub-circuit at @p g as a DIMACS string.
702 *
703 * Same encoding as the private @c Tseytin file-emitting overload, but
704 * returned in memory without any file I/O. Useful for surfacing the
705 * CNF to a user or to a knowledge-compilation tool over stdin.
706 *
707 * @param g Root gate.
708 * @param display_prob Include @c w lines listing each input's
709 * probability (and its complement).
710 * @param mapping Prepend @c "c input <var> <uuid> <prob>" comment
711 * lines, one per input gate, so the emitted DIMACS
712 * is self-documenting (the comments are ignored by
713 * every model counter / compiler).
714 * @return DIMACS CNF as a string.
715 */
716std::string TseytinCNF(gate_t g, bool display_prob, bool mapping = false) const;
717
718/**
719 * @brief One row of the Tseytin variable mapping.
720 *
721 * Ties a DIMACS variable index back to the provenance input it stands
722 * for, so an external model count / satisfying assignment can be read
723 * against the original circuit.
724 */
726 int variable; ///< DIMACS variable index (= gate id + 1).
727 std::string uuid; ///< Original-circuit UUID (empty if unknown).
728 double probability; ///< Probability assigned to the input gate.
729};
730
731/**
732 * @brief Map each input gate to its DIMACS variable, UUID, probability.
733 *
734 * The variable numbering matches @c TseytinCNF (and @c dDNNF::toNNF):
735 * variable = gate id + 1. Inputs are listed in gate-id order so the
736 * mapping is deterministic.
737 *
738 * @return One @c CNFInputMapping per input gate.
739 */
740std::vector<CNFInputMapping> tseytinVariableMapping() const;
741
742/**
743 * @brief Serialise the sub-circuit at @p g in d4's BC-S1.2 circuit format.
744 *
745 * Emits the Boolean circuit directly (inputs as @c "I" declarations,
746 * AND/OR gates as @c "G name := A|O …" definitions, the root as @c "T"),
747 * inlining @c NOT gates as literal sign flips. This is the input consumed by
748 * d4v2's @c --input-type @c circuit mode, letting us skip the Tseytin
749 * transform.
750 *
751 * Inputs are emitted first, so d4 (which numbers literals from 1 in
752 * first-seen order) assigns them variables 1..k in declaration order;
753 * every variable above k is an internal-gate variable. @p inputOrder is
754 * filled so that d4 variable @c v (1-based) corresponds to input gate
755 * @c inputOrder[v-1], which the d-DNNF parse-back uses to map decision
756 * literals to the right @c IN gate.
757 *
758 * Throws @c CircuitException on a gate shape BC-S1.2 cannot express
759 * (a nullary AND/OR, or a non-AND/OR/NOT/IN gate); the caller falls back
760 * to the Tseytin CNF path.
761 *
762 * @param g Root gate of the sub-circuit.
763 * @param inputOrder Output: input gate for each d4 variable (1-based).
764 * @return BC-S1.2 circuit description as a string.
765 */
766std::string BCS12(gate_t g, std::vector<gate_t> &inputOrder) const;
767
768/**
769 * @brief Parse a Panini (KCBox) DD output file into a ProvSQL d-DNNF.
770 *
771 * The @c panini-dd output parser, selected by @c compilation() for the
772 * @c panini-* records. Those records run the generic compile path (a Tseytin
773 * CNF written to the input, the record's @c argtpl run, the @c --lang carried
774 * in the template); they differ from the @c nnf compilers only in this
775 * parse-back. Panini's DD output is over the variables of our Tseytin CNF:
776 * decisions on input variables are translated to the corresponding @c IN
777 * gates; decisions on Tseytin auxiliaries are dropped (their branches are
778 * mutually exclusive over input assignments by Tseytin determinism, so the
779 * input-projection is still a sound d-DNNF). @c "R2-D2" / @c "CCDD" emit
780 * @c K (kernelize) nodes that break decomposability, so those variants are
781 * not registered and a @c K node here is an error.
782 *
783 * @param outfilename Path to Panini's DD output file.
784 * @return The compiled d-DNNF.
785 */
786dDNNF parsePaniniDD(const std::string &outfilename) const;
787
788/**
789 * @brief Boost serialisation support.
790 * @param ar Boost archive (input or output).
791 * @param version Archive version (unused).
792 */
793template<class Archive>
794void serialize (Archive & ar, [[maybe_unused]] const unsigned int version)
795{
796 ar & uuid2id;
797 ar & id2uuid;
798 ar & name_kind;
799 ar & name2id;
800 ar & id2name;
801 ar & gates;
802 ar & wires;
803 ar & inputs;
804 ar & mulinputs;
805 ar & prob;
806 ar & info;
807 ar & probabilistic;
808}
809
812};
813
814#endif /* BOOLEAN_CIRCUIT_H */
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.
Definition Circuit.h:53
Out-of-line template method implementations for Circuit<gateType>.
std::vector< double > prob
Per-gate probability (for IN gates).
virtual ~BooleanCircuit()
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).
BooleanCircuit & operator=(BooleanCircuit &&)=default
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,...
BooleanCircuit & operator=(const BooleanCircuit &)=default
bool probabilistic
true if any gate has a non-unit probability
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.
const std::set< gate_t > & getInputs() const
Return the set of input (IN) gate IDs.
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.
BooleanCircuit(const BooleanCircuit &)=default
bool hasMultivaluedGates() const
Return true if the circuit contains any MULIN gates.
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.
BooleanCircuit()
Construct an empty Boolean circuit.
void serialize(Archive &ar, const unsigned int version)
Boost serialisation support.
std::map< gate_t, unsigned > info
Per-gate integer info (for MULIN gates).
friend class boost::serialization::access
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.
bool isProbabilistic() const
Return true if any gate has a non-trivial (< 1) probability.
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.
BooleanCircuit(BooleanCircuit &&)=default
static std::string checkCompiler(std::string compiler)
std::vector< unsigned char > name_kind
Definition Circuit.h:190
BooleanGate getGateType(gate_t g) const
Definition Circuit.h:301
std::unordered_map< gate_uuid, gate_t, gate_uuid_hash > uuid2id
Definition Circuit.h:188
std::unordered_map< gate_t, std::string > id2name
Definition Circuit.h:192
std::vector< BooleanGate > gates
Definition Circuit.h:215
std::vector< gate_uuid > id2uuid
Definition Circuit.h:189
std::vector< std::vector< gate_t > > wires
Definition Circuit.h:216
std::unordered_map< std::string, gate_t > name2id
Definition Circuit.h:191
A d-DNNF circuit supporting exact probabilistic and game-theoretic evaluation.
Definition dDNNF.h:71
One row of the Tseytin variable mapping.
int variable
DIMACS variable index (= gate id + 1).
double probability
Probability assigned to the input gate.
std::string uuid
Original-circuit UUID (empty if unknown).