ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
CircuitCanonicalForm.cpp
Go to the documentation of this file.
1/**
2 * @file CircuitCanonicalForm.cpp
3 * @brief Canonical form of a Boolean circuit and its split into islands (implementation).
4 */
6
7#include <algorithm>
8#include <cassert>
9#include <limits>
10
11namespace provsql {
12
13namespace {
14
15using idx_t = size_t;
16
17unsigned typeCode(const BooleanCircuit &c, gate_t g, bool is_abstract)
18{
19 if(is_abstract)
20 return 4;
21 switch(c.getGateType(g)) {
22 case BooleanGate::AND: return 1;
23 case BooleanGate::OR: return 2;
24 case BooleanGate::NOT: return 3;
25 case BooleanGate::IN: return 4;
26 case BooleanGate::MULIN: return 5;
27 case BooleanGate::MULVAR: return 6;
28 case BooleanGate::UNDETERMINED: return 0;
29 }
30 return 0;
31}
32
33const char *typeToken(const BooleanCircuit &c, gate_t g, bool is_abstract)
34{
35 if(is_abstract)
36 return "V";
37 switch(c.getGateType(g)) {
38 case BooleanGate::AND: return "AND";
39 case BooleanGate::OR: return "OR";
40 case BooleanGate::NOT: return "NOT";
41 case BooleanGate::IN: return "V";
42 case BooleanGate::MULIN: return "MUL";
43 case BooleanGate::MULVAR: return "MULVAR";
44 case BooleanGate::UNDETERMINED: return "UNDET";
45 }
46 return "UNDET";
47}
48
49bool isLeafToken(const BooleanCircuit &c, gate_t g, bool is_abstract)
50{
51 return is_abstract || c.getGateType(g) == BooleanGate::IN;
52}
53
54}
55
57 const GateSet *abstract_leaves)
58{
59 GateSet nodes;
60 std::vector<gate_t> stack{root};
61 nodes.insert(root);
62 while(!stack.empty()) {
63 gate_t g = stack.back();
64 stack.pop_back();
65 if(g != root && abstract_leaves && abstract_leaves->count(g))
66 continue;
67 for(gate_t ch : c.getWires(g))
68 if(nodes.insert(ch).second)
69 stack.push_back(ch);
70 }
71 return nodes;
72}
73
75 const GateSet *abstract_leaves)
76{
77 auto isAbstract = [&](gate_t g) {
78 return g != root && abstract_leaves && abstract_leaves->count(g) != 0;
79 };
80 static const std::vector<gate_t> no_children;
81 auto childrenOf = [&](gate_t g) -> const std::vector<gate_t>& {
82 return isAbstract(g) ? no_children : c.getWires(g);
83 };
84
85 GateSet node_set = reachableNodes(c, root, abstract_leaves);
86
87 std::vector<gate_t> nodes(node_set.begin(), node_set.end());
88 std::unordered_map<gate_t, idx_t, CanonicalGateHash> index;
89 index.reserve(nodes.size());
90 for(idx_t i = 0; i < nodes.size(); ++i)
91 index[nodes[i]] = i;
92 const idx_t n = nodes.size();
93
94 std::vector<uint64_t> fanout(n, 0);
95 std::vector<idx_t> pending(n, 0);
96 for(idx_t i = 0; i < n; ++i) {
97 const auto &ch = childrenOf(nodes[i]);
98 pending[i] = ch.size();
99 for(gate_t u : ch)
100 ++fanout[index.at(u)];
101 }
102
103 std::vector<std::vector<idx_t> > consumers(n);
104 for(idx_t i = 0; i < n; ++i)
105 for(gate_t u : childrenOf(nodes[i]))
106 consumers[index.at(u)].push_back(i);
107
108 std::vector<uint64_t> height(n, 0);
109 std::vector<idx_t> worklist;
110 for(idx_t i = 0; i < n; ++i)
111 if(pending[i] == 0)
112 worklist.push_back(i);
113 size_t processed = 0;
114 while(processed < worklist.size()) {
115 idx_t v = worklist[processed++];
116 for(idx_t w : consumers[v]) {
117 if(height[w] < height[v] + 1)
118 height[w] = height[v] + 1;
119 if(--pending[w] == 0)
120 worklist.push_back(w);
121 }
122 }
123 assert(worklist.size() == n);
124
125 uint64_t max_height = 0;
126 for(idx_t i = 0; i < n; ++i)
127 max_height = std::max(max_height, height[i]);
128 std::vector<std::vector<idx_t> > by_height(max_height + 1);
129 for(idx_t i = 0; i < n; ++i)
130 by_height[height[i]].push_back(i);
131
132 std::vector<uint64_t> col(n, 0);
133 uint64_t colours_assigned = 0;
134 std::vector<uint64_t> sig;
135 for(uint64_t h = 0; h <= max_height; ++h) {
136 std::vector<std::pair<std::vector<uint64_t>, idx_t> > sigs;
137 sigs.reserve(by_height[h].size());
138 for(idx_t v : by_height[h]) {
139 gate_t g = nodes[v];
140 const bool abs = isAbstract(g);
141 sig.clear();
142 sig.push_back(typeCode(c, g, abs));
143 sig.push_back(fanout[v]);
144 const auto &ch = childrenOf(g);
145 const size_t list_start = sig.size();
146 for(gate_t u : ch)
147 sig.push_back(col[index.at(u)]);
148 const auto t = c.getGateType(g);
149 if(!abs && (t == BooleanGate::AND || t == BooleanGate::OR))
150 std::sort(sig.begin() + list_start, sig.end());
151 sigs.emplace_back(sig, v);
152 }
153 std::sort(sigs.begin(), sigs.end());
154 uint64_t rank = 0;
155 for(size_t k = 0; k < sigs.size(); ++k) {
156 if(k > 0 && sigs[k].first != sigs[k-1].first)
157 ++rank;
158 col[sigs[k].second] = colours_assigned + rank + 1;
159 }
160 if(!sigs.empty())
161 colours_assigned += rank + 1;
162 }
163
164 std::vector<std::vector<gate_t> > canonical_children(n);
165 for(idx_t i = 0; i < n; ++i) {
166 canonical_children[i] = childrenOf(nodes[i]);
167 const auto t = c.getGateType(nodes[i]);
168 if(!isAbstract(nodes[i]) &&
169 (t == BooleanGate::AND || t == BooleanGate::OR))
170 std::stable_sort(canonical_children[i].begin(),
171 canonical_children[i].end(),
172 [&](gate_t a, gate_t b) {
173 return col[index.at(a)] < col[index.at(b)];
174 });
175 }
176
177 CanonicalForm cf;
178 std::vector<uint64_t> number(n, 0);
179 uint64_t counter = 0;
180
181 struct Frame { idx_t v; size_t next_child; };
182 std::vector<Frame> stack;
183 std::string &out = cf.form;
184
185 auto firstVisit = [&](idx_t v) {
186 gate_t g = nodes[v];
187 const bool abs = isAbstract(g);
188 number[v] = ++counter;
189 if(isLeafToken(c, g, abs)) {
190 out += typeToken(c, g, abs);
191 cf.leaves.push_back(CanonicalLeaf{g, abs});
192 } else {
193 out += '(';
194 out += typeToken(c, g, abs);
195 stack.push_back(Frame{v, 0});
196 }
197 };
198
199 firstVisit(index.at(root));
200 while(!stack.empty()) {
201 Frame &f = stack.back();
202 const auto &ch = canonical_children[f.v];
203 if(f.next_child < ch.size()) {
204 idx_t u = index.at(ch[f.next_child++]);
205 out += ' ';
206 if(number[u] != 0) {
207 out += '#';
208 out += std::to_string(number[u]);
209 } else {
210 firstVisit(u);
211 }
212 } else {
213 out += ')';
214 stack.pop_back();
215 }
216 }
217
218 return cf;
219}
220
221std::vector<gate_t> maximalIslandRoots(const BooleanCircuit &c, gate_t root)
222{
223 GateSet node_set = reachableNodes(c, root);
224 std::vector<gate_t> nodes(node_set.begin(), node_set.end());
225 std::unordered_map<gate_t, idx_t, CanonicalGateHash> index;
226 index.reserve(nodes.size());
227 for(idx_t i = 0; i < nodes.size(); ++i)
228 index[nodes[i]] = i;
229 const idx_t n = nodes.size();
230 const idx_t root_idx = index.at(root);
231
232 if(n <= 1)
233 return {};
234
235 std::vector<std::vector<idx_t> > kids(n);
236 for(idx_t i = 0; i < n; ++i) {
237 const auto &wires = c.getWires(nodes[i]);
238 kids[i].reserve(wires.size());
239 for(gate_t u : wires)
240 kids[i].push_back(index.at(u));
241 }
242
243 std::vector<uint64_t> start(n, 0), end(n, 0), last(n, 0);
244 std::vector<bool> marked(n, false);
245 std::vector<idx_t> finished;
246 finished.reserve(n);
247 uint64_t t = 0;
248
249 struct Frame {
250 idx_t v;
251 size_t next_child;
252 };
253 std::vector<Frame> stack;
254
255 auto visit = [&](idx_t x) {
256 ++t;
257 last[x] = t;
258 if(!marked[x]) {
259 marked[x] = true;
260 start[x] = t;
261 stack.push_back(Frame{x, 0});
262 }
263 };
264
265 visit(root_idx);
266 while(!stack.empty()) {
267 const idx_t v = stack.back().v;
268 if(stack.back().next_child < kids[v].size()) {
269 const idx_t u = kids[v][stack.back().next_child++];
270 visit(u);
271 } else {
272 stack.pop_back();
273 if(!kids[v].empty()) {
274 ++t;
275 last[v] = t;
276 }
277 end[v] = t;
278 finished.push_back(v);
279 }
280 }
281 assert(finished.size() == n);
282
283 const uint64_t NO_DATE = std::numeric_limits<uint64_t>::max();
284 std::vector<uint64_t> lo(n, NO_DATE), hi(n, 0);
285 for(idx_t v : finished)
286 for(idx_t u : kids[v]) {
287 lo[v] = std::min(lo[v], std::min(start[u], lo[u]));
288 hi[v] = std::max(hi[v], std::max(last[u], hi[u]));
289 }
290
291 std::vector<bool> in_r(n, false);
292 for(idx_t v = 0; v < n; ++v) {
293 if(v == root_idx || kids[v].empty())
294 continue;
295 const auto type = c.getGateType(nodes[v]);
296 if(type != BooleanGate::AND && type != BooleanGate::OR &&
297 type != BooleanGate::NOT)
298 continue;
299 in_r[v] = start[v] < lo[v] && hi[v] < end[v];
300 }
301
302 std::vector<bool> reached(n, false);
303 std::vector<idx_t> queue{root_idx};
304 reached[root_idx] = true;
305 std::vector<gate_t> result;
306 for(size_t head = 0; head < queue.size(); ++head) {
307 const idx_t x = queue[head];
308 if(in_r[x]) {
309 result.push_back(nodes[x]);
310 continue;
311 }
312 for(idx_t u : kids[x])
313 if(!reached[u]) {
314 reached[u] = true;
315 queue.push_back(u);
316 }
317 }
318 return result;
319}
320
322{
323 IslandKey key;
324 std::vector<gate_t> frontier = maximalIslandRoots(c, root);
325 if(frontier.empty()) {
326 key.residual = computeCanonicalForm(c, root);
327 return key;
328 }
329
330 GateSet fs(frontier.begin(), frontier.end());
331 key.residual = computeCanonicalForm(c, root, &fs);
332
333 for(const CanonicalLeaf &leaf : key.residual.leaves)
334 if(leaf.is_abstract) {
335 key.island_roots.push_back(leaf.gate);
336 key.islands.push_back(computeCanonicalForm(c, leaf.gate));
337 }
338 assert(key.island_roots.size() == frontier.size());
339 return key;
340}
341
342}
@ 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).
Canonical form of a Boolean circuit, and its split into islands.
gate_t
Strongly-typed gate identifier.
Definition Circuit.h:53
Boolean circuit for provenance formula evaluation.
std::vector< gate_t > & getWires(gate_t g)
Return a mutable reference to the child-wire list of gate g.
Definition Circuit.h:311
gateType getGateType(gate_t g) const
Return the type of gate g.
Definition Circuit.h:301
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.
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.