Module rs_graph::maxflow::dinic
[−]
[src]
This module implements Dinic' max flow algorithm
Example
use rs_graph::{Builder, Graph, Digraph, Net, EdgeSlice}; use rs_graph::maxflow::dinic; let mut g = Net::new(); let mut upper = vec![]; let s = g.add_node(); let t = g.add_node(); let v1 = g.add_node(); let v2 = g.add_node(); let v3 = g.add_node(); let v4 = g.add_node(); g.add_edge(s, v1); upper.push(5); g.add_edge(s, v3); upper.push(5); g.add_edge(v1, v2); upper.push(2); g.add_edge(v1, v3); upper.push(1); g.add_edge(v1, v4); upper.push(1); g.add_edge(v2, t); upper.push(4); g.add_edge(v3, v4); upper.push(2); g.add_edge(v4, v2); upper.push(2); g.add_edge(v4, t); upper.push(5); let upper = EdgeSlice::new(&g, &upper); let (value, flow, mut mincut) = dinic(&g, s, t, &upper); assert_eq!(value, 5); assert!(g.edges().all(|e| flow[e] >= 0 && flow[e] <= upper[e])); assert!(g.nodes().filter(|&u| u != s && u != t).all(|u| { g.outedges(u).map(|(e,_)| flow[e]).sum::<isize>() == g.inedges(u).map(|(e,_)| flow[e]).sum::<isize>() })); mincut.sort_by_key(|u| u.index()); assert_eq!(mincut, vec![s, v1, v3]);
Structs
Dinic |
The dinic max-flow algorithm. |