## Max flow algorithms

`LightGraphsFlows.boykov_kolmogorov_impl`

— Function.`boykov_kolmogorov_impl(residual_graph, source, target, capacity_matrix)`

Compute the max-flow/min-cut between `source`

and `target`

for `residual_graph`

using the Boykov-Kolmogorov algorithm.

Return the maximum flow in the network, the flow matrix and the partition `{S,T}`

in the form of a vector of 0's, 1's and 2's.

**References**

BOYKOV, Y.; KOLMOGOROV, V., 2004. An Experimental Comparison of

Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision.

**Author**

Júlio Hoffimann Mendes ([email protected])

`LightGraphsFlows.discharge!`

— Function.`discharge!(residual_graph, v, capacity_matrix, flow_matrix, excess, height, active, count, Q)`

Drain the excess flow out of node `v`

. Run the gap heuristic or relabel the vertex if the excess remains non-zero.

`LightGraphsFlows.enqueue_vertex!`

— Method.`enqueue_vertex!(Q, v, active, excess)`

Push inactive node `v`

into queue `Q`

and activates it. Requires preallocated `active`

and `excess`

vectors.

`LightGraphsFlows.gap!`

— Function.`gap!(residual_graph, h, excess, height, active, count, Q)`

Implement the push-relabel gap heuristic. Relabel all vertices above a cutoff height. Reduce the number of relabels required.

Requires arguments:

residual_graph::DiGraph # the input graph

h::Int # cutoff height

excess::AbstractVector

height::AbstractVector{Int}

active::AbstractVector{Bool}

count::AbstractVector{Int}

Q::AbstractVector

`LightGraphsFlows.push_flow!`

— Function.`push_flow!(residual_graph, u, v, capacity_matrix, flow_matrix, excess, height, active, Q)`

Using `residual_graph`

with capacities in `capacity_matrix`

, push as much flow as possible through the given edge(`u`

, `v`

). Requires preallocated `flow_matrix`

matrix, and `excess`

, `height,`

active`, and`

Q` vectors.

`LightGraphsFlows.push_relabel`

— Function.`push_relabel(residual_graph, source, target, capacity_matrix)`

Return the maximum flow of `residual_graph`

from `source`

to `target`

using the FIFO push relabel algorithm with gap heuristic.

**Performance**

Takes approximately $\mathcal{O}(|V|^{3})$ time.

`LightGraphsFlows.relabel!`

— Function.`relabel!(residual_graph, v, capacity_matrix, flow_matrix, excess, height, active, count, Q)`

Relabel a node `v`

with respect to its neighbors to produce an admissable edge.

`LightGraphsFlows.blocking_flow!`

— Function.`blocking_flow!(residual_graph, source, target, capacity_matrix, flow-matrix, P)`

Like `blocking_flow`

, but requires a preallocated parent vector `P`

.

`LightGraphsFlows.blocking_flow`

— Method.`blocking_flow(residual_graph, source, target, capacity_matrix, flow-matrix)`

Use BFS to identify a blocking flow in the `residual_graph`

with current flow matrix `flow_matrix`

and then backtrack from `target`

to `source`

, augmenting flow along all possible paths.

`LightGraphsFlows.dinic_impl`

— Function.`function dinic_impl(residual_graph, source, target, capacity_matrix)`

Compute the maximum flow between the `source`

and `target`

for `residual_graph`

with edge flow capacities in `capacity_matrix`

using Dinic's Algorithm. Return the value of the maximum flow as well as the final flow matrix.

`LightGraphsFlows.augment_path!`

— Method.`augment_path!(path, flow_matrix, capacity_matrix)`

Calculate the amount by which flow can be augmented in the given path. Augment the flow and returns the augment value.

`LightGraphsFlows.edmonds_karp_impl`

— Function.`edmonds_karp_impl(residual_graph, source, target, capacity_matrix)`

Compute the maximum flow in flow graph `residual_graph`

between `source`

and `target`

and capacities defined in `capacity_matrix`

using the Edmonds-Karp algorithm. Return the value of the maximum flow as well as the final flow matrix.

`LightGraphsFlows.fetch_path`

— Function.`fetch_path(residual_graph, source, target, flow_matrix, capacity_matrix)`

Use bidirectional BFS to look for augmentable paths from `source`

to `target`

in `residual_graph`

. Return the vertex where the two BFS searches intersect, the parent table of the path, the successor table of the path found, and a flag indicating success (0 => success; 1 => no path to target, 2 => no path to source).

`LightGraphsFlows.fetch_path!`

— Function.`fetch_path!(residual_graph, source, target, flow_matrix, capacity_matrix, P, S)`

Like `fetch_path`

, but requires preallocated parent vector `P`

and successor vector `S`

.