Module rs_graph::maxflow::pushrelabel

This module implements a push relabel algorithm for solving max flow problems.

This implementation uses the gap heuristic and the global relabelling heuristic.

Example

use rs_graph::{Builder, Graph, Digraph, Net, EdgeVec, NumberedNode};
use rs_graph::maxflow::pushrelabel;

let mut g = Net::new();
let mut upper = vec![];
let s = g.add_node();
let t = g.add_node();
let v1 = g.add_node();
let v2 = g.add_node();
let v3 = g.add_node();
let v4 = g.add_node();
g.add_edge(s, v1); upper.push(5);
g.add_edge(s, v3); upper.push(5);
g.add_edge(v1, v2); upper.push(2);
g.add_edge(v1, v3); upper.push(1);
g.add_edge(v1, v4); upper.push(1);
g.add_edge(v2, t); upper.push(4);
g.add_edge(v3, v4); upper.push(2);
g.add_edge(v4, v2); upper.push(2);
g.add_edge(v4, t); upper.push(5);
let upper: EdgeVec<_> = upper.into();

let (value, flow, mut mincut) = pushrelabel(&g, s, t, &upper);

assert_eq!(value, 5);
assert!(g.edges().all(|e| flow[e] >= 0 && flow[e] <= upper[e]));
assert!(g.nodes().filter(|&u| u != s && u != t).all(|u| {
    g.outedges(u).map(|(e,_)| flow[e])
                 .sum::<isize>() ==
    g.inedges(u).map(|(e,_)| flow[e]).sum::<isize>()
}));

mincut.sort_by_key(|u| u.index());
assert_eq!(mincut, vec![s, v1, v3]);

Structs

PushRelabel