22#include <unordered_map>
37 std::stack<gate_t> to_process;
38 std::unordered_set<gate_t> processed;
39 to_process.push(
root);
41 std::unordered_set<gate_t> result;
42 while(!to_process.empty())
44 auto g = to_process.top();
47 if(processed.find(g)==processed.end()) {
71 std::unordered_set<gate_t> all;
72 std::vector<std::unordered_set<gate_t> > varss;
76 varss.push_back(
vars(x));
78 std::for_each(varss.begin(), varss.end(),
80 all.insert(s.begin(),s.end());
84 bool modified =
false;
85 for(
size_t i=0; i<varss.size(); ++i) {
86 if(varss[i].find(v)==varss[i].end()) {
100 addWire(dummy_or_gate, dummy_not_gate);
117 for(
size_t i=1; i<3; ++i) {
127 const auto k = w.size();
129 for(
unsigned i=0; i<k; ++i)
143 if (
gates.size() == 0)
149 using RecursionParams =
struct {
151 size_t children_processed;
152 double partial_value;
154 using RecursionResult = double;
155 std::stack<std::variant<RecursionParams,RecursionResult> > stack;
156 stack.emplace(RecursionParams{
root,0,0.});
159 double child_value{0.};
161 if(stack.top().index()==1) {
162 child_value=std::get<1>(stack.top());
166 auto [g, children_processed, partial_value]=std::get<0>(stack.top());
175 stack.emplace(it->second);
177 if(children_processed==0) {
201 partial_value *= child_value;
203 partial_value = 1-child_value;
205 partial_value += child_value;
209 if(children_processed<
getWires(g).size()) {
210 stack.emplace(RecursionParams{g,children_processed+1,partial_value});
211 stack.emplace(RecursionParams{
getWires(g)[children_processed],0,0.});
213 double result = partial_value;
219 stack.emplace(result);
229 std::unordered_map<gate_t, double> result;
230 std::unordered_map<gate_t, double> prod_one_plus_p;
235 std::stack<std::pair<gate_t, bool> > stack;
236 stack.emplace(std::make_pair(
root,
false));
238 while(!stack.empty())
240 auto [node, b] = stack.top();
243 if(result.find(node)!=result.end()) {
251 prod_one_plus_p[node] = 1+
getProb(node);
256 stack.push(std::make_pair(node,
true));
257 stack.push(std::make_pair(
getWires(node)[0],
false));
260 result[node] = prod_one_plus_p[child] - result[child];
261 prod_one_plus_p[node] = prod_one_plus_p[child];
269 prod_one_plus_p[node] = 1.;
271 stack.push(std::make_pair(node,
true));
273 stack.push(std::make_pair(c,
false));
278 [&](
auto r,
auto g) {
279 return r + result[g];
281 prod_one_plus_p[node] = prod_one_plus_p[
getWires(node)[0]];
289 prod_one_plus_p[node] = 1.;
291 stack.push(std::make_pair(node,
true));
293 stack.push(std::make_pair(c,
false));
298 [&](
auto r,
auto g) {
299 return r * result[g];
301 prod_one_plus_p[node] =
303 [&](
auto r,
auto g) {
304 return r * prod_one_plus_p[g];
321 std::unordered_map<gate_t, std::vector<double> > result;
329 std::stack<std::pair<gate_t, bool> > stack;
330 stack.emplace(std::make_pair(
root,
false));
332 while(!stack.empty())
334 auto [node, b] = stack.top();
337 if(result.find(node)!=result.end()) {
353 stack.push(std::make_pair(node,
true));
355 stack.push(std::make_pair(c,
false));
358 result[node] = result[
getWires(node)[0]];
368 stack.push(std::make_pair(node,
true));
370 stack.push(std::make_pair(c,
false));
374 result[node] = result[
getWires(node)[0]];
377 const auto &r1 = result[
getWires(node)[0]];
378 const auto &r2 = result[
getWires(node)[1]];
379 const auto n1=r1.size()-1;
380 const auto n2=r2.size()-1;
381 for(
size_t k=0; k<=n1+n2; ++k) {
383 for(
size_t k1=std::max(0,
static_cast<int>(k-n2)); k1<=std::min(k,n1); ++k1) {
386 result[node].push_back(r);
411static long long comb(
unsigned n,
unsigned k)
419 else return n *
comb(n-1,k-1) / k;
423 std::unordered_map<gate_t, std::vector<double> > delta {
shapley_delta()};
424 std::unordered_map<gate_t, std::vector<std::vector<double> > > result;
429 std::stack<std::pair<gate_t, bool> > stack;
430 stack.emplace(std::make_pair(
root,
false));
432 while(!stack.empty())
434 auto [node, b] = stack.top();
437 if(result.find(node)!=result.end()) {
444 result[node] = {{0},{0,
getProb(node)}};
449 stack.push(std::make_pair(node,
true));
450 stack.push(std::make_pair(
getWires(node)[0],
false));
452 result[node] = result[
getWires(node)[0]];
454 for(
unsigned k=k0; k<result[node].size(); ++k)
455 for(
unsigned l=0; l<=k; ++l) {
456 result[node][k][l] *= -1;
465 result[node] = {{0.}};
467 stack.push(std::make_pair(node,
true));
469 stack.push(std::make_pair(c,
false));
472 result[node] = result[
getWires(node)[0]];
473 for(
size_t i=1; i<
getWires(node).size(); ++i) {
474 const auto &r = result[
getWires(node)[i]];
476 for(
unsigned k=k0; k<r.size(); ++k)
477 for(
unsigned l=0; l<r[k].size(); ++l)
478 result[node][k][l]+=r[k][l];
486 result[node] = {{1.}};
488 stack.push(std::make_pair(node,
true));
490 stack.push(std::make_pair(c,
false));
494 result[node] = result[
getWires(node)[0]];
497 const auto &r1 = result[
getWires(node)[0]];
498 const auto &r2 = result[
getWires(node)[1]];
499 const auto n1=r1.size()-1;
500 const auto n2=r2.size()-1;
501 result[node].resize(n1+n2+1);
503 for(
size_t k=k0; k<=n1+n2; ++k) {
504 result[node][k].resize(k+1);
505 for(
size_t l=0; l<=k; ++l) {
506 for(
size_t k1=std::max(0,
static_cast<int>(k-n2)); k1<=std::min(k,n1); ++k1)
507 for(
size_t l1=std::max(0,
static_cast<int>(l-k+k1)); l1<=std::min(k1,l); ++l1)
508 result[node][k][l] += r1[k1][l1] * r2[k-k1][l-l1];
530 auto alpha_pos=cond_pos.shapley_alpha();
531 auto alpha_neg=cond_neg.shapley_alpha();
536 for(
size_t k=k0; k<alpha_pos.size(); ++k)
537 for(
size_t l=0; l<=k; ++l) {
538 double pos = alpha_pos[k][l];
539 double neg = alpha_neg[k][l];
540 result += (pos-neg)/
comb(k,l)/(k+1);
558 auto env_pos=cond_pos.banzhaf_internal();
559 auto env_neg=cond_neg.banzhaf_internal();
561 return getProb(var) * (env_pos-env_neg);
579 std::vector<gate_t> result;
581 std::stack<gate_t> nodesToProcess;
582 std::vector<size_t> inDegree(
wires.size());
584 for(
size_t g=0; g<
wires.size(); ++g)
585 if(!(inDegree[g] =
wires[g].size()))
586 nodesToProcess.push(
gate_t{g});
588 while(!nodesToProcess.empty()) {
589 auto g = nodesToProcess.top();
590 nodesToProcess.pop();
592 for(
auto p: reversedWires[
static_cast<size_t>(g)])
593 if(!(--inDegree[
static_cast<size_t>(p)]))
594 nodesToProcess.push(p);
601 std::vector<std::vector<gate_t> > reversedWires(
gates.size());
602 for(
size_t i=0; i<
wires.size(); ++i)
603 for(
auto g:
wires[i])
604 reversedWires[
static_cast<size_t>(g)].push_back(
gate_t{i});
607 auto &w =
wires[
static_cast<size_t>(node)];
620 bool shorted =
false;
621 for(
auto c=w.begin(); c!=w.end();) {
639 }
else if(w.size()==1) {
643 for(
auto p: reversedWires[
static_cast<size_t>(node)])
644 std::replace(
wires[
static_cast<size_t>(p)].begin(),
wires[
static_cast<size_t>(p)].end(), node, w[0]);
670 std::vector<bool> used(
gates.size());
671 std::stack<gate_t> to_process;
672 to_process.push(
root);
674 while(!to_process.empty()) {
675 auto g = to_process.top();
677 used[
static_cast<size_t>(g)]=
true;
678 for(
auto c:
wires[
static_cast<size_t>(g)])
679 if(!used[
static_cast<size_t>(c)])
684 std::vector<gate_t> relabel(
gates.size());
685 for(
size_t i=0; i<
gates.size(); ++i)
731 for(
size_t i=0; i<w.size(); ++i)
732 w[i]=relabel[
static_cast<size_t>(w[i])];
740 std::set<gate_t> seen;
742 std::stack<gate_t> stk;
744 while(!stk.empty()) {
777 for(std::size_t i = 1; i < children.size() && s.
smooth; ++i)
778 if(
vars(children[i]) !=
vars(children[0]))
785 std::unordered_map<gate_t, int, hash_gate_t> depth;
786 std::function<int(
gate_t)> longest = [&](
gate_t g) ->
int {
787 auto it = depth.find(g);
788 if(it != depth.end())
793 d = std::max(d, 1 + longest(c));
797 s.
depth = seen.empty() ? 0 : longest(
root);
803 const std::function<
int(
const std::string &)> &var_of_uuid)
const
807 std::vector<std::string> lines;
808 std::unordered_map<gate_t, int, hash_gate_t> idx;
809 std::size_t edges = 0;
814 auto var_of = [&](
gate_t g) ->
int {
817 int v = var_of_uuid(
getUUID(g));
822 return static_cast<int>(
823 static_cast<std::underlying_type<gate_t>::type
>(g)) + 1;
826 std::function<int(
gate_t)> emit = [&](
gate_t g) ->
int {
827 auto found = idx.find(g);
828 if(found != idx.end())
829 return found->second;
835 max_var = std::max(max_var, v);
836 line =
"L " + std::to_string(v);
846 "toNNF: NOT over a non-input gate (circuit not in negation normal form)");
848 max_var = std::max(max_var, v);
849 line =
"L -" + std::to_string(v);
855 ch.push_back(emit(c));
857 line =
"A " + std::to_string(ch.size());
859 line +=
" " + std::to_string(i);
865 ch.push_back(emit(c));
869 line =
"O 0 " + std::to_string(ch.size());
871 line +=
" " + std::to_string(i);
878 int my =
static_cast<int>(lines.size());
879 lines.push_back(std::move(line));
886 std::ostringstream out;
887 out <<
"nnf " << lines.size() <<
" " << edges <<
" " << max_var <<
"\n";
888 for(
const auto &l : lines)
895 std::ostringstream out;
896 out <<
"digraph dDNNF {\n"
897 <<
" graph [rankdir=TB];\n"
898 <<
" node [fontname=\"Helvetica\"];\n";
902 std::stack<gate_t> stk;
903 std::set<gate_t> seen;
905 while(!stk.empty()) {
922 auto id =
static_cast<std::underlying_type<gate_t>::type
>(g);
924 std::string shape =
"circle";
939 fill =
", style=filled, fillcolor=\"#e6f0fa\"";
940 const std::string u =
getUUID(g);
941 std::string sh = u.size() > 8 ? u.substr(0, 8) : u;
942 std::ostringstream lab;
943 lab << sh <<
"\\np=" << std::fixed << std::setprecision(3) <<
prob[id];
957 out <<
" n" <<
id <<
" [label=\"" << label <<
"\", shape=" << shape
960 out <<
", tooltip=\"" << tooltip <<
"\"";
962 out <<
", penwidth=2";
970 auto id =
static_cast<std::underlying_type<gate_t>::type
>(g);
974 auto cid =
static_cast<std::underlying_type<gate_t>::type
>(c);
975 out <<
" n" <<
id <<
" -> n" << cid <<
";\n";
BooleanGate
Gate types for a Boolean provenance circuit.
@ 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).
gate_t
Strongly-typed gate identifier.
Out-of-line template method implementations for Circuit<gateType>.
std::vector< double > prob
Per-gate probability (for IN gates).
std::set< gate_t > inputs
Set of IN (input) gate IDs.
gate_t setGate(BooleanGate type) override
Allocate a new gate with type type and no UUID.
double getProb(gate_t g) const
Return the probability stored for gate g.
bool isProbabilistic() const
Return true if any gate has a non-trivial (< 1) probability.
Exception type thrown by circuit operations on invalid input.
unsigned char nameKind(gate_t g) const
std::vector< unsigned char > name_kind
std::vector< gate_t > & getWires(gate_t g)
BooleanGate getGateType(gate_t g) const
void dropName(gate_t g)
Remove the name of gate g, if any.
void addWire(gate_t f, gate_t t)
void setGateType(gate_t g, gateType t)
Update the type of an existing gate.
std::vector< BooleanGate > gates
std::vector< gate_uuid > id2uuid
uuid getUUID(gate_t g) const
std::vector< std::vector< gate_t > > wires
void moveName(gate_t from, gate_t to)
A d-DNNF circuit supporting exact probabilistic and game-theoretic evaluation.
std::string toNNF(const std::function< int(const std::string &)> &var_of_uuid={}) const
Serialise the d-DNNF in the c2d / d4 ".nnf" text format.
gate_t root
The root gate of the d-DNNF.
dDNNF condition(gate_t var, bool value) const
Condition on variable var having value value (no simplification).
double banzhaf_internal() const
Compute the unnormalised Banzhaf value for the whole circuit.
Stats nodeStats() const
Compute structural statistics over the gates reachable from root.
double probabilityEvaluation() const
Compute the exact probability of the d-DNNF being true.
void simplify()
Simplify the d-DNNF by removing redundant constants.
void makeSmooth()
Make the d-DNNF smooth.
void makeGatesBinary(BooleanGate type)
Rewrite all n-ary AND/OR gates into binary trees.
std::vector< std::vector< double > > shapley_alpha() const
Compute the α table used in the Shapley algorithm.
double shapley(gate_t var) const
Compute the Shapley value of input gate var.
double banzhaf(gate_t var) const
Compute the Banzhaf power index of input gate var.
std::vector< gate_t > topological_order(const std::vector< std::vector< gate_t > > &reversedWires) const
Compute a topological ordering of the circuit.
std::unordered_set< gate_t > vars(gate_t root) const
Return the set of all variable (IN) gates reachable from root.
std::unordered_map< gate_t, double, hash_gate_t > probability_cache
Memoisation cache mapping gates to their probability values.
gate_t getRoot() const
Return the root gate of this d-DNNF.
std::unordered_map< gate_t, std::vector< double > > shapley_delta() const
Compute the δ table used in the Shapley algorithm.
std::string toDot() const
Return a GraphViz DOT representation of the d-DNNF.
static long long comb(unsigned n, unsigned k)
Compute the binomial coefficient C(n, k).
Decomposable Deterministic Negation Normal Form circuit.
Structural statistics of a compiled d-DNNF.
bool smooth
Every OR gate's children share their variable set.
int depth
Longest path (in gates) from the root.
std::size_t nodes
Total reachable gates.
std::size_t or_gates
OR (decision) gates.
std::size_t edges
Total wires among reachable gates.
std::size_t not_gates
NOT gates.
std::size_t inputs
IN (variable) leaves.
std::size_t and_gates
AND (decomposition) gates.