extern crate rs_graph as graph;
extern crate time;
extern crate num_traits;
#[macro_use]
extern crate rustop;
use graph::{Graph, Digraph, IndexNetwork, EdgeSlice, LinkedListGraph};
use graph::maxflow::{MaxFlow, EdmondsKarp};
use graph::dimacs::maxflow::Instance;
use std::fmt::Display;
fn run<'a, 'b, G, F>(g: &mut EdmondsKarp<'a, G, F>,
src: G::Node, snk: G::Node,
upper: &EdgeSlice<'a, 'b, G, F>,
niter: usize)
where G: 'a + IndexNetwork<'a>,
F: Display + num_traits::NumAssign + Ord + Copy,
{
{
let tstart = time::precise_time_ns();
for _ in 0..niter {
g.solve(src, snk, upper);
}
let tend = time::precise_time_ns();
println!("Time: {}", (tend - tstart) as f64 / 1e9);
println!("Flow: {}", g.value());
}
}
fn main() {
let (args, _) = opts! {
synopsis "Solve max-flow problem with the algorithm of Edmonds-Karp.";
opt num:usize=1, desc:"Number of times the algorithm is repeated.";
param file:String, desc:"Instance file name";
}.parse_or_exit();
let tstart = time::precise_time_ns();
let instance = Instance::<_, i32, _>::read(&args.file).unwrap();
let g: LinkedListGraph = instance.graph;
let s = instance.src;
let t = instance.snk;
let upper = EdgeSlice::new(&g, &instance.upper);
let tend = time::precise_time_ns();
println!("Time: {}", (tend - tstart) as f64 / 1e9);
println!(" graph: LinkedListGraph");
println!(" number of nodes: {}", g.num_nodes());
println!(" number of arcs: {}", g.num_edges());
let mut d = EdmondsKarp::new(&g);
run(&mut d, s, t, &upper, 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());
}