use crate::arith::{Cost, Flow, add_i128, gcd, mul_i128, neg};
use crate::error::VerifyError;
use crate::problem::Problem;
#[derive(Debug, Clone, PartialEq, Eq)]
#[non_exhaustive]
pub struct CycleCertificate {
pub minimum_mean: Option<(i128, i128)>,
}
pub fn certify_no_negative_cycle(
problem: &Problem,
flows: &[Flow],
) -> Result<CycleCertificate, VerifyError> {
if flows.len() != problem.arc_count() {
return Err(VerifyError::LengthMismatch {
expected: problem.arc_count(),
found: flows.len(),
});
}
let graph = ResidualGraph::build(problem, flows)?;
let Some(mut search) = PolicyIteration::new(&graph) else {
return Ok(CycleCertificate { minimum_mean: None });
};
search.run(&graph)?;
let Some((numerator, denominator, node)) = search.minimum(&graph)? else {
return Ok(CycleCertificate { minimum_mean: None });
};
if numerator < 0 {
return Err(VerifyError::NegativeCycle {
numerator,
denominator,
node: search.cycle_node_from(&graph, node),
});
}
Ok(CycleCertificate {
minimum_mean: Some((numerator, denominator)),
})
}
struct ResidualGraph {
node_count: usize,
first_out: Vec<u32>,
head: Vec<u32>,
cost: Vec<Cost>,
first_in: Vec<u32>,
in_tail: Vec<u32>,
}
impl ResidualGraph {
fn build(problem: &Problem, flows: &[Flow]) -> Result<Self, VerifyError> {
let node_count = problem.node_count();
let mut arcs: Vec<(u32, u32, Cost)> = Vec::with_capacity(problem.arc_count());
for (arc, &flow) in problem.arcs().iter().zip(flows) {
if flow < arc.upper {
arcs.push((arc.tail as u32, arc.head as u32, arc.cost));
}
if flow > arc.lower {
arcs.push((
arc.head as u32,
arc.tail as u32,
neg(arc.cost, "reverse residual arc cost")?,
));
}
}
let mut first_out = vec![0u32; node_count + 1];
let mut first_in = vec![0u32; node_count + 1];
for &(u, v, _) in &arcs {
first_out[u as usize + 1] += 1;
first_in[v as usize + 1] += 1;
}
for i in 0..node_count {
first_out[i + 1] += first_out[i];
first_in[i + 1] += first_in[i];
}
let mut head = vec![0u32; arcs.len()];
let mut cost = vec![0 as Cost; arcs.len()];
let mut in_tail = vec![0u32; arcs.len()];
let mut out_cursor: Vec<u32> = first_out[..node_count].to_vec();
let mut in_cursor: Vec<u32> = first_in[..node_count].to_vec();
for &(u, v, c) in &arcs {
let slot = out_cursor[u as usize] as usize;
out_cursor[u as usize] += 1;
head[slot] = v;
cost[slot] = c;
let in_slot = in_cursor[v as usize] as usize;
in_cursor[v as usize] += 1;
in_tail[in_slot] = u;
}
Ok(Self {
node_count,
first_out,
head,
cost,
first_in,
in_tail,
})
}
#[inline]
fn out_arcs(&self, node: usize) -> std::ops::Range<usize> {
self.first_out[node] as usize..self.first_out[node + 1] as usize
}
#[inline]
fn in_arcs(&self, node: usize) -> std::ops::Range<usize> {
self.first_in[node] as usize..self.first_in[node + 1] as usize
}
fn nodes_on_or_before_a_cycle(&self) -> Vec<bool> {
let mut alive = vec![true; self.node_count];
let mut out_degree: Vec<u32> = (0..self.node_count)
.map(|v| self.first_out[v + 1] - self.first_out[v])
.collect();
let mut dead: Vec<usize> = (0..self.node_count)
.filter(|&v| out_degree[v] == 0)
.collect();
while let Some(v) = dead.pop() {
if !alive[v] {
continue;
}
alive[v] = false;
for a in self.in_arcs(v) {
let u = self.in_tail[a] as usize;
if alive[u] {
out_degree[u] -= 1;
if out_degree[u] == 0 {
dead.push(u);
}
}
}
}
alive
}
}
struct PolicyIteration {
alive: Vec<bool>,
policy: Vec<u32>,
mean_num: Vec<i128>,
mean_den: Vec<i128>,
bias: Vec<i128>,
state: Vec<u8>,
position: Vec<usize>,
}
impl PolicyIteration {
fn new(graph: &ResidualGraph) -> Option<Self> {
let alive = graph.nodes_on_or_before_a_cycle();
if !alive.iter().any(|&a| a) {
return None;
}
let node_count = graph.node_count;
let mut policy = vec![u32::MAX; node_count];
for v in 0..node_count {
if !alive[v] {
continue;
}
let mut best: Option<(Cost, u32)> = None;
for a in graph.out_arcs(v) {
if !alive[graph.head[a] as usize] {
continue;
}
let candidate = (graph.cost[a], a as u32);
best = Some(best.map_or(candidate, |b| b.min(candidate)));
}
policy[v] = best.map_or(u32::MAX, |(_, a)| a);
}
Some(Self {
alive,
policy,
mean_num: vec![0; node_count],
mean_den: vec![1; node_count],
bias: vec![0; node_count],
state: vec![0; node_count],
position: vec![0; node_count],
})
}
fn run(&mut self, graph: &ResidualGraph) -> Result<(), VerifyError> {
let limit = (graph.node_count as u64)
.saturating_mul(4)
.saturating_add(1024);
for iteration in 0..limit {
self.evaluate(graph)?;
if !self.improve(graph)? {
return Ok(());
}
let _ = iteration;
}
Err(VerifyError::CycleSearchDidNotConverge { iterations: limit })
}
fn evaluate(&mut self, graph: &ResidualGraph) -> Result<(), VerifyError> {
self.state.iter_mut().for_each(|s| *s = 0);
let mut walk: Vec<usize> = Vec::new();
for start in 0..graph.node_count {
if !self.alive[start] || self.state[start] != 0 {
continue;
}
walk.clear();
let mut node = start;
while self.state[node] == 0 {
self.state[node] = 1;
self.position[node] = walk.len();
walk.push(node);
node = graph.head[self.policy[node] as usize] as usize;
}
let mut tree_end = walk.len();
if self.state[node] == 1 {
let entry = self.position[node];
let length = walk.len() - entry;
let mut sum: i128 = 0;
for &member in &walk[entry..] {
let arc = self.policy[member] as usize;
sum = add_i128(sum, i128::from(graph.cost[arc]), "cycle cost")?;
}
let (num, den) = normalise(sum, length as i128);
for &member in &walk[entry..] {
self.mean_num[member] = num;
self.mean_den[member] = den;
}
let mut base = 0usize;
for (offset, &member) in walk[entry..].iter().enumerate() {
if member < walk[entry + base] {
base = offset;
}
}
self.bias[walk[entry + base]] = 0;
for step in 1..length {
let offset = (base + length - step) % length;
let member = walk[entry + offset];
let successor = walk[entry + (offset + 1) % length];
self.bias[member] = self.step_bias(graph, member, successor, num, den)?;
}
tree_end = entry;
}
for i in (0..tree_end).rev() {
let member = walk[i];
let successor = if i + 1 < walk.len() {
walk[i + 1]
} else {
node
};
let (num, den) = (self.mean_num[successor], self.mean_den[successor]);
self.mean_num[member] = num;
self.mean_den[member] = den;
self.bias[member] = self.step_bias(graph, member, successor, num, den)?;
}
for &member in &walk {
self.state[member] = 2;
}
}
Ok(())
}
fn step_bias(
&self,
graph: &ResidualGraph,
node: usize,
successor: usize,
num: i128,
den: i128,
) -> Result<i128, VerifyError> {
let arc = self.policy[node] as usize;
let scaled = mul_i128(i128::from(graph.cost[arc]), den, "bias arc term")?;
let with_successor = add_i128(scaled, self.bias[successor], "bias accumulation")?;
Ok(add_i128(with_successor, -num, "bias accumulation")?)
}
fn improve(&mut self, graph: &ResidualGraph) -> Result<bool, VerifyError> {
let mut improved = false;
for v in 0..graph.node_count {
if !self.alive[v] {
continue;
}
let mut best_arc = self.policy[v];
let (mut best_num, mut best_den) = (self.mean_num[v], self.mean_den[v]);
let mut best_bias = self.bias[v];
for a in graph.out_arcs(v) {
let w = graph.head[a] as usize;
if !self.alive[w] {
continue;
}
let (num, den) = (self.mean_num[w], self.mean_den[w]);
match compare_rationals((num, den), (best_num, best_den))? {
std::cmp::Ordering::Less => {
best_arc = a as u32;
best_num = num;
best_den = den;
best_bias = bias_of(graph, a, self.bias[w], num, den)?;
}
std::cmp::Ordering::Equal => {
let candidate = bias_of(graph, a, self.bias[w], num, den)?;
if candidate < best_bias {
best_arc = a as u32;
best_bias = candidate;
}
}
std::cmp::Ordering::Greater => {}
}
}
if best_arc != self.policy[v] {
self.policy[v] = best_arc;
improved = true;
}
}
Ok(improved)
}
fn minimum(&self, graph: &ResidualGraph) -> Result<Option<(i128, i128, usize)>, VerifyError> {
let mut best: Option<(i128, i128, usize)> = None;
for v in 0..graph.node_count {
if !self.alive[v] {
continue;
}
let candidate = (self.mean_num[v], self.mean_den[v], v);
best = Some(match best {
None => candidate,
Some(current) => {
match compare_rationals((candidate.0, candidate.1), (current.0, current.1))? {
std::cmp::Ordering::Less => candidate,
_ => current,
}
}
});
}
Ok(best)
}
fn cycle_node_from(&self, graph: &ResidualGraph, node: usize) -> usize {
let mut seen = vec![false; graph.node_count];
let mut current = node;
for _ in 0..=graph.node_count {
if seen[current] {
return current;
}
seen[current] = true;
let arc = self.policy[current] as usize;
if arc >= graph.head.len() {
return current;
}
current = graph.head[arc] as usize;
}
current
}
}
fn bias_of(
graph: &ResidualGraph,
arc: usize,
successor_bias: i128,
num: i128,
den: i128,
) -> Result<i128, VerifyError> {
let scaled = mul_i128(i128::from(graph.cost[arc]), den, "candidate bias term")?;
let with_successor = add_i128(scaled, successor_bias, "candidate bias")?;
Ok(add_i128(with_successor, -num, "candidate bias")?)
}
fn normalise(sum: i128, length: i128) -> (i128, i128) {
if length == 0 {
return (0, 1);
}
let divisor = gcd(sum.unsigned_abs(), length.unsigned_abs()).max(1) as i128;
(sum / divisor, length / divisor)
}
fn compare_rationals(a: (i128, i128), b: (i128, i128)) -> Result<std::cmp::Ordering, VerifyError> {
let left = mul_i128(a.0, b.1, "cycle mean comparison")?;
let right = mul_i128(b.0, a.1, "cycle mean comparison")?;
Ok(left.cmp(&right))
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn acyclic_residual_graph_has_no_cycle_mean() {
let problem = Problem::builder(2)
.supply(0, 1)
.supply(1, -1)
.edge(0, 1, 1, 5)
.build()
.unwrap();
let certificate = certify_no_negative_cycle(&problem, &[1]).unwrap();
assert_eq!(certificate.minimum_mean, None);
}
#[test]
fn finds_the_exact_mean_of_a_positive_cycle() {
let problem = Problem::builder(2)
.edge(0, 1, 4, 1)
.edge(1, 0, 4, 2)
.build()
.unwrap();
let certificate = certify_no_negative_cycle(&problem, &[0, 0]).unwrap();
assert_eq!(certificate.minimum_mean, Some((3, 2)));
}
#[test]
fn detects_a_negative_cycle_and_names_a_node_on_it() {
let problem = Problem::builder(3)
.edge(0, 1, 4, -5)
.edge(1, 2, 4, 1)
.edge(2, 0, 4, 1)
.build()
.unwrap();
let err = certify_no_negative_cycle(&problem, &[0, 0, 0]).unwrap_err();
match err {
VerifyError::NegativeCycle {
numerator,
denominator,
node,
} => {
assert_eq!((numerator, denominator), (-1, 1), "mean of (−5+1+1)/3");
assert!(node < 3);
}
other => panic!("expected NegativeCycle, got {other:?}"),
}
}
#[test]
fn negative_self_loop_is_a_length_one_cycle() {
let problem = Problem::builder(1).arc(0, 0, 0, 3, -7).build().unwrap();
let err = certify_no_negative_cycle(&problem, &[0]).unwrap_err();
assert!(matches!(
err,
VerifyError::NegativeCycle {
numerator: -7,
denominator: 1,
node: 0
}
));
assert_eq!(
certify_no_negative_cycle(&problem, &[3])
.unwrap()
.minimum_mean,
Some((7, 1))
);
}
#[test]
fn picks_the_minimum_among_several_cycles() {
let problem = Problem::builder(4)
.edge(0, 1, 1, 5)
.edge(1, 0, 1, 5)
.edge(2, 3, 1, 0)
.edge(3, 2, 1, 1)
.build()
.unwrap();
let certificate = certify_no_negative_cycle(&problem, &[0, 0, 0, 0]).unwrap();
assert_eq!(certificate.minimum_mean, Some((1, 2)));
}
#[test]
fn agrees_with_brute_force_on_small_random_graphs() {
let mut seed = 0x5eed_1234_u64;
let mut next = move || {
seed ^= seed << 13;
seed ^= seed >> 7;
seed ^= seed << 17;
seed
};
for _ in 0..300 {
let n = 2 + (next() % 5) as usize;
let arc_count = 1 + (next() % 10) as usize;
let mut builder = Problem::builder(n);
let mut arcs = Vec::new();
for _ in 0..arc_count {
let u = (next() % n as u64) as usize;
let v = (next() % n as u64) as usize;
let cost = (next() % 21) as i64 - 10;
arcs.push((u, v, cost));
builder = builder.edge(u, v, 3, cost);
}
let Ok(problem) = builder.build() else {
continue;
};
let flows = vec![0; arc_count];
let expected = brute_force_minimum_mean(n, &arcs);
let actual = match certify_no_negative_cycle(&problem, &flows) {
Ok(c) => c.minimum_mean,
Err(VerifyError::NegativeCycle {
numerator,
denominator,
..
}) => Some((numerator, denominator)),
Err(other) => panic!("unexpected verifier failure: {other:?}"),
};
assert_eq!(actual, expected, "graph {arcs:?}");
}
}
fn brute_force_minimum_mean(n: usize, arcs: &[(usize, usize, i64)]) -> Option<(i128, i128)> {
let mut best: Option<(i128, i128)> = None;
for start in 0..n {
let mut path: Vec<usize> = vec![start];
let mut on_path = vec![false; n];
on_path[start] = true;
walk(start, start, 0, arcs, &mut path, &mut on_path, &mut best);
}
best
}
fn walk(
start: usize,
node: usize,
cost: i128,
arcs: &[(usize, usize, i64)],
path: &mut Vec<usize>,
on_path: &mut Vec<bool>,
best: &mut Option<(i128, i128)>,
) {
for &(u, v, w) in arcs {
if u != node {
continue;
}
let total = cost + i128::from(w);
if v == start {
let (num, den) = normalise(total, path.len() as i128);
let better = match *best {
None => true,
Some((bn, bd)) => num * bd < bn * den,
};
if better {
*best = Some((num, den));
}
} else if v > start && !on_path[v] {
on_path[v] = true;
path.push(v);
walk(start, v, total, arcs, path, on_path, best);
path.pop();
on_path[v] = false;
}
}
}
}