dDNNF.cpp File Reference

d-DNNF circuit operations and evaluation algorithms. More...

#include "dDNNF.h"
#include "Circuit.hpp"
#include <unordered_map>
#include <stack>
#include <variant>
#include <cassert>
#include <algorithm>
#include <numeric>

Include dependency graph for dDNNF.cpp:

Go to the source code of this file.

Functions
static long long	comb (unsigned n, unsigned k)
	Compute the binomial coefficient C(n, k).

Detailed Description

d-DNNF circuit operations and evaluation algorithms.

Implements all methods of dDNNF declared in dDNNF.h:

• vars(): set of reachable input (IN) gates.
• makeSmooth(): smooth the circuit so every OR gate's children mention the same variable set.
• makeGatesBinary(): binarise n-ary AND/OR gates.
• simplify(): constant propagation.
• condition() / conditionAndSimplify(): fix one variable.
• probabilityEvaluation(): exact probability in linear time.
• shapley() / banzhaf(): power index computation.
• topological_order(): DFS topological sort.

The private helpers shapley_delta() and shapley_alpha() implement the polynomial-time Shapley-value algorithm for d-DNNFs.

Definition in file dDNNF.cpp.

Function Documentation

comb()

static long long comb ( unsigned  n, unsigned  k  )

static

Compute the binomial coefficient C(n, k).

Parameters

n	Total number of elements.
k	Number of elements to choose; must satisfy k ≤ n.

Returns

The binomial coefficient n-choose-k.

Definition at line 400 of file dDNNF.cpp.

Here is the call graph for this function:

Here is the caller graph for this function: