use num_traits;
use time::PrimitiveDateTime;
use rustop::opts;
use rs_graph::dimacs::maxflow::Instance;
use rs_graph::maxflow::{Dinic, MaxFlow};
use rs_graph::traits::*;
use rs_graph::vec::EdgeVec;
use rs_graph::LinkedListGraph;
use std::fmt::Display;
fn run<'a, G, F, Us>(g: &mut Dinic<'a, G, F>, src: G::Node, snk: G::Node, upper: Us, niter: usize)
where
G: 'a + IndexDigraph<'a>,
F: Display + num_traits::NumAssign + Ord + Copy,
Us: Fn(G::Edge) -> F + Copy,
{
{
let tstart = PrimitiveDateTime::now();
for _ in 0..niter {
g.solve(src, snk, upper);
}
let tend = PrimitiveDateTime::now();
println!("Time: {}", (tend - tstart).as_seconds_f64());
println!("Flow: {}", g.value());
}
}
fn main() {
let (args, _) = opts! {
synopsis "Solve max-flow problem with Dinic's algorithm.";
opt num:usize=1, desc:"Number of times the algorithm is repeated.";
param file:String, desc:"Instance file name";
}
.parse_or_exit();
let tstart = PrimitiveDateTime::now();
let instance = Instance::<_, i32, _>::read(&args.file).unwrap();
let g: LinkedListGraph = instance.graph;
let s = instance.src;
let t = instance.snk;
let upper = EdgeVec::new_from_vec(&g, instance.upper);
let tend = PrimitiveDateTime::now();
println!("Time: {}", (tend - tstart).as_seconds_f64());
println!(" graph: LinkedListGraph");
println!(" number of nodes: {}", g.num_nodes());
println!(" number of arcs: {}", g.num_edges());
let mut d = Dinic::new(&g);
run(&mut d, s, t, |e| upper[e], args.num);
assert!(g.edges().all(|e| d.flow(e) >= 0 && d.flow(e) <= upper[e]));
assert!(g.nodes().filter(|&u| u != s && u != t).all(
|u| g.outedges(u).map(|(e, _)| d.flow(e)).sum::<i32>() == g.inedges(u).map(|(e, _)| d.flow(e)).sum::<i32>()
));
assert_eq!(
g.outedges(s).map(|(e, _)| d.flow(e)).sum::<i32>() - g.inedges(s).map(|(e, _)| d.flow(e)).sum::<i32>(),
d.value()
);
}