use time::PrimitiveDateTime;
use rustop::opts;
use rs_graph::dimacs::maxflow::Instance;
use rs_graph::maxflow::{MaxFlow, PushRelabel};
use rs_graph::traits::*;
use rs_graph::vec::EdgeVec;
use rs_graph::LinkedListGraph;
use std::fmt::{Debug, Display};
use num_traits::{FromPrimitive, NumAssign};
use ordered_float::NotNan;
fn run<'a, G, F, Us>(g: &mut PushRelabel<'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 read_and_run<F>(filename: &str, num: usize, global_relabelling: bool, typ: &str)
where
F: Debug + Display + NumAssign + FromPrimitive + Copy + Ord,
{
let tstart = PrimitiveDateTime::now();
let instance = Instance::<_, F, _>::read(filename).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 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, |e| upper[e], 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");
}
}