Max-flow min-cut by Ford-Fulkerson with breadth-first augmentation

Returns both the flow value and a minimum cut. The cut is derived from the residual graph and its capacity RECOMPUTED from the original matrix rather than assumed equal, so the theorem is a check rather than a restatement.

Usage

morie_max_flow_min_cut(capacity, source = 1L, sink = NULL)

Arguments

capacity: Square non-negative matrix; capacity[i, j] is the arc capacity from i to j.
source, sink: Node indices, numbered from 1.

Value

A list with flow, cut_capacity, min_cut_source_side, theorem_holds, warnings.

References

Ford LR, Fulkerson DR (1956) Canad J Math 8:399-404.

Examples

C <- matrix(c(0, 3, 2, 0, 0, 0, 5, 2, 0, 0, 0, 3, 0, 0, 0, 0),
    4, 4, byrow = TRUE)
morie_max_flow_min_cut(C, 1, 4)
#> $flow
#> [1] 5
#> 
#> $cut_capacity
#> [1] 5
#> 
#> $min_cut_source_side
#> [1] 1
#> 
#> $cut_edges
#> $cut_edges[[1]]
#> [1] 1 2
#> 
#> $cut_edges[[2]]
#> [1] 1 3
#> 
#> 
#> $theorem_holds
#> [1] TRUE
#> 
#> $residual_gap
#> [1] 0
#> 
#> $source
#> [1] 1
#> 
#> $sink
#> [1] 4
#> 
#> $n
#> [1] 4
#> 
#> $warnings
#> character(0)
#> 
#> $method
#> [1] "Ford-Fulkerson with a verified minimum cut"
#>