extern crate rs_graph as graph;
extern crate time;
extern crate num_traits;
#[macro_use]
extern crate rustop;
extern crate ordered_float;
use graph::{Graph, Digraph, IndexNetwork, EdgeSlice, LinkedListGraph};
use graph::maxflow::{MaxFlow, PushRelabel};
use graph::dimacs::maxflow::Instance;
use std::fmt::{Debug, Display};
use num_traits::{FromPrimitive, NumAssign};
use ordered_float::NotNaN;
fn run<'a, 'b, G, F>(g: &mut PushRelabel<'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 read_and_run<F>(filename: &str, num: usize, global_relabelling: bool, typ: &str)
where F: Debug + Display + NumAssign + FromPrimitive + Copy + Ord
{
let tstart = time::precise_time_ns();
let instance = Instance::<_, F, _>::read(filename).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 type: {}", typ);
println!(" global-relabelling heuristic: {}", if global_relabelling { "YES" } else { "NO" });
println!(" number of nodes: {}", g.num_nodes());
println!(" number of arcs: {}", g.num_edges());
let mut d = PushRelabel::new(&g);
d.use_global_relabelling = global_relabelling;
run(&mut d, s, t, &upper, num);
println!(" number of relabels: {}", d.cnt_relabel);
assert!(g.edges().all(|e| d.flow(e) >= F::zero() && d.flow(e) <= upper[e]));
assert!(g.nodes().filter(|&u| u != s && u != t).all(|u| {
let mut f_out = F::zero();
for (e, _) in g.outedges(u) {
f_out += d.flow(e);
}
let mut f_in = F::zero();
for (e, _) in g.inedges(u) {
f_in += d.flow(e);
}
f_out == f_in
}));
assert_eq!({
let mut f_out = F::zero();
for (e, _) in g.outedges(s) {
f_out += d.flow(e);
}
let mut f_in = F::zero();
for (e, _) in g.inedges(s) {
f_in += d.flow(e);
}
f_out - f_in
}, d.value());
}
fn main() {
let (args, _) = opts! {
synopsis "Solve max-flow problem with a push-relabel algorithm.";
opt global_relabelling:bool, desc:"Use global-relabel heuristic.";
opt num:usize=1, desc:"Number of times the algorithm is repeated.";
opt real:bool, desc:"Use real valued flows.";
param file:String, desc:"Instance file name";
}.parse_or_exit();
if !args.real {
read_and_run::<i32>(&args.file, args.num, args.global_relabelling, "i32");
} else {
read_and_run::<NotNaN<f64>>(&args.file, args.num, args.global_relabelling, "f64");
}
}