29#include <unordered_map>
30#include <unordered_set>
50#define CHECK_FOR_INTERRUPTS() provsql_tdkc_poll()
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)
85 const unsigned u =
static_cast<unsigned>(g1);
88 const unsigned v =
static_cast<unsigned>(g2);
91 arcs.emplace_back(u, v);
92 arcs.emplace_back(v, u);
96 std::sort(arcs.begin(), arcs.end());
97 arcs.erase(std::unique(arcs.begin(), arcs.end()), arcs.end());
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);
115 std::vector<unsigned> deg(n, 0);
116 unsigned max_deg = 0;
117 for(std::size_t u = 0; u < n; ++u)
119 deg[u] =
static_cast<unsigned>(start[u + 1] - start[u]);
120 max_deg = std::max(max_deg, deg[u]);
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)
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);
137 std::vector<std::size_t> next(bin.begin(), bin.end() - 1);
138 for(std::size_t u = 0; u < n; ++u)
140 pos[u] = next[deg[u]]++;
141 vert[pos[u]] =
static_cast<unsigned>(u);
144 unsigned degeneracy = 0;
145 for(std::size_t i = 0; i < nb_nodes; ++i) {
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]) {
154 const unsigned du = deg[u];
155 const std::size_t pu = pos[u], pw = bin[du];
156 const unsigned w = vert[pw];
158 vert[pu] = w; pos[w] = pu;
159 vert[pw] = u; pos[u] = pw;
170 unsigned &max_degree)
180 std::unordered_map<unsigned long, unsigned> deg;
181 deg.reserve(nodes.size());
182 unsigned max_deg = 0;
183 for(
unsigned long n : nodes) {
187 max_deg = std::max(max_deg, d);
189 max_degree = max_deg;
196 std::vector<std::set<unsigned long> > bucket(max_deg + 1);
197 for(
const auto &kv : deg)
198 bucket[kv.second].insert(kv.first);
204 unsigned degeneracy = 0;
205 std::unordered_set<unsigned long> removed;
206 removed.reserve(nodes.size());
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())
214 unsigned long v = *bucket[scan].begin();
215 bucket[scan].erase(bucket[scan].begin());
216 degeneracy = std::max(degeneracy, scan);
220 if(removed.find(u) != removed.end())
225 bucket[d - 1].insert(u);
230 CHECK_FOR_INTERRUPTS();
270 auto nb_bags =
bags.size();
271 for(
bag_t i{0}; i<nb_bags; ++i) {
278 decltype(copy_children) new_children;
279 new_children.push_back(current);
281 new_children.push_back(copy_children[k]);
289 nb_bags =
bags.size();
290 for(
bag_t i{0}; i<nb_bags; ++i) {
293 for(
size_t j = 1; j <
getBag(i).
size(); ++j) {
296 for(
size_t k = 0; k <
getBag(i).
size() - j; ++k, ++it)
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)];
311 getChildrenGates(
getParent(i)).insert(g);
318 nb_bags =
bags.size();
319 for(
bag_t i{0}; i<nb_bags; ++i) {
322 std::vector<gate_t> extra_gates;
324 if(getChildrenGates(i).find(g) == getChildrenGates(i).end())
325 extra_gates.push_back(g);
327 intersection.insert(g);
330 if(!extra_gates.empty()) {
333 if(
getChildren(i).size()==1 && intersection.size()==getChildrenGates(i).size()) {
338 auto gate = extra_gates.back();
341 extra_gates.pop_back();
345 for(
auto g: extra_gates) {
361 const std::vector<bag_t> &ch)
409 std::string result=
"digraph circuit{\n graph [rankdir=UD] ;\n";
413 result +=
" " +
to_string(i) +
" [label=\"{";
415 for(
auto gate:
getBag(i)) {
438 unsigned long nb_bags;
441 td.
bags.resize(nb_bags);
442 td.
parent.resize(nb_bags);
445 for(
bag_t i{0}; i<nb_bags; ++i) {
456 for(
unsigned long j=0; j<nb_gates; ++j) {
471 unsigned long nb_children;
474 for(
unsigned long j=0; j<nb_children; ++j) {
493 Graph graph, std::unordered_map<unsigned long, bag_t> *elimination_bag,
504 unsigned max_width{0};
505 std::unordered_map<gate_t, bag_t> bag_ids;
516 CHECK_FOR_INTERRUPTS();
518 unsigned long node = strategy.
get_next();
520 std::unordered_set<unsigned long> neigh = graph.
remove_node(node);
521 max_width = std::max<unsigned>(neigh.size(), max_width);
523 if(max_width>width_cap)
538 (*elimination_bag)[node] = bag_id;
539 bag_ids[
gate_t{node}] = bag_id++;
552 (*elimination_bag)[n] =
bag_t{
bags.size()};
554 bags.push_back(remaining_bag);
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);
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.
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.
gateType getGateType(gate_t g) const
Return the type of gate g.
std::vector< gate_t >::size_type getNbGates() const
Return the total number of gates in the circuit.
Mutable adjacency-list graph over unsigned-long node IDs.
void fill(const std::unordered_set< unsigned long > &nodes, bool undirected=true)
Add all missing edges within nodes (clique fill).
const std::unordered_set< unsigned long > & get_nodes() const
Return the set of all node IDs in the graph.
bool has_neighbours(unsigned long node) const
Return true if node has any adjacent edges.
std::unordered_set< unsigned long > remove_node(unsigned long node)
Remove node and all its incident edges.
const std::unordered_set< unsigned long > & get_neighbours(unsigned long node) const
Return the neighbour set of node.
unsigned long number_nodes() const
Return the number of nodes in the graph.
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.
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
iterator begin()
Return iterator to the first element.
size_t size() const
Return the number of elements in the set.
void insert(const K &value)
Insert value if not already present (const-ref overload).
Build-loop interrupt hook for the standalone tdkc binary.