Struct EdmondsKarp 

pub struct EdmondsKarp { /* private fields */ }

Edmonds-Karp maximum flow algorithm.

Uses BFS to find shortest augmenting paths (Ford-Fulkerson with BFS). Time complexity: O(V E²).

Example

use scirs2_graph::flow::max_flow::EdmondsKarp;

let mut ek = EdmondsKarp::new(4);
ek.add_edge(0, 1, 10);
ek.add_edge(0, 2, 10);
ek.add_edge(1, 3, 10);
ek.add_edge(2, 3, 10);
let flow = ek.max_flow(0, 3);
assert_eq!(flow, 20);

Implementations

impl EdmondsKarp

pub fn new(n: usize) -> Self

Create a new Edmonds-Karp solver with n nodes.

pub fn add_edge(&mut self, u: usize, v: usize, cap: i64)

Add a directed edge from u to v with capacity cap.

pub fn max_flow(&mut self, source: usize, sink: usize) -> i64

Compute maximum flow from source to sink.

Trait Implementations

impl Clone for EdmondsKarp

fn clone(&self) -> EdmondsKarp

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for EdmondsKarp

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.