use crate::builder::{Buildable, Builder};
use crate::traits::IndexGraph;
use super::{read_dimacs, DimacsError};
use crate::num::traits::FromPrimitive;
use std::fs;
use std::io;
pub struct Instance<G, F, N>
where
G: for<'a> IndexGraph<'a, Node = N>,
{
pub graph: G,
pub src: N,
pub snk: N,
pub upper: Vec<F>,
}
impl<G, F, N> Instance<G, F, N>
where
G: for<'a> IndexGraph<'a, Node = N> + Buildable,
F: FromPrimitive,
N: Copy + Eq,
{
pub fn read(fname: &str) -> Result<Self, DimacsError> {
let f = fs::File::open(fname)?;
Instance::read_from_buf(&mut io::BufReader::new(f))
}
pub fn read_from_buf<R>(buf: &mut R) -> Result<Self, DimacsError>
where
R: io::BufRead,
{
let mut graph = G::Builder::new();
let mut nnodes = 0;
let mut nedges = 0;
let mut src = None;
let mut snk = None;
let mut upper = vec![];
enum State {
Prob,
SrcSnk,
Arcs,
};
let mut state = State::Prob;
let mut nodes = vec![];
read_dimacs(buf, &mut |d, toks| match state {
State::Prob => {
if d != 'p' {
return Err(DimacsError::Format {
line: toks.line,
msg: format!("expected problem line starting with 'p', got: {}", d),
});
}
let max = toks.next().unwrap_or("end of line");
if max != "max" {
return Err(DimacsError::Format {
line: toks.line,
msg: format!("expected 'max' in p line, got: {}", max),
});
}
nnodes = toks.number()?;
nedges = toks.number()?;
toks.end()?;
nodes = graph.add_nodes(nnodes);
upper.extend((0..nedges).map(|_| F::from_usize(0).unwrap()));
state = State::SrcSnk;
Ok(())
}
State::SrcSnk => {
if d != 'n' {
return Err(DimacsError::Format {
line: toks.line,
msg: format!("expected node line starting with 'n', got: {}", d),
});
}
let u: usize = toks.number()?;
let what = toks.str()?;
toks.end()?;
if u < 1 || u > nnodes {
return Err(DimacsError::Data {
line: toks.line,
msg: format!("invalid node id {} (must be <= {})", u, nnodes),
});
}
match what {
"s" => {
if src.is_some() {
return Err(DimacsError::Format {
line: toks.line,
msg: "duplicate source node".to_string(),
});
}
src = Some(u);
}
"t" => {
if snk.is_some() {
return Err(DimacsError::Format {
line: toks.line,
msg: "duplicate sink node".to_string(),
});
}
snk = Some(u);
}
_ => {
return Err(DimacsError::Format {
line: toks.line,
msg: format!("invalid node type, must be 's' or 't', got: {}", what),
});
}
}
if src.is_some() && snk.is_some() {
state = State::Arcs;
}
Ok(())
}
State::Arcs => {
if d != 'a' {
return Err(DimacsError::Format {
line: toks.line,
msg: format!("expected arc line starting with 'a', got: {}", d),
});
}
let u: usize = toks.number()?;
let v: usize = toks.number()?;
let c: usize = toks.number()?;
if u < 1 || u > nnodes {
return Err(DimacsError::Data {
line: toks.line,
msg: format!("invalid source node id {} (must be <= {})", u, nnodes),
});
}
if v < 1 || v > nnodes {
return Err(DimacsError::Data {
line: toks.line,
msg: format!("invalid sink node id {} (must be <= {})", v, nnodes),
});
}
if u == v {
return Err(DimacsError::Data {
line: toks.line,
msg: format!("invalid loop ({},{}) in edge", u, u),
});
}
let e = graph.add_edge(nodes[u - 1], nodes[v - 1]);
upper[graph.edge2id(e)] = F::from_usize(c).unwrap();
Ok(())
}
})?;
let src = graph.node2id(src.map(|s| nodes[s - 1]).ok_or_else(|| DimacsError::Format {
line: 0,
msg: "missing source node".to_string(),
})?);
let snk = graph.node2id(snk.map(|t| nodes[t - 1]).ok_or_else(|| DimacsError::Format {
line: 0,
msg: "missing sink node".to_string(),
})?);
let graph = graph.to_graph();
let src = graph.id2node(src);
let snk = graph.id2node(snk);
Ok(Instance { graph, src, snk, upper })
}
}
#[cfg(test)]
mod tests {
use crate::dimacs::maxflow::Instance;
use crate::{traits::*, LinkedListGraph};
use std::io;
#[test]
fn parse_file_test() {
let file = "c this is a test file
p max 6 9
n 5 s
n 6 t
c there might be empty lines
a 5 1 10
a 5 2 10
a 1 2 2
a 1 3 4
a 1 4 8
a 2 4 9
a 3 6 10
a 4 3 6
a 4 6 10
c end of the file
";
let instance = Instance::read_from_buf(&mut io::Cursor::new(file)).unwrap();
let g: LinkedListGraph = instance.graph;
let src = instance.src;
let snk = instance.snk;
let upper = instance.upper;
assert_eq!(g.num_nodes(), 6);
assert_eq!(g.num_edges(), 9);
assert_eq!(g.node_id(src), 4);
assert_eq!(g.node_id(snk), 5);
let mut arcs: Vec<_> = g
.edges()
.map(|e| (g.node_id(g.src(e)) + 1, g.node_id(g.snk(e)) + 1, upper[g.edge_id(e)]))
.collect();
arcs.sort();
assert_eq!(
arcs,
vec![
(1, 2, 2),
(1, 3, 4),
(1, 4, 8),
(2, 4, 9),
(3, 6, 10),
(4, 3, 6),
(4, 6, 10),
(5, 1, 10),
(5, 2, 10),
]
);
}
}