use crate::arith::{Capacity, Cost, Flow, Objective, add_i128};
use crate::error::BuildError;
pub const MAX_NODES: usize = u32::MAX as usize;
pub const MAX_ARCS: usize = (u32::MAX / 2) as usize;
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct Arc {
pub tail: usize,
pub head: usize,
pub lower: Capacity,
pub upper: Capacity,
pub cost: Cost,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Problem {
node_count: usize,
supplies: Vec<Flow>,
arcs: Vec<Arc>,
}
#[derive(Debug, Clone)]
pub struct ProblemBuilder {
node_count: usize,
supplies: Vec<Flow>,
arcs: Vec<Arc>,
stray_supply: Option<usize>,
}
impl Problem {
#[must_use]
pub fn builder(node_count: usize) -> ProblemBuilder {
ProblemBuilder {
node_count,
supplies: vec![0; node_count.min(MAX_NODES)],
arcs: Vec::new(),
stray_supply: None,
}
}
#[must_use]
pub fn node_count(&self) -> usize {
self.node_count
}
#[must_use]
pub fn arc_count(&self) -> usize {
self.arcs.len()
}
#[must_use]
pub fn arcs(&self) -> &[Arc] {
&self.arcs
}
#[must_use]
pub fn supplies(&self) -> &[Flow] {
&self.supplies
}
#[must_use]
pub fn supply(&self, node: usize) -> Option<Flow> {
self.supplies.get(node).copied()
}
pub fn objective(&self, flows: &[Flow]) -> Result<Objective, crate::arith::Overflow> {
let mut total: Objective = 0;
for (arc, &f) in self.arcs.iter().zip(flows) {
let term = crate::arith::mul_i128(
Objective::from(arc.cost),
Objective::from(f),
"objective term",
)?;
total = add_i128(total, term, "objective")?;
}
Ok(total)
}
#[must_use]
pub fn canonical(&self) -> (Self, Vec<usize>) {
let mut perm: Vec<usize> = (0..self.arcs.len()).collect();
perm.sort_by_key(|&i| {
let a = self.arcs[i];
(a.tail, a.head, a.cost, a.lower, a.upper, i)
});
let arcs = perm.iter().map(|&i| self.arcs[i]).collect();
(
Self {
node_count: self.node_count,
supplies: self.supplies.clone(),
arcs,
},
perm,
)
}
#[must_use]
pub fn memory_estimate(&self) -> u64 {
let n = self.node_count as u64;
let m = self.arcs.len() as u64;
let residual = 2 * m * (4 + 4 + 4 + 8 + 8) + (n + 1) * 4;
let per_node = n * (8 + 8 + 4 + 4 + 1);
let per_node = per_node
+ if cfg!(feature = "heur-arc-fixing") {
n * 4
} else {
0
}
+ if cfg!(feature = "heur-global-update") {
n * (8 + 8)
} else {
0
}
+ if cfg!(feature = "heur-bucket-update") {
(2 * n + 1) * 4 + (n + 2 * m) * (4 + 4)
} else if cfg!(feature = "heur-global-update") {
(n + 2 * m) * 16
} else {
0
}
+ if cfg!(feature = "heur-price-refinement") {
n * (8 + 8 + 4 + 4)
} else {
0
};
let feasibility = 2 * (m + n) * (4 + 4 + 8) + (n + 2) * (4 + 4 + 4);
let result = m * 8;
residual + per_node + feasibility + result
}
}
impl ProblemBuilder {
#[must_use]
pub fn supply(mut self, node: usize, value: Flow) -> Self {
match self.supplies.get_mut(node) {
Some(slot) => *slot = value,
None => self.stray_supply = self.stray_supply.or(Some(node)),
}
self
}
#[must_use]
pub fn arc(
mut self,
tail: usize,
head: usize,
lower: Capacity,
upper: Capacity,
cost: Cost,
) -> Self {
self.arcs.push(Arc {
tail,
head,
lower,
upper,
cost,
});
self
}
#[must_use]
pub fn edge(self, tail: usize, head: usize, capacity: Capacity, cost: Cost) -> Self {
self.arc(tail, head, 0, capacity, cost)
}
pub fn build(self) -> Result<Problem, BuildError> {
if let Some(node) = self.stray_supply {
return Err(BuildError::SupplyNodeOutOfRange {
node,
node_count: self.node_count,
});
}
if self.node_count > MAX_NODES {
return Err(BuildError::TooLarge {
what: "nodes",
count: self.node_count,
max: MAX_NODES,
});
}
if self.arcs.len() > MAX_ARCS {
return Err(BuildError::TooLarge {
what: "arcs",
count: self.arcs.len(),
max: MAX_ARCS,
});
}
for (i, arc) in self.arcs.iter().enumerate() {
if arc.tail >= self.node_count {
return Err(BuildError::NodeOutOfRange {
arc: i,
node: arc.tail,
node_count: self.node_count,
});
}
if arc.head >= self.node_count {
return Err(BuildError::NodeOutOfRange {
arc: i,
node: arc.head,
node_count: self.node_count,
});
}
if arc.lower > arc.upper {
return Err(BuildError::InvalidBounds {
arc: i,
lower: arc.lower,
upper: arc.upper,
});
}
}
let mut supplies = self.supplies;
supplies.resize(self.node_count, 0);
let mut total: Objective = 0;
for &b in &supplies {
total = add_i128(total, Objective::from(b), "total supply")?;
}
if total != 0 {
return Err(BuildError::UnbalancedSupply { total });
}
Ok(Problem {
node_count: self.node_count,
supplies,
arcs: self.arcs,
})
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn builds_a_balanced_instance() {
let p = Problem::builder(3)
.supply(0, 5)
.supply(2, -5)
.edge(0, 1, 5, 1)
.edge(1, 2, 5, 1)
.build()
.unwrap();
assert_eq!(p.node_count(), 3);
assert_eq!(p.arc_count(), 2);
assert_eq!(p.supply(0), Some(5));
assert_eq!(p.supply(1), Some(0));
assert_eq!(p.supply(3), None);
}
#[test]
fn rejects_unbalanced_supply() {
let err = Problem::builder(2)
.supply(0, 5)
.supply(1, -4)
.build()
.unwrap_err();
assert_eq!(err, BuildError::UnbalancedSupply { total: 1 });
}
#[test]
fn rejects_out_of_range_endpoints() {
let err = Problem::builder(2).edge(0, 7, 1, 1).build().unwrap_err();
assert_eq!(
err,
BuildError::NodeOutOfRange {
arc: 0,
node: 7,
node_count: 2
}
);
}
#[test]
fn rejects_lower_bound_above_capacity() {
let err = Problem::builder(2).arc(0, 1, 5, 2, 0).build().unwrap_err();
assert_eq!(
err,
BuildError::InvalidBounds {
arc: 0,
lower: 5,
upper: 2
}
);
}
#[test]
fn supply_on_an_unknown_node_is_reported() {
let err = Problem::builder(2).supply(9, 3).build().unwrap_err();
assert_eq!(
err,
BuildError::SupplyNodeOutOfRange {
node: 9,
node_count: 2
}
);
}
#[test]
fn a_stray_supply_is_reported_even_when_the_totals_balance() {
let err = Problem::builder(2)
.supply(9, 3)
.supply(0, -3)
.build()
.unwrap_err();
assert_eq!(
err,
BuildError::SupplyNodeOutOfRange {
node: 9,
node_count: 2
}
);
}
#[test]
fn objective_widens_past_i64() {
let p = Problem::builder(2)
.supply(0, 0)
.edge(0, 1, i64::MAX, i64::MAX)
.build()
.unwrap();
let want = Objective::from(i64::MAX) * Objective::from(i64::MAX);
assert_eq!(p.objective(&[i64::MAX]), Ok(want));
}
#[test]
fn canonical_form_is_permutation_invariant() {
let a = Problem::builder(3)
.supply(0, 2)
.supply(2, -2)
.edge(0, 1, 2, 3)
.edge(1, 2, 2, 4)
.edge(0, 2, 1, 9)
.build()
.unwrap();
let b = Problem::builder(3)
.supply(0, 2)
.supply(2, -2)
.edge(0, 2, 1, 9)
.edge(1, 2, 2, 4)
.edge(0, 1, 2, 3)
.build()
.unwrap();
let (ca, pa) = a.canonical();
let (cb, _) = b.canonical();
assert_eq!(ca, cb, "canonical forms of permuted instances must agree");
for (i, &orig) in pa.iter().enumerate() {
assert_eq!(ca.arcs()[i], a.arcs()[orig]);
}
}
#[test]
fn memory_estimate_grows_with_the_instance() {
let small = Problem::builder(2).edge(0, 1, 1, 1).build().unwrap();
let big = Problem::builder(100)
.edge(0, 1, 1, 1)
.edge(1, 2, 1, 1)
.build()
.unwrap();
assert!(big.memory_estimate() > small.memory_estimate());
}
}