[−][src]Module rs_graph::maxflow::edmondskarp
This module implements the max flow algorithm of Edmonds-Karp.
Example
use rs_graph::traits::*; use rs_graph::maxflow::edmondskarp; use rs_graph::{EdgeVec, 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 = nodes[&'s']; let t = nodes[&'t']; let v1 = nodes[&'a']; let v2 = nodes[&'b']; let v3 = nodes[&'c']; let v4 = nodes[&'d']; let (value, flow, mut mincut) = edmondskarp(&g, s, t, |e| upper[e.index()]); assert_eq!(value, 5); assert!(g.edges().all(|e| flow[e] >= 0 && flow[e] <= upper[e.index()])); assert!(g.nodes().filter(|&u| u != s && u != t).all(|u| { g.outedges(u).map(|(e,_)| flow[e]).sum::<usize>() == g.inedges(u).map(|(e,_)| flow[e]).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::{EdgeVec, 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 = nodes[&'s']; let t = 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| nodes[&v]).collect::<Vec<_>>());
Structs
EdmondsKarp | Max-flow algorithm of Edmonds and Karp. |