ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
CircuitCanonicalForm.h
Go to the documentation of this file.
1/**
2 * @file CircuitCanonicalForm.h
3 * @brief Canonical form of a Boolean circuit, and its split into islands.
4 *
5 * The canonical form of a circuit is a string that spells out its
6 * structure and forgets which inputs it is over: an input reads @c V the
7 * first time it is met and a gate met again reads @c \#k, its rank among
8 * the nodes of the form. The children of an AND or an OR are ordered by
9 * a colour computed bottom-up from the type, the fan-out and the colours
10 * of the children, so that the order they are stored in does not matter.
11 *
12 * Two circuits of equal form have the same structure, with the inputs of
13 * one matching those of the other in the order of
14 * @c CanonicalForm::leaves: a d-DNNF compiled for one evaluates the other
15 * once the probabilities are replaced. The converse does not hold: when
16 * children are tied on colour their stored order decides, so two
17 * isomorphic circuits may get different forms. For the cache of
18 * @c ProbCache.h this only costs a compilation.
19 *
20 * An *island* is the part of the circuit below a gate that the rest of
21 * the circuit reaches only through that gate: it shares no input with
22 * the rest, so its probability can be computed on its own and the gate
23 * treated as an independent input. @c computeIslandKey splits a circuit
24 * into its outermost islands and the *residual*, the circuit with each
25 * island replaced by an input. (These are not the certified regions
26 * that the island discipline of @c independentEvaluation refers to.)
27 */
28#ifndef CIRCUIT_CANONICAL_FORM_H
29#define CIRCUIT_CANONICAL_FORM_H
30
31#include <cstdint>
32#include <string>
33#include <unordered_set>
34#include <vector>
35
36#include "BooleanCircuit.h"
37
38namespace provsql {
39
40/// Hash of a @c gate_t, for the containers of this module.
42 size_t operator()(gate_t g) const {
43 return std::hash<typename std::underlying_type<gate_t>::type>()(
44 static_cast<typename std::underlying_type<gate_t>::type>(g));
45 }
46};
47
48/// Set of gates of one circuit.
49using GateSet = std::unordered_set<gate_t, CanonicalGateHash>;
50
51/// A leaf of a canonical form, in the order the form meets it.
53 gate_t gate; ///< The gate of the circuit this leaf stands for
54 bool is_abstract; ///< Whether it is an island root read as an input
55};
56
57/// Canonical form of a circuit below a root.
59 std::string form; ///< The form, e.g. `(OR (AND V V) (AND V #4))`
60 std::vector<CanonicalLeaf> leaves; ///< The leaves, in the order of their @c V in @c form
61};
62
63/**
64 * @brief Gates reachable from @p root.
65 * @param c The circuit.
66 * @param root Gate to start from.
67 * @param abstract_leaves Gates not to go below (other than @p root); they
68 * are part of the result.
69 */
71 const GateSet *abstract_leaves = nullptr);
72
73/**
74 * @brief Canonical form of the circuit below @p root.
75 * @param c The circuit.
76 * @param root Root of the form.
77 * @param abstract_leaves Gates read as inputs, whatever is below them.
78 *
79 * Iterative, so that a circuit as deep as the data does not exhaust the
80 * stack.
81 */
83 const GateSet *abstract_leaves = nullptr);
84
85/**
86 * @brief Roots of the outermost islands below @p root.
87 *
88 * An AND, OR or NOT gate other than @p root is an island root when no
89 * gate below it is reached from @p root by a path avoiding it. Only the
90 * outermost ones are returned, those not inside another island. One
91 * depth-first traversal, linear in the size of the circuit.
92 */
93std::vector<gate_t> maximalIslandRoots(const BooleanCircuit &c, gate_t root);
94
95/// A circuit split into its outermost islands and what remains.
96struct IslandKey {
97 CanonicalForm residual; ///< Form of the circuit, each island read as an input
98 std::vector<gate_t> island_roots; ///< Island roots, in the order of the residual's leaves
99 std::vector<CanonicalForm> islands; ///< Form of each island, in the same order
100};
101
102/// Splits the circuit below @p root into its outermost islands and the residual.
104
105}
106
107#endif
Boolean provenance circuit with support for knowledge compilation.
gate_t
Strongly-typed gate identifier.
Definition Circuit.h:53
Boolean circuit for provenance formula evaluation.
GateSet reachableNodes(const BooleanCircuit &c, gate_t root, const GateSet *abstract_leaves)
Gates reachable from root.
std::vector< gate_t > maximalIslandRoots(const BooleanCircuit &c, gate_t root)
Roots of the outermost islands below root.
IslandKey computeIslandKey(const BooleanCircuit &c, gate_t root)
Splits the circuit below root into its outermost islands and the residual.
CanonicalForm computeCanonicalForm(const BooleanCircuit &c, gate_t root, const GateSet *abstract_leaves)
Canonical form of the circuit below root.
std::unordered_set< gate_t, CanonicalGateHash > GateSet
Set of gates of one circuit.
Canonical form of a circuit below a root.
std::string form
The form, e.g. (OR (AND V V) (AND V #4)).
std::vector< CanonicalLeaf > leaves
The leaves, in the order of their V in form.
Hash of a gate_t, for the containers of this module.
size_t operator()(gate_t g) const
A leaf of a canonical form, in the order the form meets it.
bool is_abstract
Whether it is an island root read as an input.
gate_t gate
The gate of the circuit this leaf stands for.
A circuit split into its outermost islands and what remains.
std::vector< gate_t > island_roots
Island roots, in the order of the residual's leaves.
CanonicalForm residual
Form of the circuit, each island read as an input.
std::vector< CanonicalForm > islands
Form of each island, in the same order.