sim_lib_discrete_graph/assignment/
mod.rs

1//! Certified minimum-cost bipartite assignment.
2//!
3//! The unrestricted solver is a polynomial min-cost-flow reduction. The
4//! no-crossing policy uses a polynomial sequence-alignment dynamic program,
5//! because pairwise voice-order constraints are not ordinary edge costs.
6//! Both paths return independently checkable optimality certificates.
7
8// conformance: minimum-cost assignment verifies edits, deterministic ties, and optimality certificates.
9
10mod flow;
11mod ordered;
12mod types;
13mod verify;
14
15use core::cmp::Ordering;
16
17use crate::{
18    AlgorithmControl, AlgorithmInterrupt, GraphError, NeverInterrupt,
19    control::WorkMeter,
20    cost::{add as add_cost, compare},
21};
22
23pub use types::{
24    Assignment, AssignmentCertificate, AssignmentCost, AssignmentOperation, AssignmentPolicy,
25    CostMatrix, DoublingPolicy, VoiceCrossingPolicy,
26};
27pub use verify::verify_assignment;
28
29/// Finds a minimum-cost assignment under insertion, deletion, doubling, and
30/// voice-crossing rules.
31///
32/// Ties are stable: the unrestricted solver uses canonical source/target edge
33/// order, while the no-crossing solver prefers a shorter match span, then
34/// deletion, then insertion at each equal-cost suffix.
35pub fn min_cost_assignment<C: AssignmentCost>(
36    costs: &CostMatrix<C>,
37    policy: AssignmentPolicy<C>,
38) -> Result<Assignment<C>, GraphError> {
39    min_cost_assignment_with_control(costs, policy, &AlgorithmControl::default(), &NeverInterrupt)
40}
41
42/// Finds a minimum-cost assignment under explicit work and cancellation
43/// control.
44pub fn min_cost_assignment_with_control<C: AssignmentCost>(
45    costs: &CostMatrix<C>,
46    policy: AssignmentPolicy<C>,
47    control: &AlgorithmControl,
48    interrupt: &dyn AlgorithmInterrupt,
49) -> Result<Assignment<C>, GraphError> {
50    verify::validate_inputs(costs, &policy)?;
51    let memory = assignment_memory_cells(costs)?;
52    let mut meter = WorkMeter::new(control, interrupt, memory)?;
53    let assignment = match policy.voice_crossing {
54        VoiceCrossingPolicy::Allow => flow::solve(costs, &policy, &mut meter)?,
55        VoiceCrossingPolicy::Forbid => ordered::solve(costs, &policy, &mut meter)?,
56    };
57    let assignment = Assignment {
58        receipt: meter.finish(),
59        ..assignment
60    };
61    verify_assignment(costs, &policy, &assignment)?;
62    Ok(assignment)
63}
64
65pub(super) fn add<C: AssignmentCost>(left: &C, right: &C, context: &str) -> Result<C, GraphError> {
66    add_cost(left, right, context)
67}
68
69pub(super) fn sub<C: AssignmentCost>(left: &C, right: &C, context: &str) -> Result<C, GraphError> {
70    left.checked_sub(right)
71        .ok_or_else(|| GraphError::WeightOverflow(context.to_owned()))
72}
73
74pub(super) fn certificate_error<T>(message: &str) -> Result<T, GraphError> {
75    Err(GraphError::CertificateInvalid(message.to_owned()))
76}
77
78pub(super) fn less<C: AssignmentCost>(
79    left: &C,
80    right: &C,
81    context: &str,
82) -> Result<bool, GraphError> {
83    Ok(compare(left, right, context)? == Ordering::Less)
84}
85
86fn assignment_memory_cells<C>(costs: &CostMatrix<C>) -> Result<usize, GraphError> {
87    costs
88        .rows()
89        .checked_add(1)
90        .and_then(|rows| {
91            costs
92                .columns()
93                .checked_add(1)
94                .and_then(|columns| rows.checked_mul(columns))
95        })
96        .ok_or_else(|| GraphError::InvalidAssignment("assignment dimensions overflow".to_owned()))
97}
98
99#[cfg(test)]
100mod tests;
sim_lib_discrete_graph/assignment/mod.rs

sim_lib_discrete_graph/assignment/
mod.rs
