use crate::arith::{Capacity, Cost, Flow, Objective};
use crate::error::DimacsError;
use crate::problem::{Problem, ProblemBuilder};
const BYTES_PER_DECLARED_NODE: u64 = size_of::<Flow>() as u64 + size_of::<bool>() as u64;
pub const DEFAULT_READ_LIMIT: u64 = 256 << 20;
pub fn read(text: &str) -> Result<Problem, DimacsError> {
read_within(text, DEFAULT_READ_LIMIT)
}
pub fn read_within(text: &str, memory_limit: u64) -> Result<Problem, DimacsError> {
let mut builder: Option<ProblemBuilder> = None;
let mut node_count = 0usize;
let mut declared_arcs = 0usize;
let mut arcs_seen = 0usize;
let mut supply_seen: Vec<bool> = Vec::new();
for (index, raw) in text.lines().enumerate() {
let line = index + 1;
let mut fields = raw.split_whitespace();
let Some(tag) = fields.next() else { continue };
let Some(tag) = single_char(tag) else {
return Err(DimacsError::UnknownLineType { line, tag: '?' });
};
match tag {
'c' => {}
'p' => {
if builder.is_some() {
return Err(DimacsError::DuplicateProblemLine { line });
}
let rest: Vec<&str> = fields.collect();
if rest.len() != 3 {
return Err(DimacsError::FieldCount {
line,
tag,
expected: 3,
found: rest.len(),
});
}
if rest[0] != "min" {
return Err(DimacsError::UnsupportedProblemType {
line,
found: rest[0].to_owned(),
});
}
node_count = count(rest[1], line, 2, "node count")?;
declared_arcs = count(rest[2], line, 3, "arc count")?;
let required = (node_count as u64).saturating_mul(BYTES_PER_DECLARED_NODE);
if required > memory_limit {
return Err(DimacsError::DeclaredSizeExceedsLimit {
line,
node_count,
required,
limit: memory_limit,
});
}
supply_seen = vec![false; node_count];
builder = Some(Problem::builder(node_count));
}
'n' => {
let Some(current) = builder.take() else {
return Err(DimacsError::DescriptorBeforeProblem { line, tag });
};
let rest: Vec<&str> = fields.collect();
if rest.len() != 2 {
return Err(DimacsError::FieldCount {
line,
tag,
expected: 2,
found: rest.len(),
});
}
let node = node_id(rest[0], line, 1, node_count)?;
let supply: Flow = integer(rest[1], line, 2)?;
if supply_seen[node] {
return Err(DimacsError::DuplicateSupply { line, node });
}
supply_seen[node] = true;
builder = Some(current.supply(node, supply));
}
'a' => {
let Some(current) = builder.take() else {
return Err(DimacsError::DescriptorBeforeProblem { line, tag });
};
let rest: Vec<&str> = fields.collect();
if rest.len() != 5 {
return Err(DimacsError::FieldCount {
line,
tag,
expected: 5,
found: rest.len(),
});
}
let tail = node_id(rest[0], line, 1, node_count)?;
let head = node_id(rest[1], line, 2, node_count)?;
let lower: Capacity = integer(rest[2], line, 3)?;
let upper: Capacity = integer(rest[3], line, 4)?;
let cost: Cost = integer(rest[4], line, 5)?;
arcs_seen += 1;
builder = Some(current.arc(tail, head, lower, upper, cost));
}
other => return Err(DimacsError::UnknownLineType { line, tag: other }),
}
}
let Some(builder) = builder else {
return Err(DimacsError::MissingProblemLine);
};
if arcs_seen != declared_arcs {
return Err(DimacsError::ArcCountMismatch {
declared: declared_arcs,
found: arcs_seen,
});
}
Ok(builder.build()?)
}
#[must_use]
pub fn write(problem: &Problem) -> String {
use std::fmt::Write as _;
let mut out = String::new();
let _ = writeln!(out, "c min-cost flow instance written by eo-mcf");
let _ = writeln!(
out,
"p min {} {}",
problem.node_count(),
problem.arc_count()
);
for (node, &supply) in problem.supplies().iter().enumerate() {
if supply != 0 {
let _ = writeln!(out, "n {} {supply}", node + 1);
}
}
for arc in problem.arcs() {
let _ = writeln!(
out,
"a {} {} {} {} {}",
arc.tail + 1,
arc.head + 1,
arc.lower,
arc.upper,
arc.cost
);
}
out
}
#[must_use]
pub fn write_solution(problem: &Problem, flows: &[Flow], objective: Objective) -> String {
use std::fmt::Write as _;
let mut out = String::new();
let _ = writeln!(out, "s {objective}");
for (arc, &flow) in problem.arcs().iter().zip(flows) {
if flow != 0 {
let _ = writeln!(out, "f {} {} {flow}", arc.tail + 1, arc.head + 1);
}
}
out
}
fn single_char(field: &str) -> Option<char> {
let mut chars = field.chars();
let first = chars.next()?;
chars.next().is_none().then_some(first)
}
fn integer(text: &str, line: usize, field: usize) -> Result<i64, DimacsError> {
text.parse::<i64>().map_err(|_| DimacsError::BadInteger {
line,
field,
text: text.to_owned(),
})
}
fn count(text: &str, line: usize, field: usize, what: &'static str) -> Result<usize, DimacsError> {
let value = integer(text, line, field)?;
usize::try_from(value).map_err(|_| DimacsError::BadCount { line, what, value })
}
fn node_id(text: &str, line: usize, field: usize, node_count: usize) -> Result<usize, DimacsError> {
let value = integer(text, line, field)?;
if value < 1 || value > node_count as i64 {
return Err(DimacsError::NodeOutOfRange {
line,
node: value,
node_count,
});
}
Ok(value as usize - 1)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::error::BuildError;
const SAMPLE: &str = "\
c a four-node instance
p min 4 5
n 1 4
n 4 -4
a 1 2 0 3 1
a 2 4 0 3 1
a 1 3 0 4 3
a 3 4 0 4 3
a 2 3 0 1 0
";
#[test]
fn reads_a_well_formed_instance() {
let problem = read(SAMPLE).unwrap();
assert_eq!(problem.node_count(), 4);
assert_eq!(problem.arc_count(), 5);
assert_eq!(problem.supplies(), &[4, 0, 0, -4]);
assert_eq!(problem.arcs()[0].tail, 0);
assert_eq!(problem.arcs()[0].head, 1);
assert_eq!(problem.arcs()[4].cost, 0);
}
#[test]
fn round_trips() {
let problem = read(SAMPLE).unwrap();
assert_eq!(read(&write(&problem)), Ok(problem));
}
#[test]
fn round_trips_lower_bounds_and_negative_costs() {
let problem = Problem::builder(3)
.supply(0, 5)
.supply(2, -5)
.arc(0, 1, 2, 6, -3)
.arc(1, 2, 0, 9, 4)
.build()
.unwrap();
assert_eq!(read(&write(&problem)), Ok(problem));
}
#[test]
fn rejects_a_missing_problem_line() {
assert_eq!(
read("c nothing here\n"),
Err(DimacsError::MissingProblemLine)
);
}
#[test]
fn rejects_a_second_problem_line() {
assert_eq!(
read("p min 2 0\np min 3 0\n"),
Err(DimacsError::DuplicateProblemLine { line: 2 })
);
}
#[test]
fn rejects_a_descriptor_before_the_problem_line() {
assert_eq!(
read("n 1 5\np min 2 0\n"),
Err(DimacsError::DescriptorBeforeProblem { line: 1, tag: 'n' })
);
}
#[test]
fn rejects_an_unknown_tag() {
assert_eq!(
read("p min 2 0\nx 1 2\n"),
Err(DimacsError::UnknownLineType { line: 2, tag: 'x' })
);
}
#[test]
fn rejects_a_short_arc_line() {
assert_eq!(
read("p min 2 1\na 1 2 0 5\n"),
Err(DimacsError::FieldCount {
line: 2,
tag: 'a',
expected: 5,
found: 4
})
);
}
#[test]
fn rejects_a_non_integer_field() {
assert_eq!(
read("p min 2 1\na 1 2 0 five 1\n"),
Err(DimacsError::BadInteger {
line: 2,
field: 4,
text: "five".to_owned()
})
);
}
#[test]
fn rejects_a_node_id_out_of_range() {
assert_eq!(
read("p min 2 1\na 1 7 0 5 1\n"),
Err(DimacsError::NodeOutOfRange {
line: 2,
node: 7,
node_count: 2
})
);
assert_eq!(
read("p min 2 1\na 0 1 0 5 1\n"),
Err(DimacsError::NodeOutOfRange {
line: 2,
node: 0,
node_count: 2
})
);
}
#[test]
fn rejects_a_duplicate_supply() {
assert_eq!(
read("p min 2 0\nn 1 3\nn 1 -3\n"),
Err(DimacsError::DuplicateSupply { line: 3, node: 0 })
);
}
#[test]
fn rejects_an_arc_count_that_disagrees_with_the_header() {
assert_eq!(
read("p min 2 3\na 1 2 0 5 1\n"),
Err(DimacsError::ArcCountMismatch {
declared: 3,
found: 1
})
);
}
const FUZZ_OOM: &str = "p\u{b}min\u{b}666663165\u{b}666663165193";
#[test]
fn rejects_the_fuzzers_out_of_memory_header() {
assert_eq!(FUZZ_OOM.len(), 28, "not the input that was minimised");
let error = read(FUZZ_OOM).expect_err("28 bytes must not buy 6 GB");
assert!(
matches!(
error,
DimacsError::DeclaredSizeExceedsLimit {
line: 1,
node_count: 666_663_165,
limit: DEFAULT_READ_LIMIT,
..
}
),
"refused for the wrong reason: {error}"
);
}
#[test]
fn rejects_an_unaffordable_node_count_with_no_arcs_at_all() {
let error = read("p min 666663165 0\n").expect_err("18 bytes must not buy 6 GB");
assert!(
matches!(error, DimacsError::DeclaredSizeExceedsLimit { .. }),
"refused for the wrong reason: {error}"
);
}
#[test]
fn still_reads_a_large_but_affordable_instance() {
let problem = read("p min 1000000 0\n").unwrap();
assert_eq!(problem.node_count(), 1_000_000);
assert_eq!(problem.arc_count(), 0);
}
#[test]
fn the_read_limit_binds_and_belongs_to_the_caller() {
assert!(matches!(
read_within(SAMPLE, 0),
Err(DimacsError::DeclaredSizeExceedsLimit {
node_count: 4,
limit: 0,
..
})
));
assert!(read_within(SAMPLE, DEFAULT_READ_LIMIT).is_ok());
assert_eq!(read_within(SAMPLE, u64::MAX), read(SAMPLE));
}
#[test]
fn the_limit_is_exact_at_the_boundary_and_raising_it_admits_the_instance() {
const TEXT: &str = "p min 1000 0\n";
let required = 1000 * BYTES_PER_DECLARED_NODE;
assert_eq!(required, 9000);
assert!(matches!(
read_within(TEXT, required - 1),
Err(DimacsError::DeclaredSizeExceedsLimit {
required: 9000,
limit: 8999,
..
})
));
let problem = read_within(TEXT, required).expect("the limit is a ceiling, not a barrier");
assert_eq!(problem.node_count(), 1000);
}
#[test]
fn an_over_declared_arc_count_is_still_reported_as_a_mismatch() {
assert_eq!(
read("p min 2 3000000\na 1 2 0 5 1\n"),
Err(DimacsError::ArcCountMismatch {
declared: 3_000_000,
found: 1
})
);
}
#[test]
fn rejects_an_unsupported_problem_type() {
assert_eq!(
read("p max 2 1\n"),
Err(DimacsError::UnsupportedProblemType {
line: 1,
found: "max".to_owned()
})
);
}
#[test]
fn rejects_a_negative_declared_count() {
assert_eq!(
read("p min -2 0\n"),
Err(DimacsError::BadCount {
line: 1,
what: "node count",
value: -2
})
);
}
#[test]
fn surfaces_structural_problems_from_the_builder() {
assert_eq!(
read("p min 2 0\nn 1 5\n"),
Err(DimacsError::Build(BuildError::UnbalancedSupply {
total: 5
}))
);
}
#[test]
fn tolerates_blank_lines_and_odd_whitespace() {
let problem = read("\np min 2 1\n\n a 1 2 0 5 1 \n").unwrap();
assert_eq!(problem.arc_count(), 1);
}
#[test]
fn writes_a_solution_in_the_conventional_shape() {
let problem = read(SAMPLE).unwrap();
let rendered = write_solution(&problem, &[3, 3, 1, 1, 0], 12);
assert!(rendered.starts_with("s 12\n"));
assert!(rendered.contains("f 1 2 3\n"));
assert!(!rendered.contains("f 2 3"), "zero-flow arcs are omitted");
}
}