ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
TreeDecomposition.cpp
Go to the documentation of this file.
1/**
2 * @file TreeDecomposition.cpp
3 * @brief Tree decomposition construction, manipulation, and I/O.
4 *
5 * Implements the @c TreeDecomposition class declared in
6 * @c TreeDecomposition.h:
7 *
8 * - @c TreeDecomposition(const BooleanCircuit&): constructs the tree
9 * decomposition of the circuit's primal graph using the min-fill
10 * elimination-ordering heuristic (@c PermutationStrategy). Throws
11 * @c TreeDecompositionException if the treewidth exceeds @c MAX_TREEWIDTH.
12 * - @c TreeDecomposition(std::istream&): parses a PACE-format
13 * decomposition from a stream.
14 * - Copy constructor and copy-assignment operator.
15 * - @c makeFriendly(): restructures the tree into the friendly normal
16 * form expected by @c dDNNFTreeDecompositionBuilder.
17 * - @c toDot(): GraphViz DOT string for visualising the tree.
18 * - @c operator>>(): stream extraction in PACE format.
19 *
20 * The @c reroot() helper and @c addEmptyBag(), @c addGateToBag(),
21 * @c findGateConnection() are private utilities for tree restructuring.
22 */
23#include <cassert>
24#include <set>
25#include <algorithm>
26#include <set>
27#include <string>
28#include <type_traits>
29#include <unordered_map>
30#include <unordered_set>
31#include <vector>
32
33#include "TreeDecomposition.h"
34#include "BooleanCircuit.h"
35#include "Graph.h"
36#include "PermutationStrategy.h"
38
39/* The min-fill elimination loop below can grind for tens of seconds
40 * on circuits whose treewidth approaches MAX_TREEWIDTH ; without
41 * periodic CHECK_FOR_INTERRUPTS the backend ignores both
42 * statement_timeout and pg_cancel_backend. Guard pattern mirrors
43 * BooleanCircuit.cpp's : in the standalone tdkc binary the macro
44 * resolves to a no-op. */
45#ifdef TDKC
46// In tdkc the hot-loop interrupt check services any active KCMCP session
47// (PONG / PROGRESS) and aborts the build on CANCEL or a timeout; a no-op in
48// the plain command-line mode.
49#include "tdkc_interrupt.h"
50#define CHECK_FOR_INTERRUPTS() provsql_tdkc_poll()
51#else
52extern "C" {
53#include "postgres.h"
54#include "miscadmin.h"
55}
56#endif
57
58/* Interrupt check for the C++ loops that must unwind by throwing (their
59 * vectors freed), not by the longjmp of CHECK_FOR_INTERRUPTS. */
60#ifdef TDKC
61static inline void poll_interrupt() { provsql_tdkc_poll(); }
62#else
63#include "provsql_interrupt.h"
64static inline void poll_interrupt() { provsql_poll_interrupt(); }
65#endif
66
68 unsigned &max_degree)
69{
70 /* The graph of Graph(bc), in arrays: hash-based adjacency sets cost
71 * seconds and gigabytes on a circuit of millions of gates (that of a
72 * recursion on cyclic data, for one), which this proxy is meant to be
73 * cheap on. Nodes are the gates other than UNDETERMINED / MULVAR, plus
74 * the targets of their wires; edges are the wires, undirected, without
75 * repetition. */
76 const std::size_t n = bc.getNbGates();
77 std::vector<char> is_node(n, 0);
78 std::vector<std::pair<unsigned, unsigned> > arcs;
79 for(gate_t g1{0}; g1 < n; ++g1) {
80 if((static_cast<std::size_t>(g1) & 65535) == 0)
84 continue;
85 const unsigned u = static_cast<unsigned>(g1);
86 is_node[u] = 1;
87 for(auto g2 : bc.getWires(g1)) {
88 const unsigned v = static_cast<unsigned>(g2);
89 is_node[v] = 1;
90 if(u != v) {
91 arcs.emplace_back(u, v);
92 arcs.emplace_back(v, u);
93 }
94 }
95 }
96 std::sort(arcs.begin(), arcs.end());
97 arcs.erase(std::unique(arcs.begin(), arcs.end()), arcs.end());
99
100 // Compressed adjacency: the neighbours of u are adj[start[u] .. start[u+1]).
101 std::vector<std::size_t> start(n + 1, 0);
102 for(const auto &a : arcs)
103 ++start[a.first + 1];
104 for(std::size_t u = 0; u < n; ++u)
105 start[u + 1] += start[u];
106 std::vector<unsigned> adj(arcs.size());
107 for(std::size_t k = 0; k < arcs.size(); ++k)
108 adj[k] = arcs[k].second;
109 std::vector<std::pair<unsigned, unsigned> >().swap(arcs);
110
111 // Batagelj-Zaversnik peel, O(V+E): vertices sorted by degree in vert,
112 // bin[d] the position of the first of degree d; removing a minimum-degree
113 // vertex moves each remaining neighbour one bin down. The degeneracy is
114 // the largest degree a vertex has at its removal.
115 std::vector<unsigned> deg(n, 0);
116 unsigned max_deg = 0;
117 for(std::size_t u = 0; u < n; ++u)
118 if(is_node[u]) {
119 deg[u] = static_cast<unsigned>(start[u + 1] - start[u]);
120 max_deg = std::max(max_deg, deg[u]);
121 }
122 max_degree = max_deg;
123 std::vector<std::size_t> bin(max_deg + 2, 0);
124 std::size_t nb_nodes = 0;
125 for(std::size_t u = 0; u < n; ++u)
126 if(is_node[u]) {
127 ++bin[deg[u] + 1];
128 ++nb_nodes;
129 }
130 if(nb_nodes == 0)
131 return 0;
132 for(unsigned d = 0; d <= max_deg; ++d)
133 bin[d + 1] += bin[d];
134 std::vector<unsigned> vert(nb_nodes);
135 std::vector<std::size_t> pos(n, 0);
136 {
137 std::vector<std::size_t> next(bin.begin(), bin.end() - 1);
138 for(std::size_t u = 0; u < n; ++u)
139 if(is_node[u]) {
140 pos[u] = next[deg[u]]++;
141 vert[pos[u]] = static_cast<unsigned>(u);
142 }
143 }
144 unsigned degeneracy = 0;
145 for(std::size_t i = 0; i < nb_nodes; ++i) {
146 if((i & 65535) == 0)
148 const unsigned v = vert[i];
149 degeneracy = std::max(degeneracy, deg[v]);
150 for(std::size_t k = start[v]; k < start[v + 1]; ++k) {
151 const unsigned u = adj[k];
152 if(deg[u] > deg[v]) {
153 // Swap u with the first vertex of its bin, then shrink the bin.
154 const unsigned du = deg[u];
155 const std::size_t pu = pos[u], pw = bin[du];
156 const unsigned w = vert[pw];
157 if(u != w) {
158 vert[pu] = w; pos[w] = pu;
159 vert[pw] = u; pos[u] = pw;
160 }
161 ++bin[du];
162 --deg[u];
163 }
164 }
165 }
166 return degeneracy;
167}
168
170 unsigned &max_degree)
171{
172 max_degree = 0;
173 const auto &nodes = graph.get_nodes();
174 if(nodes.empty())
175 return 0;
176
177 // Initial degrees and degree buckets. An isolated node (a disconnected
178 // constant/gate) has no adjacency entry -- get_neighbours would dereference a
179 // missing key -- so guard with has_neighbours and treat it as degree 0.
180 std::unordered_map<unsigned long, unsigned> deg;
181 deg.reserve(nodes.size());
182 unsigned max_deg = 0;
183 for(unsigned long n : nodes) {
184 unsigned d = graph.has_neighbours(n)
185 ? static_cast<unsigned>(graph.get_neighbours(n).size()) : 0;
186 deg[n] = d;
187 max_deg = std::max(max_deg, d);
188 }
189 max_degree = max_deg;
190 // Ordered buckets so the min-degree peel below picks the smallest-id node
191 // deterministically. The k-core degeneracy is a graph invariant (independent
192 // of the tie-break), but an unordered_set's begin() is an arbitrary element,
193 // which is a non-determinism smell -- a std::set makes the whole pass provably
194 // deterministic for the price of log-time bucket ops (degeneracy is only a
195 // cheap proxy, so this is negligible).
196 std::vector<std::set<unsigned long> > bucket(max_deg + 1);
197 for(const auto &kv : deg)
198 bucket[kv.second].insert(kv.first);
199
200 // Matula-Beck peel: repeatedly remove a minimum-degree node; the degeneracy
201 // is the largest degree a node has at its own removal. The graph itself is
202 // not mutated -- removed nodes are tracked in a set and skipped -- so
203 // get_neighbours stays the original adjacency. O(V+E).
204 unsigned degeneracy = 0;
205 std::unordered_set<unsigned long> removed;
206 removed.reserve(nodes.size());
207 unsigned scan = 0;
208 const size_t n_nodes = nodes.size();
209 for(size_t processed = 0; processed < n_nodes; ++processed) {
210 while(scan <= max_deg && bucket[scan].empty())
211 ++scan;
212 if(scan > max_deg)
213 break;
214 unsigned long v = *bucket[scan].begin();
215 bucket[scan].erase(bucket[scan].begin());
216 degeneracy = std::max(degeneracy, scan);
217 removed.insert(v);
218 if(graph.has_neighbours(v)) {
219 for(unsigned long u : graph.get_neighbours(v)) {
220 if(removed.find(u) != removed.end())
221 continue;
222 unsigned d = deg[u];
223 bucket[d].erase(u);
224 deg[u] = d - 1;
225 bucket[d - 1].insert(u);
226 if(d - 1 < scan)
227 scan = d - 1;
228 }
229 }
230 CHECK_FOR_INTERRUPTS();
231 }
232 return degeneracy;
233}
234
236{
237 in >> *this;
238}
239
240// This utility function looks for an existing bag to attach a new bag
241// that contains a single gate v
243{
244 for(bag_t i{0}; i<bags.size(); ++i)
245 for(auto g: getBag(i)) {
246 if(g == v)
247 return i;
248 }
249
250 return root;
251}
252
253// Transform a tree decomposition into one that is root-friendly for a
254// given node root, as per the definition page 6 of
255// https://doi.org/10.1007/s00224-019-09930-2 ; the transformation implemented is
256// described in Lemma 2.2 of that paper. The only difference is that we
257// do not enforce the tree to be full, as this is not required for
258// correctness; and we do not make it binary but n-ary for a small n, as
259// it is more efficient.
261 // Look for a bag root_connection to attach to the new root
262 auto root_connection = findGateConnection(v);
263
264 // Create the new root and attach it to this root_connection
265 auto new_root = addEmptyBag(root_connection);
266 addGateToBag(v, new_root);
267 reroot(new_root);
268
269 // Make the tree n-ary for a small n
270 auto nb_bags = bags.size();
271 for(bag_t i{0}; i<nb_bags; ++i) {
272 if(getChildren(i).size()<=OPTIMAL_ARITY)
273 continue;
274
275 auto current = i;
276 auto copy_children=getChildren(i);
277 for(int j=copy_children.size()-OPTIMAL_ARITY-1; j>=0; j-=OPTIMAL_ARITY-1) {
278 decltype(copy_children) new_children;
279 new_children.push_back(current);
280 for(auto k{j}; k>=0 && k>j-OPTIMAL_ARITY; --k)
281 new_children.push_back(copy_children[k]);
282 current = addEmptyBag(getParent(current), new_children);
283 for(auto g: getBag(i))
284 addGateToBag(g, current);
285 }
286 }
287
288 // Transform leaves into paths that introduce gates one at a time
289 nb_bags = bags.size();
290 for(bag_t i{0}; i<nb_bags; ++i) {
291 if(getChildren(i).empty()) {
292 auto p = i;
293 for(size_t j = 1; j < getBag(i).size(); ++j) {
294 p = addEmptyBag(p);
296 for(size_t k = 0; k < getBag(i).size() - j; ++k, ++it)
297 addGateToBag(*it, p);
298 }
299 }
300 }
301
302 // Construct for each bag the union of gates in its children
303 std::vector<std::set<gate_t>> gates_in_children(bags.size());
304 auto getChildrenGates = [&gates_in_children](bag_t i) -> auto& {
305 return gates_in_children[static_cast<std::underlying_type<bag_t>::type>(i)];
306 };
307
308 for(bag_t i{0}; i<bags.size(); ++i) {
309 if(i!=root) {
310 for(auto g: getBag(i))
311 getChildrenGates(getParent(i)).insert(g);
312 }
313 }
314
315 // For every gate that is in an internal bag but not in the union of
316 // its children, construct a subtree introducing these gates one at a
317 // time
318 nb_bags = bags.size();
319 for(bag_t i{0}; i<nb_bags; ++i) {
320 if(!getChildren(i).empty()) {
321 Bag intersection;
322 std::vector<gate_t> extra_gates;
323 for(auto g: getBag(i)) {
324 if(getChildrenGates(i).find(g) == getChildrenGates(i).end())
325 extra_gates.push_back(g);
326 else
327 intersection.insert(g);
328 }
329
330 if(!extra_gates.empty()) {
331 getBag(i) = intersection;
332
333 if(getChildren(i).size()==1 && intersection.size()==getChildrenGates(i).size()) {
334 // We can skip one level, to avoid creating a node identical to
335 // the single child
336
337 auto new_bag = addEmptyBag(i);
338 auto gate = extra_gates.back();
339 addGateToBag(gate, new_bag);
340 addGateToBag(gate, i);
341 extra_gates.pop_back();
342 }
343
344 auto b = i;
345 for(auto g: extra_gates) {
346 auto id = addEmptyBag(getParent(b), {b});
347 getBag(id) = getBag(b);
348 addGateToBag(g, id);
349
350 auto single_gate_bag = addEmptyBag(id);
351 addGateToBag(g, single_gate_bag);
352
353 b = id;
354 }
355 }
356 }
357 }
358}
359
361 const std::vector<bag_t> &ch)
362{
363 bag_t id {bags.size()};
364 bags.push_back(Bag());
365 parent.push_back(p);
366 getChildren(p).push_back(id);
367 children.push_back(ch);
368
369 for(auto c: ch) {
370 if(c!=root)
371 getChildren(getParent(c)).erase(std::find(getChildren(getParent(c)).begin(),
372 getChildren(getParent(c)).end(),
373 c));
374 setParent(c,id);
375 }
376
377 return id;
378}
379
384
386{
387 if(bag == root)
388 return;
389
390 for(bag_t b = bag, p = getParent(b), gp; b != root; b = p, p = gp) {
391 gp = getParent(p);
392 setParent(p, b);
393 if(p!=root)
394 getChildren(gp).erase(std::find(getChildren(gp).begin(),
395 getChildren(gp).end(),
396 p));
397 getChildren(b).push_back(p);
398 }
399
400 getChildren(getParent(bag)).erase(std::find(getChildren(getParent(bag)).begin(),
401 getChildren(getParent(bag)).end(),
402 bag));
403 setParent(bag, bag);
404 root = bag;
405}
406
407std::string TreeDecomposition::toDot() const
408{
409 std::string result="digraph circuit{\n graph [rankdir=UD] ;\n";
410
411 for(bag_t i{0}; i < bags.size(); ++i)
412 {
413 result += " " + to_string(i) + " [label=\"{";
414 bool first=true;
415 for(auto gate: getBag(i)) {
416 if(!first)
417 result+=",";
418 else
419 first=false;
420 result += to_string(gate);
421 }
422 result += "}\"];\n";
423
424 if(i!=root)
425 result+=" " + to_string(getParent(i)) + " -> " + to_string(i) + ";\n";
426 }
427
428 result += "}\n";
429
430 return result;
431}
432
433std::istream& operator>>(std::istream& in, TreeDecomposition &td)
434{
435 in >> td.treewidth;
437
438 unsigned long nb_bags;
439 in >> nb_bags;
440
441 td.bags.resize(nb_bags);
442 td.parent.resize(nb_bags);
443 td.children.resize(nb_bags);
444
445 for(bag_t i{0}; i<nb_bags; ++i) {
446 bag_t id_bag;
447 in >> id_bag;
448
449 assert(i==id_bag);
450
451 unsigned nb_gates;
452 in >> nb_gates;
453
454 assert(nb_gates <= td.treewidth+1);
455
456 for(unsigned long j=0; j<nb_gates; ++j) {
457 gate_t g;
458 in >> g;
459
460 td.addGateToBag(g, i);
461 }
462
464 in >> parent;
465 td.setParent(i, parent);
466 if(parent == i)
467 td.root = i;
468 else
469 td.getChildren(parent).push_back(i);
470
471 unsigned long nb_children;
472 in >> nb_children;
473
474 for(unsigned long j=0; j<nb_children; ++j) {
475 unsigned long child;
476 in >> child;
477
478 // Ignored, we used the parent link instead
479 }
480 }
481
482 return in;
483}
484
486 unsigned max_width)
487 : TreeDecomposition(Graph(bc), nullptr, max_width)
488{
489}
490
491// Taken and adapted from https://github.com/smaniu/treewidth
493 Graph graph, std::unordered_map<unsigned long, bag_t> *elimination_bag,
494 unsigned width_cap)
495{
496 width_cap = std::min<unsigned>(width_cap, MAX_TREEWIDTH);
497 PermutationStrategy strategy;
498
499 strategy.init_permutation(graph);
500
501 // Upper bound on size of the bags vector to avoid redimensioning
502 bags.reserve(graph.number_nodes());
503
504 unsigned max_width{0};
505 std::unordered_map<gate_t, bag_t> bag_ids;
506 bag_t bag_id{0};
507
508 //looping greedily through the permutation
509 //we stop when the maximum bag has the same width as the remaining graph
510 //or when we achive the partial decomposition condition
511 while(max_width<graph.number_nodes() && !strategy.empty()){
512 /* Yield to the postgres backend ; the min-fill elimination loop
513 * dominates the runtime of the tree-decomposition construction
514 * on circuits near MAX_TREEWIDTH, so per-iteration cancellation
515 * is the right granularity. */
516 CHECK_FOR_INTERRUPTS();
517 //getting the next node
518 unsigned long node = strategy.get_next();
519 //removing the node from the graph and getting its neighbours
520 std::unordered_set<unsigned long> neigh = graph.remove_node(node);
521 max_width = std::max<unsigned>(neigh.size(), max_width);
522 //we stop as soon as we find bag that is too wide
523 if(max_width>width_cap)
525
526 //filling missing edges between the neighbours and recomputing statistics
527 // for relevant nodes in the graph (the neighbours, most of the time)
528 graph.fill(neigh);
529 strategy.recompute(neigh, graph);
530
531 Bag bag;
532 for(auto n: neigh) {
533 bag.insert(gate_t{n});
534 }
535 bag.insert(gate_t{node});
536
537 if(elimination_bag)
538 (*elimination_bag)[node] = bag_id;
539 bag_ids[gate_t{node}] = bag_id++;
540
541 bags.push_back(bag);
542 }
543
544 if(graph.get_nodes().size()>width_cap)
546
547 if(graph.number_nodes()>0) {
548 Bag remaining_bag;
549 for(auto n: graph.get_nodes()) {
550 remaining_bag.insert(gate_t{n});
551 if(elimination_bag)
552 (*elimination_bag)[n] = bag_t{bags.size()};
553 }
554 bags.push_back(remaining_bag);
555 }
556
557 parent.resize(bags.size());
558 children.resize(bags.size());
559
560 if(graph.number_nodes()==0)
561 treewidth=max_width;
562 else
563 treewidth = std::max<unsigned>(max_width,graph.number_nodes()-1);
564
565 for(bag_t i{0};i<bags.size()-1;++i){
566 bag_t min_bag{bags.size()-1};
567 for(auto n: getBag(i)) {
568 auto it = bag_ids.find(n);
569 if(it!=bag_ids.end() && it->second!=i)
570 min_bag = std::min(it->second, min_bag);
571 }
572 setParent(i, min_bag);
573 getChildren(min_bag).push_back(i);
574 }
575
576 // Special semantics: a node is its own parent if it is the root
577 root = bag_t{bags.size()-1};
579}
Boolean provenance circuit with support for knowledge compilation.
@ MULVAR
Auxiliary gate grouping all MULIN siblings.
@ UNDETERMINED
Placeholder gate whose type has not been set yet.
gate_t
Strongly-typed gate identifier.
Definition Circuit.h:53
Undirected graph used in tree-decomposition computations.
Priority-queue-based node-elimination ordering for tree decomposition.
static void poll_interrupt()
std::istream & operator>>(std::istream &in, TreeDecomposition &td)
Read a tree decomposition in PACE challenge format.
Tree decomposition of a Boolean circuit for knowledge compilation.
std::string to_string(bag_t b)
Convert a bag_t to its decimal string representation.
bag_t
Strongly-typed bag identifier for a tree decomposition.
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
std::vector< gate_t >::size_type getNbGates() const
Return the total number of gates in the circuit.
Definition Circuit.h:252
Mutable adjacency-list graph over unsigned-long node IDs.
Definition Graph.h:33
void fill(const std::unordered_set< unsigned long > &nodes, bool undirected=true)
Add all missing edges within nodes (clique fill).
Definition Graph.h:155
const std::unordered_set< unsigned long > & get_nodes() const
Return the set of all node IDs in the graph.
Definition Graph.h:235
bool has_neighbours(unsigned long node) const
Return true if node has any adjacent edges.
Definition Graph.h:189
std::unordered_set< unsigned long > remove_node(unsigned long node)
Remove node and all its incident edges.
Definition Graph.h:99
const std::unordered_set< unsigned long > & get_neighbours(unsigned long node) const
Return the neighbour set of node.
Definition Graph.h:225
unsigned long number_nodes() const
Return the number of nodes in the graph.
Definition Graph.h:243
Node-elimination ordering strategy using a priority queue.
unsigned long get_next()
Pop and return the node with the smallest statistic.
virtual void recompute(const std::unordered_set< unsigned long > &nodes, Graph &graph)
Recompute statistics for a subset of nodes and update the queue.
bool empty()
Return true if the queue is empty.
void init_permutation(Graph &graph)
Populate the priority queue with all nodes in graph.
Exception thrown when a tree decomposition cannot be constructed.
bag_t findGateConnection(gate_t v) const
Find the bag whose gate set is closest to gate v (for rooting).
bag_t addEmptyBag(bag_t parent, const std::vector< bag_t > &children=std::vector< bag_t >())
Insert a new empty bag as a child of parent.
std::vector< Bag > bags
Bag contents, indexed by bag_t.
void addGateToBag(gate_t g, bag_t b)
Add gate g to the contents of bag b.
static unsigned degeneracyLowerBound(const BooleanCircuit &bc, unsigned &max_degree)
Cheap degeneracy lower bound on the treewidth of bc's primal graph.
flat_set< gate_t, small_vector > Bag
The type of a bag: a small flat set of gate IDs.
void setParent(bag_t b, bag_t p)
Set the parent of bag b to p.
TreeDecomposition()=default
std::string toDot() const
Render the tree decomposition as a GraphViz DOT string.
void reroot(bag_t bag)
Re-root the tree so that bag becomes the root.
static constexpr int OPTIMAL_ARITY
Preferred maximum arity of bags in the friendly form.
std::vector< bag_t > parent
Parent of each bag (root points to itself).
unsigned treewidth
Treewidth of the decomposition.
bag_t getParent(bag_t b) const
Return the parent of bag b.
static constexpr int MAX_TREEWIDTH
Maximum supported treewidth.
std::vector< std::vector< bag_t > > children
Children of each bag.
bag_t root
Identifier of the root bag.
Bag & getBag(bag_t b)
Mutable access to bag b.
void makeFriendly(gate_t root)
Restructure the tree into the friendly normal form.
std::vector< bag_t > & getChildren(bag_t b)
Mutable access to the children of bag b.
Constructs a d-DNNF from a Boolean circuit and its tree decomposition.
void provsql_tdkc_poll()
Cancellation of the long C++ evaluation loops.
void provsql_poll_interrupt()
Throw where an evaluation is to stop, its query cancelled.
decltype(std::begin(std::declval< const storage_t & >())) const_iterator
Definition flat_set.hpp:47
iterator begin()
Return iterator to the first element.
Definition flat_set.hpp:51
size_t size() const
Return the number of elements in the set.
Definition flat_set.hpp:81
void insert(const K &value)
Insert value if not already present (const-ref overload).
Definition flat_set.hpp:129
Build-loop interrupt hook for the standalone tdkc binary.