use crate::arith::{Flow, Objective, add_i128};
use crate::error::VerifyError;
use crate::problem::Problem;
pub fn certify_feasibility(problem: &Problem, flows: &[Flow]) -> Result<(), VerifyError> {
if flows.len() != problem.arc_count() {
return Err(VerifyError::LengthMismatch {
expected: problem.arc_count(),
found: flows.len(),
});
}
for (index, (arc, &flow)) in problem.arcs().iter().zip(flows).enumerate() {
if flow < arc.lower || flow > arc.upper {
return Err(VerifyError::CapacityViolated {
arc: index,
flow,
lower: arc.lower,
upper: arc.upper,
});
}
}
let mut net = vec![0 as Objective; problem.node_count()];
for (arc, &flow) in problem.arcs().iter().zip(flows) {
let f = Objective::from(flow);
net[arc.tail] = add_i128(net[arc.tail], f, "net outflow")?;
net[arc.head] = add_i128(net[arc.head], -f, "net outflow")?;
}
for (node, (&balance, &supply)) in net.iter().zip(problem.supplies()).enumerate() {
if balance != Objective::from(supply) {
return Err(VerifyError::ConservationViolated {
node,
net: balance,
supply,
});
}
}
Ok(())
}
#[cfg(test)]
mod tests {
use super::*;
fn instance() -> Problem {
Problem::builder(3)
.supply(0, 4)
.supply(2, -4)
.edge(0, 1, 5, 1)
.edge(1, 2, 5, 1)
.build()
.unwrap()
}
#[test]
fn accepts_a_feasible_flow() {
assert_eq!(certify_feasibility(&instance(), &[4, 4]), Ok(()));
}
#[test]
fn rejects_a_wrong_length_vector() {
assert_eq!(
certify_feasibility(&instance(), &[4]),
Err(VerifyError::LengthMismatch {
expected: 2,
found: 1
})
);
}
#[test]
fn rejects_an_over_capacity_arc() {
assert_eq!(
certify_feasibility(&instance(), &[9, 9]),
Err(VerifyError::CapacityViolated {
arc: 0,
flow: 9,
lower: 0,
upper: 5
})
);
}
#[test]
fn rejects_a_negative_flow() {
assert_eq!(
certify_feasibility(&instance(), &[-1, 4]),
Err(VerifyError::CapacityViolated {
arc: 0,
flow: -1,
lower: 0,
upper: 5
})
);
}
#[test]
fn rejects_broken_conservation() {
assert_eq!(
certify_feasibility(&instance(), &[4, 3]),
Err(VerifyError::ConservationViolated {
node: 1,
net: -1,
supply: 0
})
);
}
#[test]
fn honours_lower_bounds() {
let p = Problem::builder(2)
.supply(0, 3)
.supply(1, -3)
.arc(0, 1, 3, 5, 1)
.build()
.unwrap();
assert_eq!(certify_feasibility(&p, &[3]), Ok(()));
assert_eq!(
certify_feasibility(&p, &[2]),
Err(VerifyError::CapacityViolated {
arc: 0,
flow: 2,
lower: 3,
upper: 5
})
);
}
#[test]
fn self_loops_do_not_disturb_conservation() {
let p = Problem::builder(2)
.supply(0, 1)
.supply(1, -1)
.arc(0, 0, 0, 7, 2)
.edge(0, 1, 1, 0)
.build()
.unwrap();
assert_eq!(certify_feasibility(&p, &[5, 1]), Ok(()));
}
}