Function edmonds_karp 

pub fn edmonds_karp(graph: &mut FlowGraph, source: usize, sink: usize) -> f64

Computes the maximum flow from source to sink using the Edmonds-Karp algorithm (Ford-Fulkerson with BFS augmenting paths).

Edmonds-Karp improves on ford_fulkerson by always choosing the shortest augmenting path (fewest edges) via BFS rather than an arbitrary path via DFS. This simple change reduces the number of augmentations from potentially O(max_flow) to O(V · E), giving a polynomial runtime guarantee regardless of capacity values.

How it works

1. BFS finds the shortest augmenting path from source to sink in the residual graph.
2. The bottleneck capacity (minimum residual along the path) is computed.
3. Flow is pushed: each forward edge’s flow increases, each reverse edge’s residual capacity increases by the same amount.
4. Repeat until BFS finds no path.

Arguments

• graph — a mutable FlowGraph; flow values are updated in place.
• source — index of the source node.
• sink — index of the sink node.

Returns

The total maximum flow value sent from source to sink.

Complexity

O(V · E²). Polynomial in all cases — safe for general use.

Examples

use graph_flow::{FlowGraph, edmonds_karp};

// CLRS Figure 26.1 style network:
//   0 --16-- 1 --12-- 3
//   |        |        |
//   13       4        20
//   |        |        |
//   2 --14-- 4 --7--- 5 (sink=5)
//   Note: simplified 4-node version below.
let mut g = FlowGraph::new(4);
g.add_edge(0, 1, 10.0);
g.add_edge(0, 2, 5.0);
g.add_edge(1, 3, 10.0);
g.add_edge(2, 3, 5.0);

let flow = edmonds_karp(&mut g, 0, 3);
assert_eq!(flow, 15.0);