Module rs_graph::maxflow::pushrelabel
source · Expand description
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::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) = pushrelabel(&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::pushrelabel;
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--- 7
\ |/ @ | /
---->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) = 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| g.id2node(nodes[&v])).collect::<Vec<_>>());
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>()
}));
Structs
- The push-relabel algorithm.
Functions
- Solve the maxflow problem using the push-relabel algorithm.