Dinic's Algorithm
Dinic's algorithm is a practically fast algorithm for computing the maximum flow in a flow network.
User can create a network instance with Dinic::new(n)
where n
is the number of vertices in the network,
and add edges with Dinic::add_edges(&mut self, src, dst, cap)
method where cap
is the capacity of the edge being added.
Calling Dinic::max_flow(&mut self, src, dst)
calculates the maximum flow from src
to dst
.
After the calculation, remaining capacity of any edges can be found by directly inspecting into cap
field of a wanted edge.
Example
The example below calculates maximum flow of a flow network shown on page 5 of https://github.com/justiceHui/SSU-SCCC-Study/blob/master/2022-winter-adv/slide/02.pdf.
use dinic::Dinic; fn main() { let mut dn = Dinic::new(4); for (src, dst, cap) in [(0, 1, 2), (0, 2, 2), (1, 2, 1), (1, 3, 2), (2, 3, 2)] { dn.add_edge(src, dst, cap); } let (src, dst) = (0, 3); let max_flow = dn.max_flow(src, dst); println!("{max_flow}"); // 4 // Remaining capacity of an edge from 0 to 1 let edge = dn.g[0].iter().filter(|e| e.dst == 1).next().unwrap(); println!("{}", edge.cap); // 0 } mod dinic { //! Reference: https://github.com/justiceHui/SSU-SCCC-Study/blob/master/2022-winter-adv/slide/04.pdf use std::collections::VecDeque; #[derive(Clone)] pub struct Edge { pub dst: u32, pub opp: u32, pub cap: u64, } impl Edge { fn new(dst: usize, opp: usize, cap: u64) -> Self { Self { dst: dst as u32, opp: opp as u32, cap, } } } pub struct Dinic { pub n: usize, pub g: Vec<Vec<Edge>>, } impl Dinic { pub fn new(n: usize) -> Self { Self { n, g: vec![vec![]; n], } } pub fn add_edge(&mut self, s: usize, e: usize, cap: u64) { let sl = self.g[s].len(); let el = self.g[e].len(); self.g[s].push(Edge::new(e, el, cap)); self.g[e].push(Edge::new(s, sl, 0)); } fn bfs(&mut self, s: u32, t: u32, lv: &mut [u32]) -> bool { lv.fill(0); let mut queue = VecDeque::new(); queue.push_back(s); lv[s as usize] = 1; while let Some(v) = queue.pop_front() { for e in self.g[v as usize].iter() { if lv[e.dst as usize] == 0 && e.cap != 0 { queue.push_back(e.dst); lv[e.dst as usize] = lv[v as usize] + 1; } } } lv[t as usize] != 0 } fn dfs(&mut self, v: u32, t: u32, fl: u64, lv: &[u32], idx: &mut [u32]) -> u64 { if v == t || fl == 0 { return fl; } for i in idx[v as usize]..self.g[v as usize].len() as u32 { idx[v as usize] = i; let Edge { dst, opp, cap } = self.g[v as usize][i as usize]; if lv[dst as usize] != lv[v as usize] + 1 || cap == 0 { continue; } let now = self.dfs(dst, t, fl.min(cap), lv, idx); if now == 0 { continue; } self.g[v as usize][i as usize].cap -= now; self.g[dst as usize][opp as usize].cap += now; return now; } 0 } pub fn max_flow(&mut self, src: usize, dst: usize) -> u64 { let mut flow = 0; let mut aug; let mut lv = vec![0; self.n]; let mut idx = vec![0; self.n]; while self.bfs(src as u32, dst as u32, &mut lv) { idx.fill(0); loop { aug = self.dfs(src as u32, dst as u32, u64::MAX, &mut lv, &mut idx); if aug == 0 { break; } flow += aug; } } flow } } }
Code
mod dinic {
//! Reference: https://github.com/justiceHui/SSU-SCCC-Study/blob/master/2022-winter-adv/slide/04.pdf
use std::collections::VecDeque;
#[derive(Clone)]
pub struct Edge {
pub dst: u32,
pub opp: u32,
pub cap: u64,
}
impl Edge {
fn new(dst: usize, opp: usize, cap: u64) -> Self {
Self {
dst: dst as u32,
opp: opp as u32,
cap,
}
}
}
pub struct Dinic {
pub n: usize,
pub g: Vec<Vec<Edge>>,
}
impl Dinic {
pub fn new(n: usize) -> Self {
Self {
n,
g: vec![vec![]; n],
}
}
pub fn add_edge(&mut self, s: usize, e: usize, cap: u64) {
let sl = self.g[s].len();
let el = self.g[e].len();
self.g[s].push(Edge::new(e, el, cap));
self.g[e].push(Edge::new(s, sl, 0));
}
fn bfs(&mut self, s: u32, t: u32, lv: &mut [u32]) -> bool {
lv.fill(0);
let mut queue = VecDeque::new();
queue.push_back(s);
lv[s as usize] = 1;
while let Some(v) = queue.pop_front() {
for e in self.g[v as usize].iter() {
if lv[e.dst as usize] == 0 && e.cap != 0 {
queue.push_back(e.dst);
lv[e.dst as usize] = lv[v as usize] + 1;
}
}
}
lv[t as usize] != 0
}
fn dfs(&mut self, v: u32, t: u32, fl: u64, lv: &[u32], idx: &mut [u32]) -> u64 {
if v == t || fl == 0 {
return fl;
}
for i in idx[v as usize]..self.g[v as usize].len() as u32 {
idx[v as usize] = i;
let Edge { dst, opp, cap } = self.g[v as usize][i as usize];
if lv[dst as usize] != lv[v as usize] + 1 || cap == 0 {
continue;
}
let now = self.dfs(dst, t, fl.min(cap), lv, idx);
if now == 0 {
continue;
}
self.g[v as usize][i as usize].cap -= now;
self.g[dst as usize][opp as usize].cap += now;
return now;
}
0
}
pub fn max_flow(&mut self, src: usize, dst: usize) -> u64 {
let mut flow = 0;
let mut aug;
let mut lv = vec![0; self.n];
let mut idx = vec![0; self.n];
while self.bfs(src as u32, dst as u32, &mut lv) {
idx.fill(0);
loop {
aug = self.dfs(src as u32, dst as u32, u64::MAX, &mut lv, &mut idx);
if aug == 0 {
break;
}
flow += aug;
}
}
flow
}
}
}