use crate::arith::{Capacity, Cost, Flow, Objective, Overflow};
use crate::problem::Problem;
pub const BRUTE_FORCE_LIMIT: u128 = 1 << 20;
#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
#[non_exhaustive]
pub enum OracleError {
#[error("instance has {combinations} candidate flows, above the brute-force limit of {limit}")]
TooLarge {
combinations: u128,
limit: u128,
},
#[error("successive shortest paths did not converge within {augmentations} augmentations")]
DidNotConverge {
augmentations: u64,
},
#[error(transparent)]
Overflow(#[from] Overflow),
}
pub fn brute_force(problem: &Problem) -> Result<Option<Objective>, OracleError> {
let mut radices: Vec<u64> = Vec::with_capacity(problem.arc_count());
let mut combinations: u128 = 1;
for arc in problem.arcs() {
let span = arc
.upper
.checked_sub(arc.lower)
.and_then(|s| s.checked_add(1))
.ok_or_else(|| Overflow::new("brute-force arc span"))?;
let span = u64::try_from(span).map_err(|_| Overflow::new("brute-force arc span"))?;
radices.push(span);
combinations = combinations.saturating_mul(u128::from(span));
if combinations > BRUTE_FORCE_LIMIT {
return Err(OracleError::TooLarge {
combinations,
limit: BRUTE_FORCE_LIMIT,
});
}
}
let mut digits = vec![0u64; problem.arc_count()];
let mut flows = vec![0 as Flow; problem.arc_count()];
let mut best: Option<Objective> = None;
'candidates: loop {
for (index, arc) in problem.arcs().iter().enumerate() {
flows[index] = arc.lower + digits[index] as Flow;
}
if let Some(cost) = feasible_cost(problem, &flows) {
best = Some(best.map_or(cost, |b: Objective| b.min(cost)));
}
let mut position = 0;
loop {
if position == digits.len() {
break 'candidates;
}
digits[position] += 1;
if digits[position] < radices[position] {
break;
}
digits[position] = 0;
position += 1;
}
if digits.is_empty() {
break;
}
}
Ok(best)
}
fn feasible_cost(problem: &Problem, flows: &[Flow]) -> Option<Objective> {
let mut net = vec![0 as Objective; problem.node_count()];
for (arc, &flow) in problem.arcs().iter().zip(flows) {
net[arc.tail] += Objective::from(flow);
net[arc.head] -= Objective::from(flow);
}
for (&balance, &supply) in net.iter().zip(problem.supplies()) {
if balance != Objective::from(supply) {
return None;
}
}
problem.objective(flows).ok()
}
pub fn successive_shortest_paths(
problem: &Problem,
) -> Result<Option<(Vec<Flow>, Objective)>, OracleError> {
let node_count = problem.node_count();
let source = node_count;
let sink = node_count + 1;
let mut graph = Graph::new(node_count + 2);
let mut excess: Vec<i128> = problem.supplies().iter().map(|&b| i128::from(b)).collect();
let mut flows = vec![0 as Flow; problem.arc_count()];
let mut readback: Vec<Option<(usize, Flow, Flow)>> = vec![None; problem.arc_count()];
for (index, arc) in problem.arcs().iter().enumerate() {
if arc.tail == arc.head {
flows[index] = if arc.cost >= 0 { arc.lower } else { arc.upper };
continue;
}
excess[arc.tail] -= i128::from(arc.lower);
excess[arc.head] += i128::from(arc.lower);
let span = arc
.upper
.checked_sub(arc.lower)
.ok_or_else(|| Overflow::new("oracle arc span"))?;
if arc.cost < 0 {
excess[arc.tail] -= i128::from(span);
excess[arc.head] += i128::from(span);
let edge = graph.add(arc.head, arc.tail, span, -arc.cost);
flows[index] = arc.upper;
readback[index] = Some((edge, arc.upper, -1));
} else {
let edge = graph.add(arc.tail, arc.head, span, arc.cost);
flows[index] = arc.lower;
readback[index] = Some((edge, arc.lower, 1));
}
}
let mut required: i128 = 0;
for (node, &value) in excess.iter().enumerate() {
if value > 0 {
let capacity = Capacity::try_from(value).map_err(|_| Overflow::new("oracle supply"))?;
graph.add(source, node, capacity, 0);
required += value;
} else if value < 0 {
let capacity =
Capacity::try_from(-value).map_err(|_| Overflow::new("oracle demand"))?;
graph.add(node, sink, capacity, 0);
}
}
let bound = (graph.cap.len() as u64)
.saturating_mul(4)
.saturating_add(1024);
let mut routed: i128 = 0;
let mut augmentations = 0u64;
while routed < required {
let Some(path) = graph.shortest_path(source, sink) else {
break;
};
let Some(bottleneck) = path.iter().map(|&e| graph.cap[e]).min() else {
break;
};
if bottleneck <= 0 {
break;
}
for &edge in &path {
graph.cap[edge] -= bottleneck;
graph.cap[edge ^ 1] += bottleneck;
}
routed += i128::from(bottleneck);
augmentations += 1;
if augmentations > bound {
return Err(OracleError::DidNotConverge {
augmentations: bound,
});
}
}
if routed != required {
return Ok(None);
}
for (index, entry) in readback.iter().enumerate() {
if let &Some((edge, base, sign)) = entry {
flows[index] = base + sign * graph.cap[edge ^ 1];
}
}
let objective = problem.objective(&flows)?;
Ok(Some((flows, objective)))
}
#[must_use]
pub fn max_flow_value(
node_count: usize,
edges: &[(u32, u32, Capacity)],
source: usize,
sink: usize,
) -> i128 {
if source == sink || source >= node_count || sink >= node_count {
return 0;
}
let mut adjacency: Vec<Vec<usize>> = vec![Vec::new(); node_count];
let mut to: Vec<usize> = Vec::with_capacity(edges.len() * 2);
let mut residual: Vec<Capacity> = Vec::with_capacity(edges.len() * 2);
for &(tail, head, capacity) in edges {
adjacency[tail as usize].push(to.len());
to.push(head as usize);
residual.push(capacity.max(0));
adjacency[head as usize].push(to.len());
to.push(tail as usize);
residual.push(0);
}
let mut total: i128 = 0;
loop {
let mut arrived: Vec<Option<usize>> = vec![None; node_count];
let mut seen = vec![false; node_count];
seen[source] = true;
let mut queue = std::collections::VecDeque::new();
queue.push_back(source);
while let Some(node) = queue.pop_front() {
if node == sink {
break;
}
for &edge in &adjacency[node] {
let next = to[edge];
if residual[edge] > 0 && !seen[next] {
seen[next] = true;
arrived[next] = Some(edge);
queue.push_back(next);
}
}
}
if !seen[sink] {
return total;
}
let mut bottleneck = Capacity::MAX;
let mut node = sink;
while let Some(edge) = arrived[node] {
bottleneck = bottleneck.min(residual[edge]);
node = to[edge ^ 1];
}
if bottleneck <= 0 {
return total;
}
let mut node = sink;
while let Some(edge) = arrived[node] {
residual[edge] -= bottleneck;
residual[edge ^ 1] += bottleneck;
node = to[edge ^ 1];
}
total += i128::from(bottleneck);
}
}
struct Graph {
adjacency: Vec<Vec<usize>>,
to: Vec<usize>,
cap: Vec<Capacity>,
cost: Vec<Cost>,
}
impl Graph {
fn new(node_count: usize) -> Self {
Self {
adjacency: vec![Vec::new(); node_count],
to: Vec::new(),
cap: Vec::new(),
cost: Vec::new(),
}
}
fn add(&mut self, from: usize, to: usize, capacity: Capacity, cost: Cost) -> usize {
let edge = self.to.len();
self.adjacency[from].push(edge);
self.to.push(to);
self.cap.push(capacity);
self.cost.push(cost);
self.adjacency[to].push(edge + 1);
self.to.push(from);
self.cap.push(0);
self.cost.push(-cost);
edge
}
fn shortest_path(&self, source: usize, sink: usize) -> Option<Vec<usize>> {
let node_count = self.adjacency.len();
let mut distance = vec![i128::MAX; node_count];
let mut incoming: Vec<Option<usize>> = vec![None; node_count];
distance[source] = 0;
for _ in 0..node_count {
let mut changed = false;
for u in 0..node_count {
if distance[u] == i128::MAX {
continue;
}
for &edge in &self.adjacency[u] {
if self.cap[edge] <= 0 {
continue;
}
let v = self.to[edge];
let candidate = distance[u] + i128::from(self.cost[edge]);
if candidate < distance[v] {
distance[v] = candidate;
incoming[v] = Some(edge);
changed = true;
}
}
}
if !changed {
break;
}
}
if distance[sink] == i128::MAX {
return None;
}
let mut path = Vec::new();
let mut node = sink;
while node != source {
let edge = incoming[node]?;
path.push(edge);
node = self.to[edge ^ 1];
}
path.reverse();
Some(path)
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn brute_force_finds_the_cheap_route() {
let problem = Problem::builder(4)
.supply(0, 1)
.supply(3, -1)
.edge(0, 1, 1, 1)
.edge(1, 3, 1, 1)
.edge(0, 2, 1, 5)
.edge(2, 3, 1, 5)
.build()
.unwrap();
assert_eq!(brute_force(&problem), Ok(Some(2)));
}
#[test]
fn brute_force_reports_infeasibility_as_none() {
let problem = Problem::builder(2)
.supply(0, 5)
.supply(1, -5)
.edge(0, 1, 2, 1)
.build()
.unwrap();
assert_eq!(brute_force(&problem), Ok(None));
}
#[test]
fn brute_force_refuses_an_instance_it_cannot_enumerate() {
let problem = Problem::builder(2)
.supply(0, 0)
.edge(0, 1, 1_000_000, 1)
.edge(1, 0, 1_000_000, 1)
.build()
.unwrap();
assert!(matches!(
brute_force(&problem),
Err(OracleError::TooLarge { .. })
));
}
#[test]
fn successive_shortest_paths_agrees_with_brute_force() {
let problem = Problem::builder(4)
.supply(0, 2)
.supply(3, -2)
.edge(0, 1, 1, 1)
.edge(1, 3, 2, 1)
.edge(0, 2, 2, 2)
.edge(2, 3, 1, 1)
.build()
.unwrap();
let (_, objective) = successive_shortest_paths(&problem).unwrap().unwrap();
assert_eq!(Some(objective), brute_force(&problem).unwrap());
}
#[test]
fn successive_shortest_paths_handles_negative_costs() {
let problem = Problem::builder(3)
.supply(0, 1)
.supply(2, -1)
.edge(0, 1, 3, -4)
.edge(1, 2, 3, 1)
.edge(0, 2, 3, 1)
.build()
.unwrap();
let (flows, objective) = successive_shortest_paths(&problem).unwrap().unwrap();
assert_eq!(Some(objective), brute_force(&problem).unwrap());
assert_eq!(crate::verify::certify_feasibility(&problem, &flows), Ok(()));
}
#[test]
fn successive_shortest_paths_reports_infeasibility() {
let problem = Problem::builder(2)
.supply(0, 5)
.supply(1, -5)
.edge(0, 1, 2, 1)
.build()
.unwrap();
assert_eq!(successive_shortest_paths(&problem), Ok(None));
}
#[test]
fn successive_shortest_paths_respects_lower_bounds() {
let problem = Problem::builder(3)
.supply(0, 2)
.supply(2, -2)
.arc(0, 1, 1, 2, 7) .arc(1, 2, 0, 2, 0)
.arc(0, 2, 0, 2, 1)
.build()
.unwrap();
let (flows, objective) = successive_shortest_paths(&problem).unwrap().unwrap();
assert!(flows[0] >= 1);
assert_eq!(Some(objective), brute_force(&problem).unwrap());
}
#[test]
fn max_flow_value_matches_the_obvious_bottleneck() {
assert_eq!(max_flow_value(3, &[(0, 1, 4), (1, 2, 2)], 0, 2), 2);
}
}