use crate::arith::{Capacity, Cost, Flow, add, neg, sub};
use crate::error::SolveError;
use crate::problem::Problem;
#[derive(Debug, Clone)]
pub(crate) struct Residual {
pub(crate) node_count: usize,
pub(crate) first_out: Vec<u32>,
pub(crate) head: Vec<u32>,
pub(crate) rev: Vec<u32>,
pub(crate) cap: Vec<Capacity>,
pub(crate) cost: Vec<Cost>,
pub(crate) entry_arc: Vec<u32>,
#[cfg(feature = "heur-arc-fixing")]
pub(crate) active_end: Vec<u32>,
}
impl Residual {
#[inline]
pub(crate) fn live_end(&self, node: usize) -> u32 {
#[cfg(feature = "heur-arc-fixing")]
{
self.active_end[node]
}
#[cfg(not(feature = "heur-arc-fixing"))]
{
self.first_out[node + 1]
}
}
#[inline]
pub(crate) fn out_arcs(&self, node: usize) -> std::ops::Range<usize> {
self.first_out[node] as usize..self.live_end(node) as usize
}
#[inline]
pub(crate) fn push(&mut self, arc: usize, delta: Capacity) {
self.cap[arc] -= delta;
let r = self.rev[arc] as usize;
self.cap[r] += delta;
}
#[cfg(feature = "heur-arc-fixing")]
pub(crate) fn fix_pair(&mut self, entry: usize, tail: usize) {
let partner = self.rev[entry] as usize;
let head = self.head[entry] as usize;
debug_assert_ne!(tail, head, "self-loops are removed by normalisation");
self.retire(entry, tail);
self.retire(partner, head);
}
#[cfg(feature = "heur-arc-fixing")]
fn retire(&mut self, entry: usize, node: usize) {
let last = self.active_end[node] as usize - 1;
self.active_end[node] = last as u32;
if entry == last {
return;
}
self.head.swap(entry, last);
self.cap.swap(entry, last);
self.cost.swap(entry, last);
self.entry_arc.swap(entry, last);
self.rev.swap(entry, last);
let partner_of_entry = self.rev[entry] as usize;
let partner_of_last = self.rev[last] as usize;
self.rev[partner_of_entry] = entry as u32;
self.rev[partner_of_last] = last as u32;
}
}
#[derive(Debug, Clone)]
pub(crate) struct Normalized {
pub(crate) res: Residual,
pub(crate) excess: Vec<Flow>,
origin: Vec<u32>,
lower: Vec<Capacity>,
forced: Vec<(u32, Flow)>,
original_arcs: usize,
}
impl Normalized {
pub(crate) fn forward_arcs(&self) -> impl Iterator<Item = (u32, u32, Capacity)> + '_ {
self.res
.entry_arc
.iter()
.enumerate()
.filter(|&(_, &tag)| tag & 1 == 1)
.map(move |(i, _)| {
let tail = self.res.head[self.res.rev[i] as usize];
(tail, self.res.head[i], self.res.cap[i])
})
}
pub(crate) fn reconstruct(&self) -> Vec<Flow> {
let mut flows = vec![0; self.original_arcs];
for (i, &tag) in self.res.entry_arc.iter().enumerate() {
if tag & 1 == 0 {
let j = (tag >> 1) as usize;
flows[self.origin[j] as usize] = self.lower[j] + self.res.cap[i];
}
}
for &(arc, flow) in &self.forced {
flows[arc as usize] = flow;
}
flows
}
#[cfg(test)]
pub(crate) fn forward_entry_of(&self, j: usize) -> usize {
let tag = (j as u32) << 1 | 1;
self.res
.entry_arc
.iter()
.position(|&t| t == tag)
.expect("normalised arc has a forward entry")
}
}
pub(crate) fn normalize(problem: &Problem) -> Result<Normalized, SolveError> {
let node_count = problem.node_count();
let mut excess = problem.supplies().to_vec();
let mut tails: Vec<u32> = Vec::with_capacity(problem.arc_count());
let mut heads: Vec<u32> = Vec::with_capacity(problem.arc_count());
let mut caps: Vec<Capacity> = Vec::with_capacity(problem.arc_count());
let mut costs: Vec<Cost> = Vec::with_capacity(problem.arc_count());
let mut origin: Vec<u32> = Vec::with_capacity(problem.arc_count());
let mut lower: Vec<Capacity> = Vec::with_capacity(problem.arc_count());
let mut forced: Vec<(u32, Flow)> = Vec::new();
for (k, arc) in problem.arcs().iter().enumerate() {
let index = u32::try_from(k).map_err(|_| SolveError::InvariantViolated {
what: "arc index exceeds u32 after a successful build",
})?;
if arc.tail == arc.head {
let flow = if arc.cost >= 0 { arc.lower } else { arc.upper };
forced.push((index, flow));
continue;
}
excess[arc.tail] = sub(
excess[arc.tail],
arc.lower,
"supply after lower-bound substitution",
)?;
excess[arc.head] = add(
excess[arc.head],
arc.lower,
"supply after lower-bound substitution",
)?;
tails.push(u32::try_from(arc.tail).unwrap_or(u32::MAX));
heads.push(u32::try_from(arc.head).unwrap_or(u32::MAX));
caps.push(sub(
arc.upper,
arc.lower,
"arc capacity after lower-bound substitution",
)?);
costs.push(arc.cost);
origin.push(index);
lower.push(arc.lower);
}
let res = build_csr(node_count, &tails, &heads, &caps, &costs)?;
Ok(Normalized {
res,
excess,
origin,
lower,
forced,
original_arcs: problem.arc_count(),
})
}
fn build_csr(
node_count: usize,
tails: &[u32],
heads: &[u32],
caps: &[Capacity],
costs: &[Cost],
) -> Result<Residual, SolveError> {
let entries = tails.len() * 2;
let mut first_out = vec![0u32; node_count + 1];
for (&u, &v) in tails.iter().zip(heads) {
first_out[u as usize + 1] += 1;
first_out[v as usize + 1] += 1;
}
for i in 0..node_count {
first_out[i + 1] += first_out[i];
}
let mut head = vec![0u32; entries];
let mut rev = vec![0u32; entries];
let mut cap = vec![0 as Capacity; entries];
let mut cost = vec![0 as Cost; entries];
let mut entry_arc = vec![0u32; entries];
let mut cursor: Vec<u32> = first_out[..node_count].to_vec();
for k in 0..tails.len() {
let (u, v) = (tails[k] as usize, heads[k] as usize);
let forward = cursor[u];
cursor[u] += 1;
let backward = cursor[v];
cursor[v] += 1;
let tag = (u32::try_from(k).map_err(|_| SolveError::InvariantViolated {
what: "normalised arc index exceeds u32 after a successful build",
})?) << 1;
let (fi, bi) = (forward as usize, backward as usize);
head[fi] = heads[k];
cap[fi] = caps[k];
cost[fi] = costs[k];
rev[fi] = backward;
entry_arc[fi] = tag | 1;
head[bi] = tails[k];
cap[bi] = 0;
cost[bi] = neg(costs[k], "reverse arc cost")?;
rev[bi] = forward;
entry_arc[bi] = tag;
}
Ok(Residual {
node_count,
#[cfg(feature = "heur-arc-fixing")]
active_end: first_out[1..].to_vec(),
first_out,
head,
rev,
cap,
cost,
entry_arc,
})
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn csr_spans_partition_the_entries_and_pair_correctly() {
let p = Problem::builder(3)
.supply(0, 1)
.supply(2, -1)
.edge(0, 1, 4, 7)
.edge(1, 2, 5, -2)
.build()
.unwrap();
let norm = normalize(&p).unwrap();
let res = &norm.res;
assert_eq!(res.first_out.len(), 4);
assert_eq!(*res.first_out.last().unwrap() as usize, res.head.len());
assert_eq!(res.head.len(), 4);
for i in 0..res.head.len() {
let partner = res.rev[i] as usize;
assert_eq!(res.rev[partner] as usize, i, "rev must be an involution");
assert_eq!(
res.cost[partner], -res.cost[i],
"partner carries the negated cost"
);
}
for u in 0..res.node_count {
for a in res.out_arcs(u) {
let v = res.head[a] as usize;
assert_eq!(res.head[res.rev[a] as usize] as usize, u);
assert_ne!(u, v);
}
}
}
#[test]
fn lower_bounds_move_supply_and_come_back_on_reconstruct() {
let p = Problem::builder(2)
.supply(0, 4)
.supply(1, -4)
.arc(0, 1, 3, 5, 1)
.build()
.unwrap();
let mut norm = normalize(&p).unwrap();
assert_eq!(norm.excess, vec![1, -1]);
let forward = norm.forward_entry_of(0);
assert_eq!(norm.res.cap[forward], 2, "residual span is upper − lower");
norm.res.push(forward, 1);
assert_eq!(norm.reconstruct(), vec![4]);
}
#[test]
fn entry_arc_tags_are_a_partner_respecting_bijection() {
let p = Problem::builder(4)
.supply(0, 2)
.supply(3, -2)
.edge(0, 1, 4, 7)
.edge(1, 3, 5, -2)
.edge(0, 2, 3, 1)
.edge(2, 3, 3, 1)
.edge(1, 2, 2, 0) .build()
.unwrap();
let norm = normalize(&p).unwrap();
let res = &norm.res;
let mut seen = [0u32; 5];
for i in 0..res.head.len() {
let tag = res.entry_arc[i];
let partner = res.rev[i] as usize;
assert_eq!(
res.entry_arc[partner],
tag ^ 1,
"partners describe the same arc from opposite ends"
);
seen[(tag >> 1) as usize] += 1;
}
assert!(seen.iter().all(|&count| count == 2), "one pair per arc");
}
#[cfg(feature = "heur-arc-fixing")]
#[test]
fn fix_pair_retires_both_entries_and_preserves_every_invariant() {
let p = Problem::builder(4)
.supply(0, 2)
.supply(3, -2)
.edge(0, 1, 4, 7)
.edge(0, 2, 3, 1)
.edge(0, 3, 5, 9)
.edge(1, 3, 4, 2)
.edge(2, 3, 3, 1)
.build()
.unwrap();
let mut norm = normalize(&p).unwrap();
let via = norm.forward_entry_of(1);
norm.res.push(via, 1);
let via = norm.forward_entry_of(4);
norm.res.push(via, 1);
for arc in [1usize, 3] {
let entry = norm.forward_entry_of(arc);
let tail = norm.res.head[norm.res.rev[entry] as usize] as usize;
norm.res.fix_pair(entry, tail);
}
let res = &norm.res;
for node in 0..res.node_count {
assert!(res.active_end[node] >= res.first_out[node]);
assert!(res.active_end[node] <= res.first_out[node + 1]);
}
let live: Vec<bool> = (0..res.node_count)
.flat_map(|u| {
(res.first_out[u]..res.first_out[u + 1]).map(move |i| i < res.active_end[u])
})
.collect();
let mut dead_arcs: Vec<u32> = (0..res.head.len())
.filter(|&i| !live[i])
.map(|i| res.entry_arc[i] >> 1)
.collect();
dead_arcs.sort_unstable();
assert_eq!(dead_arcs, [1, 1, 3, 3], "exactly the fixed pairs died");
for i in 0..res.head.len() {
let partner = res.rev[i] as usize;
assert_eq!(res.rev[partner] as usize, i, "rev is an involution");
assert_eq!(res.entry_arc[partner], res.entry_arc[i] ^ 1);
assert_eq!(res.cost[partner], -res.cost[i]);
}
assert_eq!(norm.reconstruct(), vec![0, 1, 0, 0, 1]);
}
#[test]
fn self_loops_are_resolved_and_removed() {
let p = Problem::builder(2)
.supply(0, 1)
.supply(1, -1)
.arc(0, 0, 2, 9, 5) .arc(1, 1, 2, 9, -5) .edge(0, 1, 1, 0)
.build()
.unwrap();
let norm = normalize(&p).unwrap();
assert_eq!(norm.res.head.len(), 2, "only the real arc survives");
let flows = norm.reconstruct();
assert_eq!(flows[0], 2);
assert_eq!(flows[1], 9);
}
#[test]
fn reverse_cost_negation_overflow_is_an_error_not_a_wrap() {
let p = Problem::builder(2)
.supply(0, 0)
.edge(0, 1, 1, i64::MIN)
.build()
.unwrap();
assert!(matches!(normalize(&p), Err(SolveError::Overflow(_))));
}
}