Maximum flow / minimum cut

Formula: Ford-Fulkerson augmentation with Edmonds-Karp's rule that the augmenting path is always a SHORTEST one in the residual graph (breadth-first search), bounding the number of augmentations by O(V E) and making the procedure terminate on irrational capacities.

Usage

Flowmm(G, source, sink)

Arguments

G

Square non-negative capacity matrix; G[i, j] is the capacity of the directed arc i -> j.

source, sink

Zero-based vertex indices; must differ.

Value

List with estimate, max_flow, min_cut, cut_size, source_side, augmentations, n, method.

Details

On termination the vertices reachable from the source in the residual graph form the source side S of a minimum cut, and the max-flow min-cut theorem says cap(S, V \ S) equals the value of the flow. Both numbers are computed by separate routes and returned, so their equality is checkable rather than assumed.

References

Ford & Fulkerson (1956), Canadian Journal of Mathematics 8:399-404, doi:10.4153/CJM-1956-045-5; Edmonds & Karp (1972), JACM 19(2):248-264, doi:10.1145/321694.321699.

Examples

G <- matrix(c(0, 3, 2, 0, 0, 0, 1, 2, 0, 0, 0, 3, 0, 0, 0, 0), 4, 4, byrow = TRUE)
Flowmm(G, source = 0, sink = 3)
#> $estimate
#> [1] 5
#> 
#> $max_flow
#> [1] 5
#> 
#> $min_cut
#> [1] 5
#> 
#> $cut_size
#> [1] 1
#> 
#> $source_side
#> [1] 0
#> 
#> $augmentations
#> [1] 3
#> 
#> $n
#> [1] 4
#> 
#> $method
#> [1] "Maximum flow / minimum cut"
#> 
#> attr(,"class")
#> [1] "morie_rich_result" "list"