#![deny(missing_docs)]
#![warn(clippy::missing_docs_in_private_items)]
use rand::{Rng, RngExt};
use crate::mdd::{Mdd, NodeIndex};
use crate::modelling::{Problem, ValueIndex};
#[derive(Clone, Copy, Debug)]
pub enum DecodeMode {
Sample,
Greedy,
}
pub fn argmax(weights: &[f64]) -> usize {
assert!(!weights.is_empty(), "weights should not be empty");
let mut best = 0;
for (index, weight) in weights.iter().enumerate() {
assert!(!weight.is_nan(), "weights should never be NaN");
if *weight > weights[best] {
best = index;
}
}
best
}
pub fn sample_categorical_with<R: Rng + ?Sized>(weights: &[f64], rng: &mut R) -> usize {
let total: f64 = weights.iter().sum();
assert!(
total.is_finite() && total > 0.0,
"cannot sample from weights {weights:?}: they must have a positive, finite sum"
);
let mut target = rng.random_range(0.0..total);
for (index, &weight) in weights.iter().enumerate() {
target -= weight;
if target <= 0.0 {
return index;
}
}
weights.len() - 1
}
pub fn sample_categorical(weights: &[f64]) -> usize {
crate::utils::with_rng(|rng| sample_categorical_with(weights, rng))
}
pub fn random_assignment(problem: &Problem) -> Vec<isize> {
crate::utils::with_rng(|rng| random_assignment_with(problem, rng))
}
pub fn random_assignment_with<R: Rng + ?Sized>(problem: &Problem, rng: &mut R) -> Vec<isize> {
problem
.iter_variables()
.map(|variable| {
let size = problem[variable].domain_size();
problem[variable].value(ValueIndex(rng.random_range(0..size)))
})
.collect()
}
pub fn uniform_weights(mdd: &Mdd) -> Vec<Vec<f64>> {
(0..mdd.number_layers() - 1)
.map(|layer| vec![1.0; mdd.problem()[mdd.decision_at_layer(layer)].domain_size()])
.collect()
}
pub fn sample_solution(mdd: &Mdd, weights: &[Vec<f64>]) -> Vec<ValueIndex> {
assert!(
!mdd.is_unsat(),
"cannot sample a solution from an unsatisfiable diagram"
);
assert_eq!(
weights.len(),
mdd.number_layers() - 1,
"sample_solution needs one row of weights per layer but the sink's"
);
let mut path = Vec::with_capacity(weights.len());
let mut node = mdd.root();
while node != mdd.sink() {
let NodeIndex(layer, _) = node;
let edges: Vec<_> = mdd[node].iter_children().collect();
let edge_weights: Vec<f64> = edges
.iter()
.map(|&edge| weights[layer][mdd[edge].assignment().0])
.collect();
assert!(
edge_weights.iter().sum::<f64>() > 0.0,
"every edge leaving node {node:?} has a weight of zero: nothing can be sampled"
);
let edge = edges[sample_categorical(&edge_weights)];
path.push(mdd[edge].assignment());
node = mdd[edge].to();
}
path
}
#[cfg(test)]
mod tests {
use super::*;
use crate::constraints::{all_different, not_equals};
use crate::mdd::heuristics::{
CompilationHeuristic, MergeHeuristic, OrderingHeuristic, SelectHeuristic,
};
use crate::mdd::{Compiler, Mdd};
use crate::modelling::Problem;
use std::sync::Arc;
fn compile(problem: Problem) -> Mdd {
let problem = Arc::new(problem);
let constraints: Vec<_> = 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);
compiler.into_mdd()
}
fn skewed() -> Mdd {
let mut problem = Problem::default();
let x = problem.add_variable(vec![0, 1]);
let y = problem.add_variable(vec![0, 1]);
not_equals(&mut problem, x, y);
compile(problem)
}
#[test]
fn every_sample_of_an_exact_diagram_is_a_solution() {
let mut problem = Problem::default();
let vars = problem.add_variables(3, vec![0, 1, 2]);
all_different(&mut problem, vars);
let mdd = compile(problem);
let weights = vec![vec![1.0; 3]; 3];
for _ in 0..200 {
let path = sample_solution(&mdd, &weights);
let (mut solution, _) = mdd.solution_from_path(&path);
solution.sort();
assert_eq!(solution, vec![0, 1, 2]);
}
}
#[test]
fn values_are_drawn_in_proportion_to_their_weight() {
let mdd = skewed();
let weights: Vec<Vec<f64>> = (0..2)
.map(|layer| match mdd.decision_at_layer(layer).0 {
0 => vec![0.9, 0.1],
_ => vec![1.0, 1.0],
})
.collect();
let draws = 4000;
let zeros = (0..draws)
.filter(|_| {
let (values, variables) = mdd.solution_from_path(&sample_solution(&mdd, &weights));
values[variables.iter().position(|v| v.0 == 0).unwrap()] == 0
})
.count();
let frequency = zeros as f64 / draws as f64;
assert!((frequency - 0.9).abs() < 0.04, "frequency {frequency}");
}
#[test]
fn the_weights_are_those_of_the_caller() {
let mdd = skewed();
let (first, second) = (mdd.decision_at_layer(0), mdd.decision_at_layer(1));
let weights = vec![vec![0.0, 1.0], vec![0.5, 0.5]];
for _ in 0..100 {
let (solution, variables) = mdd.solution_from_path(&sample_solution(&mdd, &weights));
assert_eq!(variables, vec![first, second]);
assert_eq!(solution, vec![1, 0]);
}
}
#[test]
fn uniform_weights_have_a_row_per_layer_and_a_one_per_value() {
let mdd = skewed();
assert_eq!(uniform_weights(&mdd), vec![vec![1.0; 2]; 2]);
}
#[test]
fn a_zero_weight_is_never_drawn() {
for _ in 0..200 {
assert_eq!(sample_categorical(&[0.0, 1.0, 0.0]), 1);
}
}
#[test]
fn a_draw_with_a_given_generator_follows_its_seed() {
use rand::SeedableRng;
use rand::rngs::StdRng;
let weights = [0.2, 0.3, 0.5];
let draw = |seed| {
let mut rng = StdRng::seed_from_u64(seed);
(0..50)
.map(|_| sample_categorical_with(&weights, &mut rng))
.collect::<Vec<_>>()
};
assert_eq!(draw(7), draw(7));
assert_ne!(draw(7), draw(8));
}
#[test]
#[should_panic(expected = "must have a positive, finite sum")]
fn weights_summing_to_zero_cannot_be_drawn() {
sample_categorical(&[0.0, 0.0]);
}
#[test]
fn argmax_picks_the_largest_weight() {
assert_eq!(argmax(&[0.1, 0.7, 0.2]), 1);
assert_eq!(argmax(&[0.9, 0.05, 0.05]), 0);
}
#[test]
fn argmax_takes_the_first_of_equal_weights() {
assert_eq!(argmax(&[0.2, 0.4, 0.4]), 1);
assert_eq!(argmax(&[0.5, 0.5]), 0);
}
#[test]
fn a_random_assignment_has_a_value_of_each_domain() {
let mut problem = Problem::default();
problem.add_variable(vec![4, 5]);
problem.add_variable(vec![9]);
problem.add_variable(vec![-1, 0, 1]);
for _ in 0..100 {
let assignment = random_assignment(&problem);
assert!([4, 5].contains(&assignment[0]));
assert_eq!(assignment[1], 9);
assert!([-1, 0, 1].contains(&assignment[2]));
}
}
#[test]
#[should_panic(expected = "cannot sample a solution from an unsatisfiable diagram")]
fn an_unsatisfiable_diagram_cannot_be_sampled() {
let mut problem = Problem::default();
let x = problem.add_variable(vec![0]);
let y = problem.add_variable(vec![0]);
not_equals(&mut problem, x, y);
sample_solution(&compile(problem), &[]);
}
#[test]
#[should_panic(expected = "one row of weights per layer")]
fn the_weights_need_a_row_per_layer() {
sample_solution(&skewed(), &[vec![1.0, 1.0]]);
}
#[test]
#[should_panic(expected = "has a weight of zero")]
fn weights_that_forbid_every_edge_cannot_be_sampled() {
sample_solution(&skewed(), &[vec![0.0, 0.0], vec![1.0, 1.0]]);
}
}