ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
TreeDecomposition.h
Go to the documentation of this file.
1/**
2 * @file TreeDecomposition.h
3 * @brief Tree decomposition of a Boolean circuit for knowledge compilation.
4 *
5 * A **tree decomposition** of a graph @f$G=(V,E)@f$ is a tree @f$T@f$
6 * whose nodes are labelled with *bags* (subsets of @f$V@f$) such that:
7 * 1. Every vertex of @f$G@f$ appears in at least one bag.
8 * 2. For every edge @f$(u,v)\in E@f$, some bag contains both @f$u@f$
9 * and @f$v@f$.
10 * 3. For every vertex @f$v@f$, the bags containing @f$v@f$ form a
11 * connected sub-tree of @f$T@f$.
12 *
13 * The **treewidth** is one less than the maximum bag size. ProvSQL
14 * builds a tree decomposition of the primal graph of a @c BooleanCircuit
15 * (using the min-fill elimination heuristic via @c PermutationStrategy)
16 * and then feeds it to @c dDNNFTreeDecompositionBuilder to construct a
17 * d-DNNF. Tractable compilation is guaranteed when the treewidth is
18 * bounded (empirically ≤ @c MAX_TREEWIDTH).
19 *
20 * The decomposition can also be read from an external file in the
21 * standard PACE challenge format (via the streaming @c operator>>).
22 *
23 * @c bag_t is a strongly-typed wrapper around @c size_t, analogous to
24 * @c gate_t, used as a bag identifier within the tree.
25 */
26#ifndef TREE_DECOMPOSITION_H
27#define TREE_DECOMPOSITION_H
28
29#include <iostream>
30#include <string>
31#include <type_traits>
32#include <vector>
33#include <boost/container/static_vector.hpp>
34
35#include "flat_set.hpp"
36#include "BooleanCircuit.h"
37#include "Graph.h"
38
39// Forward declaration for friend
41
42/**
43 * @brief Strongly-typed bag identifier for a tree decomposition.
44 *
45 * Wraps a @c size_t, analogous to @c gate_t.
46 */
47enum class bag_t : size_t {};
48
49/**
50 * @brief Tree decomposition of a Boolean circuit's primal graph.
51 *
52 * Provides constructors that compute the decomposition from a
53 * @c BooleanCircuit using the min-fill heuristic, or parse it from an
54 * input stream. After construction, @c makeFriendly() restructures the
55 * tree into the "friendly" normal form required by
56 * @c dDNNFTreeDecompositionBuilder.
57 */
59public:
60/** @brief Maximum supported treewidth. Circuits exceeding this cause an error. */
61static constexpr int MAX_TREEWIDTH = 10;
62/** @brief Preferred maximum arity of bags in the friendly form. */
63static constexpr int OPTIMAL_ARITY = 2;
64
65/**
66 * @brief Stack-allocated vector type bounded by @c MAX_TREEWIDTH+1 elements.
67 *
68 * Used for bag contents to avoid heap allocation for small, bounded sets.
69 */
70template<class T>
71using small_vector = boost::container::static_vector<T, MAX_TREEWIDTH+1>;
72
73/** @brief The type of a bag: a small flat set of gate IDs. */
75
76private:
77std::vector<Bag> bags; ///< Bag contents, indexed by @c bag_t
78std::vector<bag_t> parent; ///< Parent of each bag (root points to itself)
79std::vector<std::vector<bag_t> > children; ///< Children of each bag
80bag_t root; ///< Identifier of the root bag
81unsigned treewidth; ///< Treewidth of the decomposition
82
84
85/**
86 * @brief Find the bag whose gate set is closest to gate @p v (for rooting).
87 * @param v Gate to search for.
88 * @return ID of the bag that contains or is nearest to @p v.
89 */
91/**
92 * @brief Re-root the tree so that @p bag becomes the root.
93 * @param bag The bag to use as the new root.
94 */
95void reroot(bag_t bag);
96/**
97 * @brief Insert a new empty bag as a child of @p parent.
98 * @param parent Parent bag of the new empty bag.
99 * @param children Children to transfer from @p parent to the new bag.
100 * @return ID of the newly created bag.
101 */
102bag_t addEmptyBag(bag_t parent, const std::vector<bag_t> &children = std::vector<bag_t>());
103/**
104 * @brief Add gate @p g to the contents of bag @p b.
105 * @param g Gate to add.
106 * @param b Destination bag.
107 */
108void addGateToBag(gate_t g, bag_t b);
109
110/**
111 * @brief Mutable access to bag @p b.
112 * @param b Bag identifier.
113 * @return Reference to the bag's gate set.
114 */
116{
117 return bags[static_cast<std::underlying_type<bag_t>::type>(b)];
118}
119/**
120 * @brief Mutable access to the children of bag @p b.
121 * @param b Bag identifier.
122 * @return Reference to the vector of child bag IDs.
123 */
124std::vector<bag_t> &getChildren(bag_t b)
125{
126 return children[static_cast<std::underlying_type<bag_t>::type>(b)];
127}
128/**
129 * @brief Set the parent of bag @p b to @p p.
130 * @param b Bag whose parent is to be set.
131 * @param p New parent bag.
132 */
134{
135 parent[static_cast<std::underlying_type<bag_t>::type>(b)]=p;
136}
137
138public:
139/**
140 * @brief Compute a tree decomposition of the primal graph of @p bc.
141 *
142 * Uses the min-fill elimination ordering heuristic. Throws
143 * @c TreeDecompositionException if the computed treewidth exceeds
144 * @c MAX_TREEWIDTH.
145 *
146 * @param bc The Boolean circuit to decompose.
147 * @param max_width Width past which the construction stops, throwing
148 * @c TreeDecompositionException; at most
149 * @c MAX_TREEWIDTH (a caller bounding its cost passes a
150 * smaller one, to stop as soon as it is exceeded).
151 */
153 unsigned max_width = MAX_TREEWIDTH);
154
155/**
156 * @brief Compute a tree decomposition of an arbitrary undirected graph.
157 *
158 * Same min-fill elimination ordering heuristic as the
159 * @c BooleanCircuit constructor (which delegates here), but over a
160 * caller-supplied @c Graph -- e.g. the Gaifman graph of a relational
161 * instance, when exploiting bounded-treewidth *data* rather than a
162 * bounded-treewidth circuit. Bag elements are then the graph's node
163 * IDs (wrapped in @c gate_t). Throws @c TreeDecompositionException
164 * if the computed treewidth exceeds @c MAX_TREEWIDTH.
165 *
166 * @param graph The graph to decompose (consumed: the
167 * elimination process empties it).
168 * @param elimination_bag If non-null, receives for every node the bag
169 * created when that node was eliminated (nodes
170 * remaining after the elimination loop map to
171 * the final root bag). By the elimination
172 * invariant, for every edge @c (u,v) of the
173 * graph the earlier-eliminated endpoint's bag
174 * contains both @c u and @c v, which gives a
175 * constant-time edge-to-bag assignment.
176 * @param max_width As for the @c BooleanCircuit constructor.
177 */
179 std::unordered_map<unsigned long, bag_t> *elimination_bag = nullptr,
180 unsigned max_width = MAX_TREEWIDTH);
181
182/**
183 * @brief Const access to bag @p b.
184 * @param b Bag identifier.
185 * @return Const reference to the bag's gate set.
186 */
187const Bag &getBag(bag_t b) const
188{
189 return bags[static_cast<std::underlying_type<bag_t>::type>(b)];
190}
191/**
192 * @brief Const access to the children of bag @p b.
193 * @param b Bag identifier.
194 * @return Const reference to the vector of child bag IDs.
195 */
196const std::vector<bag_t> &getChildren(bag_t b) const
197{
198 return children[static_cast<std::underlying_type<bag_t>::type>(b)];
199}
200/**
201 * @brief Return the parent of bag @p b.
202 * @param b Bag identifier.
203 * @return Parent bag identifier.
204 */
206{
207 return parent[static_cast<std::underlying_type<bag_t>::type>(b)];
208}
209/**
210 * @brief Return the root bag of the decomposition.
211 * @return Root bag identifier.
212 */
214{
215 return root;
216}
217/**
218 * @brief Return the number of bags in the decomposition.
219 * @return Bag count.
220 */
221std::size_t getNbBags() const
222{
223 return bags.size();
224}
225
226/**
227 * @brief Parse a tree decomposition from a stream (PACE challenge format).
228 *
229 * @param in Input stream containing the decomposition.
230 */
231TreeDecomposition(std::istream &in);
232
233/** @brief Copy constructor. @param td Source decomposition. */
235/**
236 * @brief Copy assignment.
237 * @param td Source decomposition.
238 * @return Reference to this decomposition after assignment.
239 */
241
242/**
243 * @brief Return the treewidth of this decomposition.
244 * @return Treewidth (maximum bag size minus one).
245 */
246unsigned getTreewidth() const {
247 return treewidth;
248}
249
250/**
251 * @brief Cheap degeneracy lower bound on the treewidth of @p bc's primal graph.
252 *
253 * Computes the degeneracy @f$\delta D(G)@f$ (Maximum Minimum Degree) by a
254 * linear-time min-degree peel (Matula-Beck): repeatedly remove a
255 * minimum-degree node, the bound being the largest degree any node has at its
256 * own removal. @f$\delta D(G) \le \mathrm{tw}(G)@f$ (Maniu, Senellart, Jog,
257 * ICDT 2019, the fastest and best-behaved cheap lower bound there), so a value
258 * above @c MAX_TREEWIDTH proves the full @c min-fill build would fail -- letting
259 * a caller skip the (costlier) attempt. @c O(V+E), no decomposition built.
260 *
261 * The maximum degree @f$\Delta@f$ falls out of the same single pass (it bounds
262 * the per-step fill-in work of the min-fill build), so it is returned alongside.
263 *
264 * @param bc The Boolean circuit.
265 * @param max_degree Output: the maximum degree of the primal graph.
266 * @return A lower bound on the circuit primal graph's treewidth.
267 */
268static unsigned degeneracyLowerBound(const BooleanCircuit &bc,
269 unsigned &max_degree);
270
271/**
272 * @brief Degeneracy lower bound over an arbitrary graph.
273 *
274 * Core of the @c BooleanCircuit overload (which builds the primal graph
275 * and delegates), usable directly on a data graph -- e.g. the
276 * reachability compiler probes the edge relation's graph with it before
277 * paying for the min-fill construction. The graph is not mutated.
278 *
279 * @param graph The graph.
280 * @param max_degree Output: the maximum degree.
281 * @return A lower bound on the graph's treewidth.
282 */
283static unsigned degeneracyLowerBound(const Graph &graph,
284 unsigned &max_degree);
285
286/**
287 * @brief Restructure the tree into the friendly normal form.
288 *
289 * Reroots the tree at the bag that covers the circuit's root gate
290 * and splits/merges bags so that @c dDNNFTreeDecompositionBuilder
291 * can process them efficiently.
292 *
293 * @param root The gate that should be covered by the root bag.
294 */
296
297/**
298 * @brief Render the tree decomposition as a GraphViz DOT string.
299 * @return DOT @c digraph string for visualisation.
300 */
301std::string toDot() const;
302
303friend std::istream& operator>>(std::istream& in, TreeDecomposition &td);
305};
306
307/**
308 * @brief Read a tree decomposition in PACE challenge format.
309 * @param in Input stream.
310 * @param td Tree decomposition to populate.
311 * @return Reference to @p in.
312 */
313std::istream& operator>>(std::istream& in, TreeDecomposition &td);
314
315/**
316 * @brief Pre-increment operator for @c bag_t.
317 * @param b Bag to increment.
318 * @return Reference to the incremented bag.
319 */
320inline bag_t &operator++(bag_t &b) {
321 return b=bag_t{static_cast<std::underlying_type<bag_t>::type>(b)+1};
322}
323/**
324 * @brief Post-increment operator for @c bag_t.
325 * @param b Bag to increment.
326 * @return Original value of @p b before the increment.
327 */
328inline bag_t operator++(bag_t &b, int) {
329 auto temp{b};
330 b=bag_t{static_cast<std::underlying_type<bag_t>::type>(b)+1};
331 return temp;
332}
333
334/**
335 * @brief Compare a @c bag_t against a @c std::vector size type.
336 * @param t Bag identifier.
337 * @param u Size to compare against.
338 * @return @c true if the underlying integer of @p t is less than @p u.
339 */
340inline bool operator<(bag_t t, std::vector<bag_t>::size_type u)
341{
342 return static_cast<std::underlying_type<bag_t>::type>(t)<u;
343}
344
345/**
346 * @brief Convert a @c bag_t to its decimal string representation.
347 * @param b Bag identifier.
348 * @return Decimal string of the underlying integer.
349 */
350inline std::string to_string(bag_t b) {
351 return std::to_string(static_cast<std::underlying_type<bag_t>::type>(b));
352}
353
354/**
355 * @brief Read a @c bag_t from an input stream.
356 * @param i Input stream.
357 * @param b Bag to populate.
358 * @return Reference to @p i.
359 */
360inline std::istream &operator>>(std::istream &i, bag_t &b)
361{
362 std::underlying_type<bag_t>::type u;
363 i >> u;
364 b=bag_t{u};
365 return i;
366}
367
368/**
369 * @brief Exception thrown when a tree decomposition cannot be constructed.
370 *
371 * Raised when the treewidth of the circuit exceeds @c MAX_TREEWIDTH or
372 * when the input stream is malformed.
373 */
374class TreeDecompositionException : public std::exception {};
375
376#endif /* TREE_DECOMPOSITION_H */
Boolean provenance circuit with support for knowledge compilation.
gate_t
Strongly-typed gate identifier.
Definition Circuit.h:53
Undirected graph used in tree-decomposition computations.
std::istream & operator>>(std::istream &in, TreeDecomposition &td)
Read a tree decomposition in PACE challenge format.
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.
bool operator<(bag_t t, std::vector< bag_t >::size_type u)
Compare a bag_t against a std::vector size type.
bag_t & operator++(bag_t &b)
Pre-increment operator for bag_t.
Boolean circuit for provenance formula evaluation.
Mutable adjacency-list graph over unsigned-long node IDs.
Definition Graph.h:33
Exception thrown when a tree decomposition cannot be constructed.
Tree decomposition of a Boolean circuit's primal graph.
friend std::istream & operator>>(std::istream &in, TreeDecomposition &td)
Read a tree decomposition in PACE challenge format.
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.
const std::vector< bag_t > & getChildren(bag_t b) const
Const access to the children of bag b.
std::size_t getNbBags() const
Return the number of bags in the decomposition.
std::vector< Bag > bags
Bag contents, indexed by bag_t.
TreeDecomposition(const TreeDecomposition &td)
Copy constructor.
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.
unsigned getTreewidth() const
Return the treewidth of this decomposition.
TreeDecomposition()=default
bag_t getRoot() const
Return the root bag of the decomposition.
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.
friend class dDNNFTreeDecompositionBuilder
const Bag & getBag(bag_t b) const
Const access to bag b.
std::vector< bag_t > parent
Parent of each bag (root points to itself).
boost::container::static_vector< T, MAX_TREEWIDTH+1 > small_vector
Stack-allocated vector type bounded by MAX_TREEWIDTH+1 elements.
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.
TreeDecomposition & operator=(const TreeDecomposition &td)
Copy assignment.
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.
Builds a d-DNNF from a Boolean circuit using a tree decomposition.
TreeDecomposition & td
Tree decomposition of the circuit's primal graph.
Flat (unsorted, contiguous-storage) set template.
Flat set with pluggable storage.
Definition flat_set.hpp:41