![]() |
ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
|
Canonical form of a Boolean circuit, and its split into islands. More...
#include <cstdint>#include <string>#include <unordered_set>#include <vector>#include "BooleanCircuit.h"

Go to the source code of this file.
Classes | |
| struct | provsql::CanonicalGateHash |
Hash of a gate_t, for the containers of this module. More... | |
| struct | provsql::CanonicalLeaf |
| A leaf of a canonical form, in the order the form meets it. More... | |
| struct | provsql::CanonicalForm |
| Canonical form of a circuit below a root. More... | |
| struct | provsql::IslandKey |
| A circuit split into its outermost islands and what remains. More... | |
Namespaces | |
| namespace | provsql |
Typedefs | |
| using | provsql::GateSet = std::unordered_set<gate_t, CanonicalGateHash> |
| Set of gates of one circuit. | |
Functions | |
| GateSet | provsql::reachableNodes (const BooleanCircuit &c, gate_t root, const GateSet *abstract_leaves=nullptr) |
Gates reachable from root. | |
| CanonicalForm | provsql::computeCanonicalForm (const BooleanCircuit &c, gate_t root, const GateSet *abstract_leaves=nullptr) |
Canonical form of the circuit below root. | |
| std::vector< gate_t > | provsql::maximalIslandRoots (const BooleanCircuit &c, gate_t root) |
Roots of the outermost islands below root. | |
| IslandKey | provsql::computeIslandKey (const BooleanCircuit &c, gate_t root) |
Splits the circuit below root into its outermost islands and the residual. | |
Canonical form of a Boolean circuit, and its split into islands.
The canonical form of a circuit is a string that spells out its structure and forgets which inputs it is over: an input reads V the first time it is met and a gate met again reads #k, its rank among the nodes of the form. The children of an AND or an OR are ordered by a colour computed bottom-up from the type, the fan-out and the colours of the children, so that the order they are stored in does not matter.
Two circuits of equal form have the same structure, with the inputs of one matching those of the other in the order of CanonicalForm::leaves: a d-DNNF compiled for one evaluates the other once the probabilities are replaced. The converse does not hold: when children are tied on colour their stored order decides, so two isomorphic circuits may get different forms. For the cache of ProbCache.h this only costs a compilation.
An island is the part of the circuit below a gate that the rest of the circuit reaches only through that gate: it shares no input with the rest, so its probability can be computed on its own and the gate treated as an independent input. computeIslandKey splits a circuit into its outermost islands and the residual, the circuit with each island replaced by an input. (These are not the certified regions that the island discipline of independentEvaluation refers to.)
Definition in file CircuitCanonicalForm.h.