use super::*;
use crate::modelling::*;
use num_bigint::BigUint;
use std::sync::Arc;
pub struct Mdd {
pub(super) problem: Arc<Problem>,
pub(super) nodes: Vec<Vec<Node>>,
pub(super) edges: Vec<Vec<Edge>>,
pub(super) order: Vec<VariableIndex>,
}
impl Mdd {
pub(super) fn with_layers(problem: Arc<Problem>, number_layers: usize) -> Self {
Self {
problem,
nodes: vec![vec![]; number_layers + 1],
edges: vec![vec![]; number_layers],
order: vec![],
}
}
#[cfg(test)]
pub(crate) fn from_parts(nodes: Vec<Vec<Node>>, edges: Vec<Vec<Edge>>) -> Self {
Self {
problem: Arc::new(Problem::default()),
nodes,
edges,
order: vec![],
}
}
#[cfg(all(test, feature = "learning"))]
pub(crate) fn number_nodes(&self) -> usize {
self.nodes.iter().map(|layer| layer.len()).sum()
}
#[cfg(all(test, feature = "learning"))]
pub(crate) fn number_edges(&self) -> usize {
self.edges.iter().map(|layer| layer.len()).sum()
}
pub(super) fn clear(&mut self) {
self.nodes.clear();
self.edges.clear();
self.order.clear();
}
pub fn number_layers(&self) -> usize {
self.nodes.len()
}
pub fn number_nodes_in_layer(&self, layer: usize) -> usize {
self.nodes[layer].len()
}
pub fn is_unsat(&self) -> bool {
self.number_layers() == 0
}
pub fn root(&self) -> NodeIndex {
assert!(!self.is_unsat(), "an unsatisfiable diagram has no root");
NodeIndex(0, 0)
}
pub fn sink(&self) -> NodeIndex {
assert!(!self.is_unsat(), "an unsatisfiable diagram has no sink");
NodeIndex(self.number_layers() - 1, 0)
}
pub fn nodes_in_layer(&self, layer: usize) -> impl Iterator<Item = NodeIndex> + '_ {
(0..self.number_nodes_in_layer(layer)).map(move |index| NodeIndex(layer, index))
}
pub fn debug_assert_root_and_sink(&self) {
if self.is_unsat() {
return;
}
let last_layer = self.number_layers() - 1;
debug_assert_eq!(
self.number_nodes_in_layer(0),
1,
"the root layer must have exactly one node"
);
debug_assert_eq!(
self.number_nodes_in_layer(last_layer),
1,
"the sink layer must have exactly one node"
);
}
pub fn count_solutions(&self) -> BigUint {
if self.is_unsat() {
return BigUint::from(0u32);
}
let last_layer = self.number_layers() - 1;
let mut counts: Vec<Vec<BigUint>> = (0..=last_layer)
.map(|layer| {
let value = BigUint::from(u32::from(layer == last_layer));
vec![value; self.number_nodes_in_layer(layer)]
})
.collect();
for layer in (0..last_layer).rev() {
for node in self.nodes_in_layer(layer) {
let mut total = BigUint::from(0u32);
for edge in self[node].iter_children() {
let NodeIndex(to_layer, to_index) = self[edge].to();
total += &counts[to_layer][to_index];
}
counts[layer][node.1] = total;
}
}
counts[0][0].clone()
}
pub fn exact_path(&self) -> Option<Vec<ValueIndex>> {
if self.is_unsat() {
return None;
}
let sink_layer = self.number_layers() - 1;
let mut way_on: Vec<Vec<Option<EdgeIndex>>> = (0..sink_layer)
.map(|layer| vec![None; self.number_nodes_in_layer(layer)])
.collect();
for layer in (0..sink_layer).rev() {
for node in self.nodes_in_layer(layer) {
if self[node].is_relaxed() {
continue;
}
way_on[layer][node.1] = self[node].iter_children().find(|&edge| {
let NodeIndex(child_layer, child_position) = self[edge].to();
child_layer == sink_layer || way_on[child_layer][child_position].is_some()
});
}
}
let mut path = Vec::with_capacity(sink_layer);
let mut node = self.root();
while node.0 < sink_layer {
let edge = way_on[node.0][node.1]?;
path.push(self[edge].assignment());
node = self[edge].to();
}
Some(path)
}
pub fn number_decisions(&self) -> usize {
self.order.len()
}
pub fn decision_at_layer(&self, layer: usize) -> VariableIndex {
self.order[layer]
}
pub fn problem(&self) -> &Problem {
&self.problem
}
}
impl std::ops::Index<EdgeIndex> for Mdd {
type Output = Edge;
fn index(&self, index: EdgeIndex) -> &Self::Output {
&self.edges[index.0][index.1]
}
}
impl std::ops::IndexMut<EdgeIndex> for Mdd {
fn index_mut(&mut self, index: EdgeIndex) -> &mut Self::Output {
&mut self.edges[index.0][index.1]
}
}
impl std::ops::Index<NodeIndex> for Mdd {
type Output = Node;
fn index(&self, index: NodeIndex) -> &Self::Output {
&self.nodes[index.0][index.1]
}
}
impl std::ops::IndexMut<NodeIndex> for Mdd {
fn index_mut(&mut self, index: NodeIndex) -> &mut Self::Output {
&mut self.nodes[index.0][index.1]
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::constraints::all_different;
use crate::mdd::heuristics::*;
use crate::mdd::{Compiler, Mdd, Node};
use crate::modelling::Problem;
use std::sync::Arc;
fn compiled(unsat: bool) -> Mdd {
let mut problem = Problem::default();
let domain = if unsat { vec![0] } else { vec![0, 1, 2] };
let vars = problem.add_variables(3, domain);
let c = all_different(&mut problem, vars);
let mut compiler = Compiler::new(
Arc::new(problem),
CompilationHeuristic {
ordering: OrderingHeuristic::MinDomMaxLinked,
merge: MergeHeuristic::LessRelaxed,
selection: SelectHeuristic::Greedy,
},
&[c],
);
compiler.refine(usize::MAX);
compiler.into_mdd()
}
#[test]
fn the_first_layer_holds_the_root_and_the_last_the_sink() {
let mdd = compiled(false);
assert_eq!(mdd.root(), NodeIndex(0, 0));
assert_eq!(mdd.number_layers(), 4);
assert_eq!(mdd.sink().0, mdd.number_layers() - 1);
assert_eq!(mdd.number_nodes_in_layer(0), 1);
assert_eq!(mdd.number_nodes_in_layer(3), 1);
assert!(!mdd.is_unsat());
}
#[test]
fn the_order_names_each_variable_once() {
let mdd = compiled(false);
let mut seen: Vec<_> = (0..mdd.number_decisions())
.map(|l| *mdd.decision_at_layer(l))
.collect();
seen.sort();
assert_eq!(seen, vec![0, 1, 2]);
}
#[test]
fn an_unsatisfiable_diagram_holds_nothing() {
let mdd = compiled(true);
assert!(mdd.is_unsat());
assert_eq!(mdd.number_layers(), 0);
assert_eq!(mdd.count_solutions().to_string(), "0");
assert_eq!(mdd.exact_path(), None);
mdd.debug_assert_root_and_sink();
}
#[test]
#[should_panic(expected = "an unsatisfiable diagram has no root")]
fn an_unsatisfiable_diagram_has_no_root() {
compiled(true).root();
}
#[test]
#[should_panic(expected = "an unsatisfiable diagram has no sink")]
fn an_unsatisfiable_diagram_has_no_sink() {
compiled(true).sink();
}
#[test]
fn the_solutions_are_counted_and_an_exact_one_is_read_off() {
let mdd = compiled(false);
assert_eq!(mdd.count_solutions().to_string(), "6");
let path = mdd.exact_path().expect("the diagram is exact");
assert_eq!(path.len(), 3);
let mut values: Vec<usize> = path.iter().map(|value| value.0).collect();
values.sort();
assert_eq!(values, vec![0, 1, 2]);
}
fn structure_with_roots(roots: usize) -> Mdd {
let mut nodes: Vec<Vec<Node>> = vec![(0..roots).map(|i| Node::new(0, i, false)).collect()];
nodes.push(vec![Node::new(1, 0, true)]);
Mdd::from_parts(nodes, vec![vec![]])
}
#[test]
fn a_single_root_and_sink_pass_the_check() {
structure_with_roots(1).debug_assert_root_and_sink();
}
#[test]
#[cfg(debug_assertions)]
#[should_panic(expected = "the root layer must have exactly one node")]
fn two_roots_fail_the_check() {
structure_with_roots(2).debug_assert_root_and_sink();
}
#[test]
#[cfg(debug_assertions)]
#[should_panic(expected = "the sink layer must have exactly one node")]
fn two_sinks_fail_the_check() {
let mut structure = structure_with_roots(1);
structure.nodes[1].push(Node::new(1, 1, true));
structure.debug_assert_root_and_sink();
}
fn fork(relaxed: [[bool; 2]; 2]) -> Mdd {
let node = |layer: usize, index: usize, relaxed: bool| Node::new(layer, index, relaxed);
let mut nodes = vec![
vec![node(0, 0, false)],
vec![node(1, 0, relaxed[0][0]), node(1, 1, relaxed[0][1])],
vec![node(2, 0, relaxed[1][0]), node(2, 1, relaxed[1][1])],
vec![node(3, 0, true)],
];
let links = [
(NodeIndex(0, 0), NodeIndex(1, 0), 0),
(NodeIndex(0, 0), NodeIndex(1, 1), 1),
(NodeIndex(1, 0), NodeIndex(2, 0), 0),
(NodeIndex(1, 1), NodeIndex(2, 1), 0),
(NodeIndex(2, 0), NodeIndex(3, 0), 0),
(NodeIndex(2, 1), NodeIndex(3, 0), 1),
];
let mut edges: Vec<Vec<Edge>> = vec![vec![]; 3];
for (from, to, value) in links {
let edge_index = EdgeIndex(from.0, edges[from.0].len());
nodes[from.0][from.1].add_child_edge(edge_index);
nodes[to.0][to.1].add_parent_edge(edge_index);
edges[from.0].push(Edge::new(from, to, ValueIndex(value)));
}
Mdd::from_parts(nodes, edges)
}
#[test]
fn an_exact_path_is_found_even_when_the_first_branch_is_a_dead_end() {
let structure = fork([[true, false], [false, false]]);
assert_eq!(
structure.exact_path(),
Some(vec![ValueIndex(1), ValueIndex(0), ValueIndex(1)])
);
}
#[test]
fn the_first_exact_path_is_the_one_returned() {
let structure = fork([[false, false], [false, false]]);
assert_eq!(
structure.exact_path(),
Some(vec![ValueIndex(0), ValueIndex(0), ValueIndex(0)])
);
}
#[test]
fn there_is_no_exact_path_when_every_branch_crosses_a_relaxed_node() {
assert_eq!(fork([[true, false], [false, true]]).exact_path(), None);
assert_eq!(fork([[true, true], [false, false]]).exact_path(), None);
assert_eq!(fork([[false, false], [true, true]]).exact_path(), None);
}
#[test]
fn a_diagram_without_variables_has_the_empty_path() {
let structure = Mdd::from_parts(vec![vec![Node::new(0, 0, false)]], vec![]);
assert_eq!(structure.exact_path(), Some(vec![]));
}
}