use super::heuristics::*;
use super::*;
use crate::modelling::*;
use rustc_hash::FxHashMap;
use std::cmp::Reverse;
use std::collections::BinaryHeap;
use std::collections::HashSet;
use std::collections::hash_map::DefaultHasher;
use std::hash::{Hash, Hasher};
use std::sync::Arc;
pub struct Compiler {
mdd: Mdd,
constraints: Vec<Box<dyn Constraint>>,
merge_heuristic: MergeHeuristic,
select_heuristic: SelectHeuristic,
top_down_properties: Vec<Vec<Vec<Box<dyn ConstraintProperty>>>>,
bottom_up_properties: Vec<Vec<Vec<Box<dyn ConstraintProperty>>>>,
}
pub(crate) fn enforce_precedence_order(
var_order: Vec<VariableIndex>,
constraints: &[Box<dyn Constraint>],
) -> Vec<VariableIndex> {
let edges: HashSet<(VariableIndex, VariableIndex)> = constraints
.iter()
.flat_map(|c| c.precedence_edges())
.collect();
if edges.is_empty() {
return var_order;
}
let rank: FxHashMap<VariableIndex, usize> =
var_order.iter().enumerate().map(|(i, &v)| (v, i)).collect();
let mut successors: FxHashMap<VariableIndex, Vec<VariableIndex>> = FxHashMap::default();
let mut in_degree: FxHashMap<VariableIndex, usize> =
var_order.iter().map(|&v| (v, 0)).collect();
for (before, after) in edges {
successors.entry(before).or_default().push(after);
*in_degree.get_mut(&after).expect(
"precedence_edges must only reference variables in this constraint's (and hence \
the MDD's) own scope",
) += 1;
}
let mut heap: BinaryHeap<Reverse<(usize, VariableIndex)>> = var_order
.iter()
.filter(|&&v| in_degree[&v] == 0)
.map(|&v| Reverse((rank[&v], v)))
.collect();
let mut result = Vec::with_capacity(var_order.len());
while let Some(Reverse((_, v))) = heap.pop() {
result.push(v);
for &succ in successors.get(&v).map(Vec::as_slice).unwrap_or(&[]) {
let deg = in_degree.get_mut(&succ).unwrap();
*deg -= 1;
if *deg == 0 {
heap.push(Reverse((rank[&succ], succ)));
}
}
}
assert_eq!(
result.len(),
var_order.len(),
"conflicting precedence requirements between constraints being compiled into the same \
MDD -- no variable ordering can satisfy every order-sensitive constraint's declared \
sequence simultaneously"
);
result
}
impl Compiler {
pub fn new(
problem: Arc<Problem>,
heuristic: CompilationHeuristic,
constraints: &[ConstraintIndex],
) -> Self {
let CompilationHeuristic {
ordering,
merge: merge_heuristic,
selection: select_heuristic,
} = heuristic;
merge_heuristic.check(&problem);
let mut in_scope = vec![false; problem.number_variables()];
let mut scope = vec![];
for constraint in constraints.iter().copied() {
for variable in problem[constraint].iter_scope() {
if !in_scope[*variable] {
scope.push(variable);
in_scope[*variable] = true;
}
}
}
let number_layers = scope.len();
let constraints = constraints
.iter()
.map(|&constraint| problem[constraint].clone() as Box<dyn Constraint>)
.collect::<Vec<Box<dyn Constraint>>>();
let mut compiler = Self {
mdd: Mdd::with_layers(problem, number_layers),
constraints,
merge_heuristic,
select_heuristic,
top_down_properties: vec![vec![]; number_layers + 1],
bottom_up_properties: vec![vec![]; number_layers + 1],
};
for layer in 0..compiler.mdd.number_layers() {
compiler.add_node(layer);
}
let var_order = ordering.get_order(&compiler.mdd.problem, &scope);
let var_order = enforce_precedence_order(var_order, &compiler.constraints);
for i in 0..compiler.constraints.len() {
compiler.constraints[i].update_variable_ordering(&var_order);
}
compiler.mdd.order = var_order;
for layer in 0..compiler.mdd.number_layers() - 1 {
let source = NodeIndex(layer, 0);
let target = NodeIndex(layer + 1, 0);
let variable = compiler.mdd.order[layer];
for value in (0..compiler.mdd.problem[variable].domain_size()).map(ValueIndex) {
compiler.add_edge(layer, source, target, value);
}
}
compiler.propagate_constraints();
if !compiler.mdd[compiler.mdd.root()].is_active()
|| !compiler.mdd[compiler.mdd.sink()].is_active()
{
compiler.unsat();
return compiler;
}
compiler.clean();
for layer in 0..compiler.mdd.number_layers() {
compiler.update_exactness(layer);
}
compiler.mdd.debug_assert_root_and_sink();
compiler
}
pub fn mdd(&self) -> &Mdd {
&self.mdd
}
pub fn into_mdd(self) -> Mdd {
self.mdd
}
fn unsat(&mut self) {
self.mdd.clear();
self.top_down_properties.clear();
self.bottom_up_properties.clear();
}
fn add_node(&mut self, layer: usize) -> NodeIndex {
let index_in_layer = self.mdd.nodes[layer].len();
let node = Node::new(layer, index_in_layer, false);
let index = NodeIndex(layer, index_in_layer);
self.mdd.nodes[layer].push(node);
let is_root = layer == 0;
let is_sink = layer == self.mdd.number_layers() - 1;
self.top_down_properties[layer].push(
(0..self.constraints.len())
.map(|i| {
if is_root {
self.constraints[i].empty_property()
} else {
self.constraints[i].identity_property()
}
})
.collect(),
);
self.bottom_up_properties[layer].push(
(0..self.constraints.len())
.map(|i| {
if is_sink {
self.constraints[i].empty_property_backward()
} else {
self.constraints[i].identity_property()
}
})
.collect(),
);
index
}
fn add_edge(&mut self, layer: usize, from: NodeIndex, to: NodeIndex, assignment: ValueIndex) {
let edge_index = EdgeIndex(layer, self.mdd.edges[layer].len());
self.mdd[from].add_child_edge(edge_index);
self.mdd[to].add_parent_edge(edge_index);
let edge = Edge::new(from, to, assignment);
self.mdd.edges[layer].push(edge);
}
pub fn number_constraints(&self) -> usize {
self.constraints.len()
}
pub fn iter_constraints(&self) -> impl Iterator<Item = &Box<dyn Constraint>> {
self.constraints.iter()
}
pub fn refine(&mut self, max_width: usize) {
if self.mdd.is_unsat() {
return;
}
let select_heuristic = self.select_heuristic;
let mut merged_lossily = false;
let mut seen_fingerprints: HashSet<u64> = HashSet::default();
seen_fingerprints.insert(self.fingerprint());
loop {
let mut any_split = false;
for layer in 1..self.mdd.nodes.len() - 1 {
let selected = if self.mdd.number_nodes_in_layer(layer) == max_width {
None
} else {
select_heuristic.select_node(self, layer)
};
if let Some(node) = selected {
any_split = true;
let new_nodes = self.split_node(node);
for &new_node in &new_nodes {
self.mdd[new_node].set_property_flag();
}
let deepest_touched = self.update_top_down(layer);
for &new_node in &new_nodes {
self.mdd[new_node].set_property_flag();
}
self.update_bottom_up(deepest_touched);
if !self.mdd[self.mdd.root()].is_active()
|| !self.mdd[self.mdd.sink()].is_active()
{
self.unsat();
return;
}
let merged = self.collapse(layer);
self.repair_after_merges(&merged);
let merged = self.merge_layer(layer, max_width);
merged_lossily |= !merged.is_empty();
self.repair_after_merges(&merged);
if !self.mdd[self.mdd.root()].is_active()
|| !self.mdd[self.mdd.sink()].is_active()
{
self.unsat();
return;
}
self.clean();
}
self.update_exactness(layer);
}
self.update_exactness(self.mdd.nodes.len() - 1);
let cycled = any_split && !seen_fingerprints.insert(self.fingerprint());
if !any_split || cycled {
let changed = self.settle();
if self.mdd.nodes.is_empty() {
return;
}
if cycled
|| !changed
|| merged_lossily
|| !seen_fingerprints.insert(self.fingerprint())
{
break;
}
}
}
}
fn settle(&mut self) -> bool {
let size = |compiler: &Self| -> (usize, usize) {
(
compiler
.mdd
.nodes
.iter()
.flatten()
.filter(|node| node.is_active())
.count(),
compiler
.mdd
.edges
.iter()
.flatten()
.filter(|edge| edge.is_active())
.count(),
)
};
let before = size(self);
loop {
let edges = size(self).1;
self.propagate_constraints();
if !self.mdd[self.mdd.root()].is_active() || !self.mdd[self.mdd.sink()].is_active() {
self.unsat();
return true;
}
if size(self).1 == edges {
break;
}
}
self.clean();
for layer in 1..self.mdd.nodes.len() - 1 {
let merged = self.collapse(layer);
self.repair_after_merges(&merged);
}
if !self.mdd[self.mdd.root()].is_active() || !self.mdd[self.mdd.sink()].is_active() {
self.unsat();
return true;
}
self.clean();
for layer in 0..self.mdd.nodes.len() {
self.update_exactness(layer);
}
size(self) != before
}
fn fingerprint(&self) -> u64 {
let mut total: u64 = 0;
for layer in 0..self.mdd.nodes.len() {
let mut layer_signature: u64 = 0;
for index in 0..self.mdd.nodes[layer].len() {
if !self.mdd.nodes[layer][index].is_active() {
continue;
}
let key = MergeKey {
td_properties: &self.top_down_properties[layer][index],
bu_properties: &self.bottom_up_properties[layer][index],
};
let mut hasher = DefaultHasher::new();
key.hash(&mut hasher);
index.hash(&mut hasher);
for edge in self.mdd.nodes[layer][index].iter_children() {
if self.mdd[edge].is_active() {
self.mdd[edge].assignment().hash(&mut hasher);
self.mdd[edge].to().hash(&mut hasher);
}
}
layer_signature ^= hasher.finish();
}
total = total
.wrapping_mul(1_000_000_007)
.wrapping_add(layer_signature);
}
total
}
fn update_exactness(&mut self, layer: usize) {
for index in 0..self.mdd.nodes[layer].len() {
let node = NodeIndex(layer, index);
if !self.mdd[node].is_active() {
continue;
}
let is_sink = layer == self.mdd.nodes.len() - 1;
let relaxed = layer != 0
&& (self.mdd[node]
.iter_parents()
.any(|edge| self.mdd[self.mdd[edge].from()].is_relaxed())
|| (!is_sink
&& !self.top_down_properties[layer][index]
.iter()
.all(|property| property.is_single_state())));
self.mdd[node].set_relaxed(relaxed);
}
}
pub(crate) fn is_splittable(&self, node: NodeIndex) -> bool {
if self.mdd[node].number_parents() < 2 {
return false;
}
(0..self.constraints.len()).any(|constraint_index| {
let mut contributions = self.mdd[node]
.iter_parents()
.map(|edge| self.property_through_edge(edge, constraint_index));
let first = contributions
.next()
.expect("a node with two parents has a first one");
contributions.any(|other| !ConstraintProperty::eq(first.as_ref(), other.as_ref()))
})
}
fn property_through_edge(
&self,
edge: EdgeIndex,
constraint_index: usize,
) -> Box<dyn ConstraintProperty> {
let NodeIndex(source_layer, source_index) = self.mdd[edge].from();
let variable = self.mdd.order[source_layer];
let assignment = self.mdd.problem[variable].value(self.mdd[edge].assignment());
let in_scope = self.constraints[constraint_index].is_layer_in_scope(source_layer);
let mut property = self.constraints[constraint_index].identity_property();
property.update(
self.top_down_properties[source_layer][source_index][constraint_index].as_ref(),
assignment,
in_scope,
);
property
}
fn split_node(&mut self, node: NodeIndex) -> Vec<NodeIndex> {
let mut nodes = vec![node];
let NodeIndex(layer, _) = node;
let n = self.mdd[node].number_parents();
let outgoing_assignments = self.mdd[node]
.iter_children()
.filter(|edge| self.mdd[*edge].is_active())
.map(|edge| (self.mdd[edge].to(), self.mdd[edge].assignment()))
.collect::<Vec<(NodeIndex, ValueIndex)>>();
for i in (1..n).rev() {
let new_node = self.add_node(layer);
nodes.push(new_node);
let edge = self.mdd[node].parent_edge_at(i);
let from = self.mdd[edge].from();
let assignment = self.mdd[edge].assignment();
self.add_edge(layer - 1, from, new_node, assignment);
for (child, outgoing_assignment) in outgoing_assignments.iter().copied() {
self.add_edge(layer, new_node, child, outgoing_assignment);
}
self.mdd[edge].deactivate();
self.mdd[node].swap_remove_parent_edge(i);
}
nodes
}
pub(crate) fn propagate_constraints(&mut self) {
self.update_top_down_properties();
self.update_bottom_up_properties_and_filter_edges();
}
fn update_top_down(&mut self, start_layer: usize) -> usize {
let mut deepest_changed_layer = start_layer.max(1) - 1;
for layer in start_layer.max(1)..self.mdd.nodes.len() {
let parent_variable = self.mdd.order[layer - 1];
let mut any_changed = false;
for index in 0..self.mdd.nodes[layer].len() {
let target = NodeIndex(layer, index);
if !self.mdd[target].is_property_flag() {
continue;
}
self.mdd[target].unset_property_flag();
if !self.mdd[target].is_active() {
continue;
}
let mut changed = false;
for constraint_index in 0..self.constraints.len() {
let new_property =
self.fold_property_over_parents(target, parent_variable, constraint_index);
if !ConstraintProperty::eq(
new_property.as_ref(),
self.top_down_properties[layer][index][constraint_index].as_ref(),
) {
changed = true;
}
self.top_down_properties[layer][index][constraint_index] = new_property;
}
if !changed {
continue;
}
any_changed = true;
deepest_changed_layer = deepest_changed_layer.max(layer);
if layer < self.mdd.nodes.len() - 1 {
let children_before: Vec<NodeIndex> = self.mdd[target]
.iter_children()
.map(|edge| self.mdd[edge].to())
.collect();
let variable = self.mdd.order[layer];
for constraint_index in 0..self.constraints.len() {
if self.constraints[constraint_index].is_layer_in_scope(layer) {
self.filter_invalid_edges(target, variable, constraint_index);
}
}
for child in children_before {
if self.mdd[child].is_active() {
self.mdd[child].set_property_flag();
}
}
}
self.mdd[target].set_property_flag();
}
if !any_changed && !self.has_flagged_node(layer + 1) {
break;
}
}
deepest_changed_layer
}
fn update_bottom_up(&mut self, start_layer: usize) {
for layer in (0..=start_layer.min(self.mdd.nodes.len() - 2)).rev() {
let variable = self.mdd.order[layer];
let mut any_changed = false;
for index in 0..self.mdd.nodes[layer].len() {
let target = NodeIndex(layer, index);
if !self.mdd[target].is_property_flag() {
continue;
}
self.mdd[target].unset_property_flag();
if !self.mdd[target].is_active() {
continue;
}
let mut changed = false;
for constraint_index in 0..self.constraints.len() {
let new_property =
self.fold_property_over_children(target, variable, constraint_index);
if !ConstraintProperty::eq(
new_property.as_ref(),
self.bottom_up_properties[layer][index][constraint_index].as_ref(),
) {
changed = true;
}
self.bottom_up_properties[layer][index][constraint_index] = new_property;
}
let parents_before: Vec<NodeIndex> = if layer > 0 {
self.mdd[target]
.iter_parents()
.map(|edge| self.mdd[edge].from())
.collect()
} else {
Vec::new()
};
for constraint_index in 0..self.constraints.len() {
if self.constraints[constraint_index].is_layer_in_scope(layer) {
self.filter_invalid_edges(target, variable, constraint_index);
}
}
let target_removed = !self.mdd[target].is_active();
if !changed && !target_removed {
continue;
}
any_changed = true;
{
for parent in parents_before {
if self.mdd[parent].is_active() {
self.mdd[parent].set_property_flag();
}
}
}
}
if !any_changed && (layer == 0 || !self.has_flagged_node(layer - 1)) {
break;
}
}
}
fn has_flagged_node(&self, layer: usize) -> bool {
self.mdd
.nodes
.get(layer)
.is_some_and(|nodes| nodes.iter().any(|node| node.is_property_flag()))
}
fn update_top_down_properties(&mut self) {
for layer in 1..self.mdd.nodes.len() {
let variable = self.mdd.order[layer - 1];
for i in 0..self.mdd.nodes[layer].len() {
let target = NodeIndex(layer, i);
for constraint_index in 0..self.constraints.len() {
self.top_down_properties[layer][i][constraint_index] =
self.fold_property_over_parents(target, variable, constraint_index);
}
}
}
}
fn fold_property_over_parents(
&self,
target: NodeIndex,
variable: VariableIndex,
constraint_index: usize,
) -> Box<dyn ConstraintProperty> {
let mut property = self.constraints[constraint_index].identity_property();
for j in 0..self.mdd[target].number_parents() {
let edge = self.mdd[target].parent_edge_at(j);
let NodeIndex(source_layer, source_index) = self.mdd[edge].from();
let in_scope = self.constraints[constraint_index].is_layer_in_scope(source_layer);
let assignment = self.mdd.problem[variable].value(self.mdd[edge].assignment());
let parent_property =
self.top_down_properties[source_layer][source_index][constraint_index].as_ref();
property.update(parent_property, assignment, in_scope);
}
property
}
fn update_bottom_up_properties_and_filter_edges(&mut self) {
for layer in (0..self.mdd.nodes.len() - 1).rev() {
let variable = self.mdd.order[layer];
for node_index in 0..self.mdd.nodes[layer].len() {
let target = NodeIndex(layer, node_index);
if !self.mdd[target].is_active() {
continue;
}
for constraint_index in 0..self.constraints.len() {
self.bottom_up_properties[layer][node_index][constraint_index] =
self.fold_property_over_children(target, variable, constraint_index);
if self.constraints[constraint_index].is_layer_in_scope(layer) {
self.filter_invalid_edges(target, variable, constraint_index);
}
}
}
}
}
fn fold_property_over_children(
&self,
target: NodeIndex,
variable: VariableIndex,
constraint_index: usize,
) -> Box<dyn ConstraintProperty> {
let NodeIndex(layer, _) = target;
let in_scope = self.constraints[constraint_index].is_layer_in_scope(layer);
let mut property = self.constraints[constraint_index].identity_property();
for edge_index in 0..self.mdd[target].number_children() {
let edge = self.mdd[target].child_edge_at(edge_index);
let NodeIndex(child_layer, child_index) = self.mdd[edge].to();
let assignment = self.mdd.problem[variable].value(self.mdd[edge].assignment());
let child_property =
self.bottom_up_properties[child_layer][child_index][constraint_index].as_ref();
property.update_backward(child_property, assignment, in_scope);
}
property
}
fn filter_invalid_edges(
&mut self,
target: NodeIndex,
variable: VariableIndex,
constraint_index: usize,
) {
let NodeIndex(layer, node_index) = target;
for edge_index in (0..self.mdd[target].number_children()).rev() {
let edge = self.mdd[target].child_edge_at(edge_index);
let child = self.mdd[edge].to();
let NodeIndex(child_layer, child_index) = child;
let assignment = self.mdd.problem[variable].value(self.mdd[edge].assignment());
let parent_property =
self.top_down_properties[layer][node_index][constraint_index].as_ref();
let child_property =
self.bottom_up_properties[child_layer][child_index][constraint_index].as_ref();
let invalid = self.constraints[constraint_index].is_assignment_invalid(
parent_property,
child_property,
layer,
assignment,
);
if !invalid {
continue;
}
self.mdd[target].swap_remove_child_edge(edge_index);
if self.mdd[target].number_children() == 0 {
self.remove_node(target);
}
self.mdd[child].remove_parent_edge(edge);
if self.mdd[child].number_parents() == 0 {
self.remove_node(child);
}
self.mdd[edge].deactivate();
}
}
fn remove_node(&mut self, node: NodeIndex) {
if !self.mdd[node].is_active() {
return;
}
self.mdd[node].deactivate();
for i in 0..self.mdd[node].number_parents() {
let edge = self.mdd[node].parent_edge_at(i);
self.mdd[edge].deactivate();
let parent = self.mdd[edge].from();
self.mdd[parent].remove_child_edge(edge);
if self.mdd[parent].number_children() == 0 {
self.remove_node(parent);
}
}
for i in 0..self.mdd[node].number_children() {
let edge = self.mdd[node].child_edge_at(i);
self.mdd[edge].deactivate();
let child = self.mdd[edge].to();
self.mdd[child].remove_parent_edge(edge);
if self.mdd[child].number_parents() == 0 {
self.remove_node(child);
}
}
}
fn collapse(&mut self, layer: usize) -> Vec<NodeIndex> {
let mut map: FxHashMap<MergeKey, NodeIndex> = FxHashMap::default();
let mut merges: Vec<(NodeIndex, NodeIndex)> = vec![];
for index in 0..self.mdd.nodes[layer].len() {
let node = NodeIndex(layer, index);
if !self.mdd[node].is_active() {
continue;
}
let key = MergeKey {
td_properties: &self.top_down_properties[layer][index],
bu_properties: &self.bottom_up_properties[layer][index],
};
if let Some(&primary_node) = map.get(&key) {
merges.push((node, primary_node));
} else {
map.insert(key, node);
}
}
let mut merged = vec![];
for (node, primary_node) in merges {
merged.extend(self.merge_nodes(node, primary_node));
}
merged
}
fn merge_layer(&mut self, layer: usize, max_width: usize) -> Vec<NodeIndex> {
let active_nodes = self
.mdd
.nodes_in_layer(layer)
.filter(|&node| self.mdd[node].is_active())
.count();
if active_nodes <= max_width {
return vec![];
}
let groups = self.merge_heuristic.group_nodes(self, layer, max_width);
let mut merged = vec![];
for group in groups {
if let Some((&into, froms)) = group.split_first() {
for &from in froms {
merged.extend(self.merge_nodes(from, into));
}
}
}
merged
}
fn merge_nodes(&mut self, from: NodeIndex, into: NodeIndex) -> Vec<NodeIndex> {
let mut worklist = vec![(from, into)];
let mut took_over = vec![];
let mut absorbed = FxHashMap::<NodeIndex, NodeIndex>::default();
while let Some((from, into)) = worklist.pop() {
let resolve = |mut node: NodeIndex| {
while let Some(&next) = absorbed.get(&node) {
node = next;
}
node
};
let (from, into) = (resolve(from), resolve(into));
if from == into {
continue;
}
took_over.push(into);
for i in 0..self.mdd[from].number_parents() {
let edge = self.mdd[from].parent_edge_at(i);
self.mdd[edge].set_to(into);
self.mdd[into].add_parent_edge(edge);
}
let mut existing_children = FxHashMap::<ValueIndex, NodeIndex>::default();
for i in 0..self.mdd[into].number_children() {
let edge = self.mdd[into].child_edge_at(i);
if !self.mdd[edge].is_active() {
continue;
}
existing_children.insert(self.mdd[edge].assignment(), self.mdd[edge].to());
}
for i in 0..self.mdd[from].number_children() {
let edge = self.mdd[from].child_edge_at(i);
if !self.mdd[edge].is_active() {
continue;
}
let assignment = self.mdd[edge].assignment();
let child = self.mdd[edge].to();
match existing_children.get(&assignment).copied() {
None => {
self.mdd[edge].set_from(into);
self.mdd[into].add_child_edge(edge);
existing_children.insert(assignment, child);
}
Some(existing_child) if existing_child == child => {
self.mdd[child].remove_parent_edge(edge);
self.mdd[edge].deactivate();
}
Some(existing_child) => {
self.mdd[child].remove_parent_edge(edge);
self.mdd[edge].deactivate();
worklist.push((child, existing_child));
}
}
}
Self::merge_properties(&mut self.top_down_properties[from.0], from.1, into.1);
Self::merge_properties(&mut self.bottom_up_properties[from.0], from.1, into.1);
self.mdd[from].deactivate();
absorbed.insert(from, into);
}
took_over
}
fn repair_after_merges(&mut self, took_over: &[NodeIndex]) {
let took_over: Vec<NodeIndex> = took_over
.iter()
.copied()
.filter(|&node| self.mdd[node].is_active())
.collect();
let (Some(first), Some(last)) = (
took_over.iter().map(|node| node.0).min(),
took_over.iter().map(|node| node.0).max(),
) else {
return;
};
for &node in &took_over {
for edge in self.mdd[node].iter_children().collect::<Vec<_>>() {
let child = self.mdd[edge].to();
if self.mdd[edge].is_active() && self.mdd[child].is_active() {
self.mdd[child].set_property_flag();
}
}
}
let deepest_changed = self.update_top_down(first + 1).max(last);
for &node in &took_over {
if !self.mdd[node].is_active() {
continue;
}
self.mdd[node].set_property_flag();
for edge in self.mdd[node].iter_parents().collect::<Vec<_>>() {
let parent = self.mdd[edge].from();
if self.mdd[edge].is_active() && self.mdd[parent].is_active() {
self.mdd[parent].set_property_flag();
}
}
}
self.update_bottom_up(deepest_changed);
}
fn merge_properties(
properties: &mut [Vec<Box<dyn ConstraintProperty>>],
from_index: usize,
into_index: usize,
) {
let hi = from_index.max(into_index);
let lo = from_index.min(into_index);
let (left, right) = properties.split_at_mut(hi);
let (from_properties, into_properties) = if from_index < into_index {
(&left[lo], &mut right[0])
} else {
(&right[0], &mut left[lo])
};
for (into_property, from_property) in into_properties.iter_mut().zip(from_properties.iter())
{
into_property.merge(from_property.as_ref());
}
}
fn clean(&mut self) {
let mut map_node_index = FxHashMap::<NodeIndex, NodeIndex>::default();
let (root, sink) = (self.mdd.root(), self.mdd.sink());
map_node_index.insert(root, root);
map_node_index.insert(sink, sink);
for layer in 1..self.mdd.nodes.len() - 1 {
let mut new_index = 0;
for index in 0..self.mdd.nodes[layer].len() {
if self.mdd.nodes[layer][index].is_active() {
map_node_index.insert(NodeIndex(layer, index), NodeIndex(layer, new_index));
self.mdd.nodes[layer].swap(new_index, index);
self.top_down_properties[layer].swap(new_index, index);
self.bottom_up_properties[layer].swap(new_index, index);
new_index += 1;
}
}
self.mdd.nodes[layer].truncate(new_index);
self.top_down_properties[layer].truncate(new_index);
self.bottom_up_properties[layer].truncate(new_index);
}
let mut map_edge_index = FxHashMap::<EdgeIndex, EdgeIndex>::default();
for layer in 0..self.mdd.edges.len() {
let mut new_index = 0;
for index in 0..self.mdd.edges[layer].len() {
let from = self.mdd.edges[layer][index].from();
let to = self.mdd.edges[layer][index].to();
if self.mdd.edges[layer][index].is_active()
&& map_node_index.contains_key(&from)
&& map_node_index.contains_key(&to)
{
map_edge_index.insert(EdgeIndex(layer, index), EdgeIndex(layer, new_index));
self.mdd.edges[layer].swap(new_index, index);
new_index += 1;
}
}
self.mdd.edges[layer].truncate(new_index);
}
for layer in 0..self.mdd.nodes.len() {
for index in 0..self.mdd.nodes[layer].len() {
self.mdd.nodes[layer][index].update_edge_indices(&map_edge_index);
}
if layer > 0 {
for index in 0..self.mdd.edges[layer - 1].len() {
self.mdd.edges[layer - 1][index].update_node_indices(&map_node_index);
}
}
}
}
pub(crate) fn top_down_properties(&self, node: NodeIndex) -> &[Box<dyn ConstraintProperty>] {
&self.top_down_properties[node.0][node.1]
}
pub(crate) fn bottom_up_properties(&self, node: NodeIndex) -> &[Box<dyn ConstraintProperty>] {
&self.bottom_up_properties[node.0][node.1]
}
}
#[cfg(test)]
pub mod test_mdd {
use crate::mdd::heuristics::*;
use crate::mdd::*;
use crate::modelling::*;
use num_bigint::BigUint;
use std::sync::Arc;
pub fn get_all_solutions(mdd: &Mdd) -> Vec<Vec<isize>> {
let mut solutions: Vec<Vec<isize>> = vec![];
let mut current_solution: Vec<isize> = vec![0; mdd.number_layers() - 1];
let root = NodeIndex(0, 0);
_get_all_solutions(mdd, root, &mut solutions, &mut current_solution);
solutions
}
fn _get_all_solutions(
mdd: &Mdd,
node: NodeIndex,
solutions: &mut Vec<Vec<isize>>,
current_solution: &mut Vec<isize>,
) {
let NodeIndex(layer, _) = node;
if layer == mdd.number_layers() - 1 {
solutions.push(current_solution.clone());
return;
}
let variable = mdd.decision_at_layer(layer);
for edge in mdd[node].iter_children() {
if mdd[edge].is_active() {
let child = mdd[edge].to();
let assignment = mdd.problem[variable].value(mdd[edge].assignment());
current_solution[*variable] = assignment;
_get_all_solutions(mdd, child, solutions, current_solution);
}
}
}
pub fn is_solution(solution: Vec<isize>, all_solutions: &[Vec<isize>]) -> bool {
for sol in all_solutions.iter() {
let mut eq = true;
for i in 0..sol.len() {
if sol[i] != solution[i] {
eq = false;
break;
}
}
if eq {
return true;
}
}
false
}
#[test]
pub fn mdd_creation() {
let mut problem = Problem::default();
let x = problem.add_variable(vec![0, 1]);
let y = problem.add_variable(vec![0, 1]);
let z = problem.add_variable(vec![0, 1, 2]);
gcc(&mut problem, vec![x, y, z], vec![]);
let problem = Arc::new(problem);
let constraints: Vec<ConstraintIndex> = problem.iter_constraints().collect();
let compiler = Compiler::new(
problem,
CompilationHeuristic {
ordering: OrderingHeuristic::MinDomMaxLinked,
merge: MergeHeuristic::LessRelaxed,
selection: SelectHeuristic::Greedy,
},
&constraints,
);
let solutions = get_all_solutions(compiler.mdd());
assert_eq!(solutions.len(), 2 * 2 * 3);
assert!(is_solution(vec![0, 0, 0], &solutions));
assert!(is_solution(vec![0, 0, 1], &solutions));
assert!(is_solution(vec![0, 0, 2], &solutions));
assert!(is_solution(vec![0, 1, 0], &solutions));
assert!(is_solution(vec![0, 1, 1], &solutions));
assert!(is_solution(vec![0, 1, 2], &solutions));
assert!(is_solution(vec![1, 0, 0], &solutions));
assert!(is_solution(vec![1, 0, 1], &solutions));
assert!(is_solution(vec![1, 0, 2], &solutions));
assert!(is_solution(vec![1, 1, 0], &solutions));
assert!(is_solution(vec![1, 1, 1], &solutions));
assert!(is_solution(vec![1, 1, 2], &solutions));
}
#[test]
pub fn min_dom_max_linked_repairs_order_for_regular_constraints() {
let mut problem = Problem::default();
let vars: Vec<VariableIndex> = (0..4).map(|_| problem.add_variable(vec![0, 1])).collect();
regular(
&mut problem,
vars.clone(),
vec![vec![Some(0), Some(0)]],
0,
vec![0],
);
for _ in 0..3 {
let dummy = problem.add_variable(vec![0, 1]);
not_equals(&mut problem, dummy, vars[3]);
}
let problem = Arc::new(problem);
let constraints: Vec<ConstraintIndex> = problem.iter_constraints().collect();
let compiler = Compiler::new(
problem,
CompilationHeuristic {
ordering: OrderingHeuristic::MinDomMaxLinked,
merge: MergeHeuristic::LessRelaxed,
selection: SelectHeuristic::Greedy,
},
&constraints,
);
let positions: Vec<usize> = (0..compiler.mdd().number_layers() - 1)
.map(|layer| (compiler.mdd().decision_at_layer(layer), layer))
.filter(|(v, _)| vars.contains(v))
.map(|(_, layer)| layer)
.collect();
assert_eq!(positions.len(), vars.len());
assert!(
positions.windows(2).all(|w| w[0] < w[1]),
"Regular's declared scope order was not respected: layers {positions:?}"
);
}
#[test]
#[should_panic(expected = "conflicting precedence requirements")]
pub fn conflicting_regular_orderings_panics_with_a_clear_message() {
let mut problem = Problem::default();
let v0 = problem.add_variable(vec![0, 1]);
let v1 = problem.add_variable(vec![0, 1]);
let trivial = vec![vec![Some(0), Some(0)]];
regular(&mut problem, vec![v0, v1], trivial.clone(), 0, vec![0]);
regular(&mut problem, vec![v1, v0], trivial, 0, vec![0]);
let problem = Arc::new(problem);
let constraints: Vec<ConstraintIndex> = problem.iter_constraints().collect();
let _ = Compiler::new(
problem,
CompilationHeuristic {
ordering: OrderingHeuristic::MinDomMaxLinked,
merge: MergeHeuristic::LessRelaxed,
selection: SelectHeuristic::Greedy,
},
&constraints,
);
}
#[test]
pub fn merge_nodes_merges_children_that_collide_on_the_same_label() {
let mut problem = Problem::default();
let x = problem.add_variable(vec![0, 1]);
let y = problem.add_variable(vec![0, 1]);
gcc(&mut problem, vec![x, y], vec![]);
let problem = Arc::new(problem);
let constraints: Vec<ConstraintIndex> = problem.iter_constraints().collect();
let mut compiler = Compiler::new(
problem,
CompilationHeuristic {
ordering: OrderingHeuristic::MinDomMaxLinked,
merge: MergeHeuristic::LessRelaxed,
selection: SelectHeuristic::Greedy,
},
&constraints,
);
let into = NodeIndex(1, 0);
let c1 = NodeIndex(2, 0);
let from = compiler.add_node(1);
let c2 = compiler.add_node(2);
let shared_assignment = ValueIndex(0);
compiler.add_edge(1, from, c2, shared_assignment);
compiler.merge_nodes(from, into);
assert!(!compiler.mdd()[from].is_active());
assert!(compiler.mdd()[into].is_active());
assert!(compiler.mdd()[c1].is_active());
assert!(!compiler.mdd()[c2].is_active());
let mut seen_assignments = std::collections::HashSet::new();
for edge in compiler.mdd()[into].iter_children() {
if !compiler.mdd()[edge].is_active() {
continue;
}
assert!(seen_assignments.insert(compiler.mdd()[edge].assignment()));
}
assert_eq!(seen_assignments.len(), 2);
}
#[test]
pub fn incremental_refine_matches_full_recompute_on_all_different() {
for n in 3..=7 {
let mut problem = Problem::default();
let vars: Vec<_> = (0..n)
.map(|_| problem.add_variable((0..n as isize).collect()))
.collect();
all_different(&mut problem, vars);
let problem = Arc::new(problem);
let constraints: Vec<ConstraintIndex> = problem.iter_constraints().collect();
let mut compiler = Compiler::new(
problem,
CompilationHeuristic {
ordering: OrderingHeuristic::MinDomMaxLinked,
merge: MergeHeuristic::LessRelaxed,
selection: SelectHeuristic::Greedy,
},
&constraints,
);
compiler.refine(usize::MAX);
let solutions = get_all_solutions(compiler.mdd());
let mut factorial = 1usize;
for k in 1..=n {
factorial *= k;
}
assert_eq!(
solutions.len(),
factorial,
"n={} produced {} solutions, expected {} (all permutations)",
n,
solutions.len(),
factorial
);
let mut seen = std::collections::HashSet::new();
for s in &solutions {
assert!(
seen.insert(s.clone()),
"duplicate solution {:?} for n={}",
s,
n
);
}
}
}
#[test]
pub fn merging_follows_nodes_absorbed_earlier_in_the_same_cascade() {
let mut problem = Problem::default();
let vars = problem.add_variables(6, (0..6).collect());
all_different(&mut problem, vars);
let problem = Arc::new(problem);
let constraints: Vec<ConstraintIndex> = problem.iter_constraints().collect();
let mut compiler = Compiler::new(
problem,
CompilationHeuristic {
ordering: OrderingHeuristic::MinDomMaxLinked,
merge: MergeHeuristic::StateSimilarity,
selection: SelectHeuristic::Greedy,
},
&constraints,
);
compiler.refine(4);
assert!(compiler.mdd().count_solutions() >= BigUint::from(720u32));
}
fn permutations_of(n: usize) -> Vec<Vec<isize>> {
fn go(n: usize, used: &mut Vec<bool>, current: &mut Vec<isize>, all: &mut Vec<Vec<isize>>) {
if current.len() == n {
all.push(current.clone());
return;
}
for value in 0..n {
if !used[value] {
used[value] = true;
current.push(value as isize);
go(n, used, current, all);
current.pop();
used[value] = false;
}
}
}
let mut used = vec![false; n];
let mut current = vec![];
let mut all = vec![];
go(n, &mut used, &mut current, &mut all);
all
}
#[test]
pub fn merged_relaxed_mdd_still_contains_every_true_all_different_solution() {
for n in 4..=6 {
for max_width in [1usize, 2, 3] {
let mut problem = Problem::default();
let vars: Vec<_> = (0..n)
.map(|_| problem.add_variable((0..n as isize).collect()))
.collect();
all_different(&mut problem, vars.clone());
let problem = Arc::new(problem);
let constraints: Vec<ConstraintIndex> = problem.iter_constraints().collect();
let mut compiler = Compiler::new(
problem,
CompilationHeuristic {
ordering: OrderingHeuristic::MinDomMaxLinked,
merge: MergeHeuristic::LessRelaxed,
selection: SelectHeuristic::Greedy,
},
&constraints,
);
compiler.refine(max_width);
let candidate_solutions = get_all_solutions(compiler.mdd());
for solution in permutations_of(n) {
assert!(
is_solution(solution.clone(), &candidate_solutions),
"n={} max_width={} true all-different solution {:?} missing from relaxed mdd -- unsound property merge",
n,
max_width,
solution
);
}
}
}
}
fn all_assignments(n: usize, domain_size: usize) -> Vec<Vec<isize>> {
let mut all = vec![vec![]];
for _ in 0..n {
let mut next = vec![];
for prefix in all.iter() {
for v in 0..domain_size as isize {
let mut extended = prefix.clone();
extended.push(v);
next.push(extended);
}
}
all = next;
}
all
}
#[test]
pub fn state_similarity_merge_caps_width_and_stays_sound_for_gcc() {
let n = 5;
let candidates = all_assignments(n, n);
for max_width in [1usize, 2, 3] {
let mut problem = Problem::default();
let vars: Vec<_> = (0..n)
.map(|_| problem.add_variable((0..n as isize).collect()))
.collect();
let bounds: Vec<(isize, usize, usize)> = (0..n as isize).map(|v| (v, 0, 2)).collect();
gcc(&mut problem, vars.clone(), bounds);
let problem = Arc::new(problem);
let constraints: Vec<ConstraintIndex> = problem.iter_constraints().collect();
let mut compiler = Compiler::new(
Arc::clone(&problem),
CompilationHeuristic {
ordering: OrderingHeuristic::MinDomMaxLinked,
merge: MergeHeuristic::StateSimilarity,
selection: SelectHeuristic::Greedy,
},
&constraints,
);
compiler.refine(max_width);
for layer in 1..compiler.mdd().number_layers() {
assert!(
compiler.mdd().number_nodes_in_layer(layer) <= max_width,
"layer {} has {} nodes, exceeding max_width={}",
layer,
compiler.mdd().number_nodes_in_layer(layer),
max_width
);
}
let candidate_solutions = get_all_solutions(compiler.mdd());
for assignment in candidates.iter() {
if problem.is_solution(assignment) {
assert!(
is_solution(assignment.clone(), &candidate_solutions),
"max_width={} true gcc solution {:?} missing from relaxed mdd -- unsound state-similarity merge",
max_width,
assignment
);
}
}
}
}
#[test]
pub fn count_solutions_matches_brute_force_when_exact() {
let n = 5;
let candidates = all_assignments(n, n);
let mut problem = Problem::default();
let vars: Vec<_> = (0..n)
.map(|_| problem.add_variable((0..n as isize).collect()))
.collect();
let bounds: Vec<(isize, usize, usize)> = (0..n as isize).map(|v| (v, 0, 2)).collect();
gcc(&mut problem, vars.clone(), bounds);
let problem = Arc::new(problem);
let constraints: Vec<ConstraintIndex> = problem.iter_constraints().collect();
let mut compiler = Compiler::new(
Arc::clone(&problem),
CompilationHeuristic {
ordering: OrderingHeuristic::MinDomMaxLinked,
merge: MergeHeuristic::LessRelaxed,
selection: SelectHeuristic::Greedy,
},
&constraints,
);
compiler.refine(usize::MAX);
let true_count = candidates
.iter()
.filter(|assignment| problem.is_solution(assignment))
.count();
let path_count = get_all_solutions(compiler.mdd()).len();
assert_eq!(
path_count, true_count,
"get_all_solutions found {} but brute force found {}",
path_count, true_count
);
assert_eq!(
compiler.mdd().count_solutions(),
BigUint::from(true_count),
"count_solutions() should exactly match the brute-force count once compiled exactly \
(no merging means the diagram is tree-shaped: every path is a distinct assignment)"
);
}
#[test]
pub fn count_solutions_is_zero_when_unsat() {
let mut problem = Problem::default();
let vars = problem.add_variables(2, vec![1]);
gcc(&mut problem, vars, vec![(1, 0, 1)]); let problem = Arc::new(problem);
let constraints: Vec<ConstraintIndex> = problem.iter_constraints().collect();
let compiler = Compiler::new(
problem,
CompilationHeuristic {
ordering: OrderingHeuristic::MinDomMaxLinked,
merge: MergeHeuristic::LessRelaxed,
selection: SelectHeuristic::Greedy,
},
&constraints,
);
assert!(compiler.mdd().is_unsat());
assert_eq!(compiler.mdd().count_solutions(), BigUint::from(0u32));
}
#[test]
pub fn count_solutions_upper_bounds_the_true_count_under_relaxed_width() {
let n = 5;
let candidates = all_assignments(n, n);
for max_width in [1usize, 2, 3] {
let mut problem = Problem::default();
let vars: Vec<_> = (0..n)
.map(|_| problem.add_variable((0..n as isize).collect()))
.collect();
let bounds: Vec<(isize, usize, usize)> = (0..n as isize).map(|v| (v, 0, 2)).collect();
gcc(&mut problem, vars.clone(), bounds);
let problem = Arc::new(problem);
let constraints: Vec<ConstraintIndex> = problem.iter_constraints().collect();
let mut compiler = Compiler::new(
Arc::clone(&problem),
CompilationHeuristic {
ordering: OrderingHeuristic::MinDomMaxLinked,
merge: MergeHeuristic::StateSimilarity,
selection: SelectHeuristic::Greedy,
},
&constraints,
);
compiler.refine(max_width);
let true_count = candidates
.iter()
.filter(|assignment| problem.is_solution(assignment))
.count();
assert!(
compiler.mdd().count_solutions() >= BigUint::from(true_count),
"max_width={} count_solutions()={} is less than the true count {} -- unsound relaxation",
max_width,
compiler.mdd().count_solutions(),
true_count
);
}
}
#[test]
fn merging_does_not_read_removed_edges() {
let mut problem = Problem::default();
let vars = problem.add_variables(3, vec![0, 1, 2]);
at_least(&mut problem, vars, vec![0, 1], 2);
let problem = Arc::new(problem);
let constraints: Vec<ConstraintIndex> = problem.iter_constraints().collect();
let mut compiler = Compiler::new(
Arc::clone(&problem),
CompilationHeuristic {
ordering: OrderingHeuristic::Custom(vec![2, 1, 0]),
merge: MergeHeuristic::LessRelaxed,
selection: SelectHeuristic::Greedy,
},
&constraints,
);
compiler.refine(usize::MAX);
let solutions = get_all_solutions(compiler.mdd());
for x in 0..3 {
for y in 0..3 {
for z in 0..3 {
let assignment = vec![x, y, z];
let satisfied = assignment.iter().filter(|&&v| v < 2).count() >= 2;
assert_eq!(
is_solution(assignment.clone(), &solutions),
satisfied,
"{assignment:?}"
);
}
}
}
}
fn unsatisfiable() -> Compiler {
let mut problem = Problem::default();
let vars = problem.add_variables(3, vec![0, 1]);
all_different(&mut problem, vars);
let problem = Arc::new(problem);
let constraints: Vec<ConstraintIndex> = problem.iter_constraints().collect();
Compiler::new(
problem,
CompilationHeuristic {
ordering: OrderingHeuristic::MinDomMaxLinked,
merge: MergeHeuristic::LessRelaxed,
selection: SelectHeuristic::Greedy,
},
&constraints,
)
}
#[test]
fn an_unsatisfiable_diagram_holds_nothing() {
let compiler = unsatisfiable();
let mdd = compiler.mdd();
assert!(mdd.is_unsat());
assert!(mdd.nodes.is_empty());
assert!(mdd.edges.is_empty());
assert!(mdd.order.is_empty());
assert!(compiler.top_down_properties.is_empty());
assert!(compiler.bottom_up_properties.is_empty());
assert_eq!(mdd.number_layers(), 0);
assert_eq!(mdd.get_solution(), None);
assert_eq!(format!("{mdd:?}"), "UNSAT");
}
#[test]
fn refining_an_unsatisfiable_diagram_changes_nothing() {
let mut compiler = unsatisfiable();
compiler.refine(usize::MAX);
compiler.refine(2);
assert!(compiler.mdd().is_unsat());
assert!(compiler.mdd().nodes.is_empty());
}
#[test]
fn the_root_and_the_sink_stay_alone_in_their_layer_at_every_width() {
let mut problem = Problem::default();
let vars = problem.add_variables(4, vec![0, 1, 2, 3]);
all_different(&mut problem, vars);
let problem = Arc::new(problem);
let constraints: Vec<ConstraintIndex> = problem.iter_constraints().collect();
for width in [1, 2, 3, usize::MAX] {
let mut compiler = Compiler::new(
Arc::clone(&problem),
CompilationHeuristic {
ordering: OrderingHeuristic::MinDomMaxLinked,
merge: MergeHeuristic::LessRelaxed,
selection: SelectHeuristic::Greedy,
},
&constraints,
);
compiler.refine(width);
compiler.mdd().debug_assert_root_and_sink();
let last_layer = compiler.mdd().number_layers() - 1;
assert_eq!(compiler.mdd().root(), NodeIndex(0, 0), "width {width}");
assert_eq!(
compiler.mdd().sink(),
NodeIndex(last_layer, 0),
"width {width}"
);
assert_eq!(compiler.mdd().number_nodes_in_layer(0), 1, "width {width}");
assert_eq!(
compiler.mdd().number_nodes_in_layer(last_layer),
1,
"width {width}"
);
}
}
fn five_different_variables() -> Compiler {
let mut problem = Problem::default();
let vars = problem.add_variables(5, vec![0, 1, 2, 3, 4]);
let constraint = crate::constraints::all_different(&mut problem, vars);
Compiler::new(
Arc::new(problem),
CompilationHeuristic {
ordering: OrderingHeuristic::MinDomMaxLinked,
merge: MergeHeuristic::LessRelaxed,
selection: SelectHeuristic::Greedy,
},
&[constraint],
)
}
#[test]
fn refining_with_growing_widths_keeps_every_solution_and_respects_the_width() {
let mut compiler = five_different_variables();
assert!(compiler.mdd().count_solutions() >= 120u32.into());
for width in [1, 2, 4, 8, 16] {
compiler.refine(width);
let mdd = compiler.mdd();
let layers = mdd.number_layers();
assert!((0..layers).all(|layer| mdd.number_nodes_in_layer(layer) <= width));
assert!(mdd.count_solutions() >= 120u32.into());
}
}
fn is_a_path(mdd: &Mdd, assignment: &[isize]) -> bool {
let mut node = mdd.root();
for layer in 0..mdd.number_layers() - 1 {
let variable = mdd.decision_at_layer(layer);
let next = mdd[node].iter_children().find(|&edge| {
mdd[edge].is_active()
&& mdd.problem()[variable].value(mdd[edge].assignment())
== assignment[variable.0]
});
match next {
Some(edge) => node = mdd[edge].to(),
None => return false,
}
}
true
}
#[test]
fn a_solution_names_the_variables_in_the_branching_order() {
let mut problem = Problem::default();
let vars = problem.add_variables(4, vec![0, 1, 2]);
let constraint = not_equals(&mut problem, vars[3], vars[1]);
let mut compiler = Compiler::new(
Arc::new(problem),
CompilationHeuristic {
ordering: OrderingHeuristic::Custom(vec![3, 1]),
merge: MergeHeuristic::LessRelaxed,
selection: SelectHeuristic::Greedy,
},
&[constraint],
);
compiler.refine(usize::MAX);
let (values, variables) = compiler.mdd().get_solution().expect("satisfiable");
assert_eq!(variables, vec![VariableIndex(3), VariableIndex(1)]);
assert_eq!(values.len(), 2);
assert_ne!(values[0], values[1]);
}
fn assert_properties_cover_the_paths(compiler: &mut Compiler, same: bool, context: &str) {
let stored_top_down = compiler.top_down_properties.clone();
let stored_bottom_up = compiler.bottom_up_properties.clone();
compiler.update_top_down_properties();
for layer in (0..compiler.mdd.nodes.len() - 1).rev() {
let variable = compiler.mdd.order[layer];
for index in 0..compiler.mdd.nodes[layer].len() {
let node = NodeIndex(layer, index);
if !compiler.mdd[node].is_active() {
continue;
}
for constraint in 0..compiler.constraints.len() {
compiler.bottom_up_properties[layer][index][constraint] =
compiler.fold_property_over_children(node, variable, constraint);
}
}
}
let check = |stored: &[Vec<Vec<Box<dyn ConstraintProperty>>>],
fresh: &[Vec<Vec<Box<dyn ConstraintProperty>>>],
layers: std::ops::Range<usize>,
direction: &str| {
for layer in layers {
for index in 0..stored[layer].len() {
if !compiler.mdd[NodeIndex(layer, index)].is_active() {
continue;
}
for (stored, fresh) in stored[layer][index].iter().zip(&fresh[layer][index]) {
let mut joined = stored.clone();
joined.merge(fresh.as_ref());
assert!(
ConstraintProperty::eq(joined.as_ref(), stored.as_ref()),
"{context}: a {direction} property of node ({layer}, {index}) \
describes fewer paths than the node holds"
);
assert!(
!same || ConstraintProperty::eq(stored.as_ref(), fresh.as_ref()),
"{context}: a {direction} property of node ({layer}, {index}) is \
coarser than the node's paths"
);
}
}
}
};
let layers = stored_top_down.len();
check(
&stored_top_down,
&compiler.top_down_properties,
1..layers,
"top-down",
);
check(
&stored_bottom_up,
&compiler.bottom_up_properties,
0..layers - 1,
"bottom-up",
);
compiler.top_down_properties = stored_top_down;
compiler.bottom_up_properties = stored_bottom_up;
}
#[test]
fn no_schedule_of_refinements_loses_a_solution() {
use crate::constraints::{all_different, among, at_least, gcc, not_equals, sum};
let variables = 5;
let domain: Vec<isize> = (0..5).collect();
for case in 0..5 {
let mut problem = Problem::default();
let vars = problem.add_variables(variables, domain.clone());
let constraints = match case {
0 => vec![gcc(
&mut problem,
vars,
vec![(0, 1, 2), (1, 0, 2), (2, 1, 3)],
)],
1 => vec![sum(&mut problem, vars, 9)],
2 => vec![all_different(&mut problem, vars)],
3 => vec![
all_different(&mut problem, vars[..3].to_vec()),
not_equals(&mut problem, vars[3], vars[4]),
],
_ => vec![
at_least(&mut problem, vars.clone(), vec![2], 2),
among(&mut problem, vars, vec![0, 1], 2, 4),
],
};
let problem = Arc::new(problem);
let mut solutions: Vec<Vec<isize>> = vec![];
let mut assignment = vec![0isize; variables];
loop {
if constraints
.iter()
.all(|&constraint| problem[constraint].is_satisfied(&assignment))
{
solutions.push(assignment.clone());
}
let mut position = 0;
while position < variables {
assignment[position] += 1;
if assignment[position] < 5 {
break;
}
assignment[position] = 0;
position += 1;
}
if position == variables {
break;
}
}
let mut seed = 7u64;
let mut next = |bound: u64| {
seed = seed
.wrapping_mul(6364136223846793005)
.wrapping_add(1442695040888963407);
(seed >> 33) % bound
};
let mut schedules: Vec<Vec<usize>> =
vec![vec![1, 10], vec![5, 9], vec![6, 9], vec![3, 3, 7, 7]];
for _ in 0..25 {
let calls = 2 + next(3) as usize;
schedules.push((0..calls).map(|_| 1 + next(12) as usize).collect());
}
for merge in [MergeHeuristic::LessRelaxed, MergeHeuristic::StateSimilarity] {
for schedule in &schedules {
let mut compiler = Compiler::new(
Arc::clone(&problem),
CompilationHeuristic {
ordering: OrderingHeuristic::MinDomMaxLinked,
merge: merge.clone(),
selection: SelectHeuristic::Greedy,
},
&constraints,
);
for &width in schedule.iter().chain(&[usize::MAX]) {
compiler.refine(width);
let mdd = compiler.mdd();
assert!(
solutions.iter().all(|solution| is_a_path(mdd, solution)),
"case {case}, {merge:?}, widths {schedule:?} then {width}: a solution was lost"
);
assert_properties_cover_the_paths(
&mut compiler,
width == usize::MAX,
&format!("case {case}, {merge:?}, widths {schedule:?} then {width}"),
);
}
assert_eq!(
compiler.mdd().count_solutions(),
solutions.len().into(),
"case {case}, {merge:?}, widths {schedule:?} then MAX: not exact"
);
}
}
}
}
#[test]
fn refining_in_several_calls_ends_as_exact_as_refining_once() {
let exact = {
let mut compiler = five_different_variables();
compiler.refine(usize::MAX);
compiler.into_mdd()
};
let widths = |mdd: &Mdd| -> Vec<usize> {
(0..mdd.number_layers())
.map(|l| mdd.number_nodes_in_layer(l))
.collect()
};
for schedule in [
vec![1, usize::MAX],
vec![2, usize::MAX],
vec![4, usize::MAX],
vec![1, 10, usize::MAX],
vec![2, 4, 8, usize::MAX],
vec![3, 3, 7, 7, usize::MAX],
vec![2, usize::MAX, usize::MAX],
] {
let mut compiler = five_different_variables();
for &width in &schedule {
compiler.refine(width);
}
let mdd = compiler.into_mdd();
assert_eq!(
mdd.count_solutions(),
120u32.into(),
"schedule {schedule:?}"
);
assert!(
(0..mdd.number_layers())
.flat_map(|layer| mdd.nodes_in_layer(layer))
.all(|node| !mdd[node].is_relaxed()),
"schedule {schedule:?}"
);
assert!(
widths(&mdd)
.iter()
.zip(widths(&exact))
.all(|(w, e)| *w >= e)
);
}
}
#[test]
fn the_diagram_can_be_read_between_refinements_and_taken_at_the_end() {
let mut compiler = five_different_variables();
compiler.refine(16);
let coarse_layers = compiler.mdd().number_layers();
compiler.refine(usize::MAX);
let mdd = compiler.into_mdd();
assert_eq!(mdd.number_layers(), coarse_layers);
assert_eq!(mdd.count_solutions(), 120u32.into());
let (mut solution, _) = mdd.get_solution().expect("the diagram is satisfiable");
solution.sort();
assert_eq!(solution, vec![0, 1, 2, 3, 4]);
}
fn two_variables_with(merge: MergeHeuristic) -> Compiler {
let mut problem = Problem::default();
let x = problem.add_variable(vec![0, 1, 2]);
let y = problem.add_variable(vec![0, 1, 2]);
not_equals(&mut problem, x, y);
let problem = Arc::new(problem);
let constraints: Vec<ConstraintIndex> = problem.iter_constraints().collect();
Compiler::new(
problem,
CompilationHeuristic {
ordering: OrderingHeuristic::MinDomMaxLinked,
merge,
selection: SelectHeuristic::Greedy,
},
&constraints,
)
}
#[test]
fn most_likely_takes_the_probabilities_it_is_given() {
let probabilities = vec![vec![0.2, 0.3, 0.5], vec![1.0, 0.0, 0.0]];
let mut compiler = two_variables_with(MergeHeuristic::MostLikely(probabilities));
compiler.refine(1);
assert!(!compiler.mdd().is_unsat());
}
#[test]
#[should_panic(expected = "one row of probabilities per variable")]
fn most_likely_needs_a_row_per_variable() {
two_variables_with(MergeHeuristic::MostLikely(vec![vec![0.2, 0.3, 0.5]]));
}
#[test]
#[should_panic(expected = "they sum to")]
fn most_likely_needs_distributions() {
two_variables_with(MergeHeuristic::MostLikely(vec![
vec![0.2, 0.3, 0.5],
vec![0.5, 0.5, 0.5],
]));
}
#[test]
#[should_panic(expected = "2 probabilities were given for a domain of 3 values")]
fn most_likely_needs_a_probability_per_value() {
two_variables_with(MergeHeuristic::MostLikely(vec![
vec![0.5, 0.5],
vec![0.2, 0.3, 0.5],
]));
}
#[test]
fn refining_in_several_calls_gives_the_solutions_of_a_single_refinement_for_every_constraint() {
use crate::constraints::{among, at_least, gcc, not_equals, sum};
for case in 0..4 {
let build = || {
let mut problem = Problem::default();
let vars = problem.add_variables(6, vec![0, 1, 2, 3]);
let constraints = match case {
0 => vec![gcc(
&mut problem,
vars,
vec![(0, 1, 2), (1, 0, 2), (2, 1, 3)],
)],
1 => vec![sum(&mut problem, vars, 9)],
2 => vec![
crate::constraints::all_different(&mut problem, vars[..4].to_vec()),
not_equals(&mut problem, vars[4], vars[5]),
],
_ => vec![
at_least(&mut problem, vars.clone(), vec![2], 2),
among(&mut problem, vars, vec![0, 1], 2, 4),
],
};
Compiler::new(
Arc::new(problem),
CompilationHeuristic {
ordering: OrderingHeuristic::MinDomMaxLinked,
merge: MergeHeuristic::LessRelaxed,
selection: SelectHeuristic::Greedy,
},
&constraints,
)
};
let mut once = build();
once.refine(usize::MAX);
let expected = once.mdd().count_solutions();
for schedule in [
vec![1, usize::MAX],
vec![3, usize::MAX],
vec![2, 5, usize::MAX],
] {
let mut compiler = build();
for &width in &schedule {
compiler.refine(width);
}
assert_eq!(
compiler.mdd().count_solutions(),
expected,
"case {case}, schedule {schedule:?}"
);
}
}
}
fn value_sets_of_paths(mdd: &Mdd) -> Vec<Vec<std::collections::BTreeSet<Vec<usize>>>> {
let mut sets: Vec<Vec<std::collections::BTreeSet<Vec<usize>>>> = (0..mdd.number_layers())
.map(|layer| vec![Default::default(); mdd.number_nodes_in_layer(layer)])
.collect();
sets[0][0].insert(vec![]);
for layer in 0..mdd.number_layers() - 1 {
for node in mdd.nodes_in_layer(layer) {
let here = sets[layer][node.1].clone();
for edge in mdd[node].iter_children() {
let NodeIndex(to_layer, to_position) = mdd[edge].to();
for set in &here {
let mut set = set.clone();
set.push(mdd[edge].assignment().0);
set.sort();
sets[to_layer][to_position].insert(set);
}
}
}
}
sets
}
#[test]
fn a_node_is_relaxed_exactly_when_its_paths_differ_or_a_parent_is_relaxed() {
for width in [1, 2, 3, 4, 5, 6, 8, 12, 16, usize::MAX] {
let mut compiler = five_different_variables();
compiler.refine(width);
let mdd = compiler.mdd();
let sets = value_sets_of_paths(mdd);
let mut expected: Vec<Vec<bool>> = vec![];
for layer in 0..mdd.number_layers() {
let relaxed = mdd
.nodes_in_layer(layer)
.map(|node| {
layer != 0
&& (sets[layer][node.1].len() > 1
|| mdd[node]
.iter_parents()
.any(|edge| expected[layer - 1][mdd[edge].from().1]))
})
.collect();
expected.push(relaxed);
}
for (layer, expected_in_layer) in expected.iter().enumerate() {
for node in mdd.nodes_in_layer(layer) {
assert_eq!(
mdd[node].is_relaxed(),
expected_in_layer[node.1],
"width {width}, node {node:?}"
);
}
}
}
}
#[test]
fn an_exact_diagram_has_no_relaxed_node() {
let mut compiler = five_different_variables();
compiler.refine(usize::MAX);
let mdd = compiler.mdd();
assert!(
(0..mdd.number_layers())
.flat_map(|layer| mdd.nodes_in_layer(layer))
.all(|node| !mdd[node].is_relaxed())
);
}
}