msk-ono/rdd

Decision diagram library for Rust.

rdd's Issues

Add new BDD example: P3□P3.

P3□P3

graph G {
  1 -- 2
  2 -- 4
  3 -- 5
  5 -- 7
  6 -- 8
  8 -- 9
  1 -- 3
  2 -- 5
  4 -- 7
  3 -- 6
  5 -- 8
  7 -- 9
}

Construct generating function of BDD.

If we have BDD of function $f(x_1, \dots, x_n)$, we can efficiently construct generating function $a_0 + a_1 z + \dots + a_n z^n$.

$a_i$ is the number of $(x_1, \dots, x_n)$ such that $f(x_1, \dots, x_n) = 1$ and $x_1 + \dots + x_n = j$.

Convert BDD to a sequence of branch instructions.

See equation (8) of TAOCP 7.1.4.

Profile BDD library.

BDD is really slow.

Use some profiling tool and find bottlenecks.

• : Select the profiling tool.
• : Run profiler.
• : List bottlenecks.

Dump weight of edges in DOT.

Implement DumpDotOption::dump_weight.

Implement ZDD.

Solve linear Boolean programming problem of BDD.

Linear Boolean programming problem:

Given $(w_1, \dots, w_n)$, find $(x_1, \dots, x_n)$ ($f(x_1, \dots, x_n) = 1$) that maximizes $w_1 x_1 + \dots + w_n x_n$.

We can solve this problem efficiently if we construct BDD of $f$.

Add new BDD example: TAOCP exercise 43.

• : $f(x_1, \dots, x_{2n}) = [x_1 + \dots + x_n = x_{n+1} + \dots + x_{2n}]$
• : $f(x_1, \dots, x_{2n}) = [x_1 + x_3 + \dots + x_{2n-1} = x_2 + x_4 + \dots + x_{2n}]$