Module rs_graph::maxflow::dinic

This module implements Dinic’ max flow algorithm

Example

use rs_graph::traits::*;
use rs_graph::maxflow::dinic;
use rs_graph::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 = g.id2node(nodes[&'s']);
let t = g.id2node(nodes[&'t']);
let v1 = g.id2node(nodes[&'a']);
let v2 = g.id2node(nodes[&'b']);
let v3 = g.id2node(nodes[&'c']);
let v4 = g.id2node(nodes[&'d']);

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

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

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

use rs_graph::traits::*;
use rs_graph::maxflow::dinic;
use rs_graph::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---       6
    \     |/       @  |              /
     ---->e----9-->f------6---->g----
           \          |        @
            \         |       /
             --5----->h---4---
    ").unwrap();

let s = g.id2node(nodes[&'s']);
let t = g.id2node(nodes[&'t']);

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

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

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

Structs

• Dinic
  The dinic max-flow algorithm.

Functions

• dinic
  Solve the maxflow problem using the algorithm of Dinic.