Module rs_graph::maxflow::edmondskarp
source · Expand description
This module implements the max flow algorithm of Edmonds-Karp.
Example
use rs_graph::traits::*;
use rs_graph::maxflow::edmondskarp;
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) = edmondskarp(&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::edmondskarp;
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) = edmondskarp(&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
- Max-flow algorithm of Edmonds and Karp.
Functions
- Solve the maxflow problem using the algorithm of Edmonds-Karp.