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::traits::*;
use rs_graph::maxflow::pushrelabel;
use rs_graph::{EdgeVec, Net};
use rs_graph::string::{Data, from_ascii};

let Data { graph: g, weights: upper, nodes } = from_ascii::<Net>(r"
     a---2-->b
    @|\      ^\
   / | \     | 4
  5  |  \    |  \
 /   |   |   |   @
s    1   1   2    t
 \   |   |   |   @
  5  |    \  |  /
   \ |     \ | 5
    @v      @|/
     c---2-->d
    ").unwrap();

let s = nodes[&'s'];
let t = nodes[&'t'];
let v1 = nodes[&'a'];
let v2 = nodes[&'b'];
let v3 = nodes[&'c'];
let v4 = nodes[&'d'];

let (value, flow, mut mincut) = pushrelabel(&g, s, t, |e| upper[e.index()]);

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

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

use rs_graph::traits::*;
use rs_graph::maxflow::pushrelabel;
use rs_graph::{EdgeVec, Net};
use rs_graph::string::{Data, from_ascii};

let Data { graph: g, weights: upper, nodes } = from_ascii::<Net>(r"
               ---8-->a---10---
              /       |        \
             /        1  --3--  |
            /         | /     \ |
           /          v@       \v
     ---->b-----9---->c----8--->d----
    /      \         @         @^    \
  18        ---6--  /         / |     33
  /               \/         /  |      \
 /                /\    -----   |       @
s           --5--- |   /        |        t
 \         /       |  /         |       @
  27      |  ----2-|--         /       /
   \      | /      |  /----8---       7
    \     |/       @  |              /
     ---->e----9-->f------6---->g----
           \          |    |   @
            \         |       /
             --5----->h---4---
    ").unwrap();

let s = nodes[&'s'];
let t = nodes[&'t'];

assert_eq!(g.num_edges(), 18);

let (value, flow, mut mincut) = pushrelabel(&g, s, t, |e| upper[e.index()]);
assert_eq!(value, 29);

let mincutval = g
    .edges()
    .filter(|&e| mincut.contains(&g.src(e)) && !mincut.contains(&g.snk(e)))
    .map(|e| upper[e.index()])
    .sum::<usize>();
assert_eq!(value, mincutval);

mincut.sort_by_key(|u| u.index());
assert_eq!(mincut, "bcsef".chars().map(|v| nodes[&v]).collect::<Vec<_>>());

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

Structs

PushRelabel

The push-relabel algorithm.