1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
//! Multi-valued decision diagrams (MDDs) of constraints: compilation, relaxation and queries.
//!
//! An MDD stores the solutions of a constraint problem as the paths of a layered graph: one layer
//! per variable, an edge for each value a variable may take, and a single root and sink. This
//! module compiles the constraints of a [`Problem`](crate::modelling::Problem) into such a
//! diagram, with a limit on the width of the layers if wanted, and allow tractable queries on it:
//! counting its solutions and reading one off it, and weighted model counting (`wmc`) for the
//! sampling and belief propagation code.
//!
//! - [`Compiler`] builds a diagram from any subset of the constraints of a problem and refines it,
//! as many times as wanted and with growing widths if wanted.
//! - [`Mdd`] is the diagram itself, which a [`Compiler`] owns and lends out between refinements.
//! - [`MddArena`] caches the diagram of each constraint shape so that identical constraints on
//! different variables share it.
//! - [`heuristics`] holds the choices that steer the compilation.
//! # Example
//!
//! ```
//! use aicad::constraints::all_different;
//! use aicad::mdd::Compiler;
//! use aicad::mdd::heuristics::{
//! CompilationHeuristic, MergeHeuristic, OrderingHeuristic, SelectHeuristic,
//! };
//! use aicad::modelling::Problem;
//! use std::sync::Arc;
//!
//! let mut problem = Problem::default();
//! let vars = problem.add_variables(3, vec![0, 1, 2]);
//! let constraint = all_different(&mut problem, vars);
//!
//! let mut compiler = Compiler::new(
//! Arc::new(problem),
//! CompilationHeuristic {
//! ordering: OrderingHeuristic::MinDomMaxLinked,
//! merge: MergeHeuristic::LessRelaxed,
//! selection: SelectHeuristic::Greedy,
//! },
//! &[constraint],
//! );
//! compiler.refine(usize::MAX);
//! let mdd = compiler.into_mdd();
//!
//! // The permutations of three values.
//! assert_eq!(mdd.count_solutions().to_string(), "6");
//! let (mut values, variables) = mdd.get_solution().expect("the diagram is satisfiable");
//! assert_eq!(variables.len(), 3);
//! values.sort();
//! assert_eq!(values, vec![0, 1, 2]);
//! ```
pub
pub
pub
pub
pub
pub use MddArena;
pub use Compiler;
pub use Mdd;
pub use ;
pub use Edge;
pub use Node;
use crate*;
use ;
/// Address of a node: its layer, then its position in the layer.
;
/// Address of an edge: the layer it leaves, then its position among the edges of that layer.
;
/// What makes two nodes of a layer interchangeable: all their top-down and bottom-up properties
/// are equal. `Compiler::collapse` merges the nodes that share a key, which does not relax the diagram.