## Max flow algorithms

`GraphsFlows.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 (julio.hoffimann@gmail.com)

`GraphsFlows.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.

`GraphsFlows.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.

`GraphsFlows.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

`GraphsFlows.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.

`GraphsFlows.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.

`GraphsFlows.blocking_flow!`

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

Like `blocking_flow`

, but requires a preallocated parent vector `P`

.

`GraphsFlows.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.

`GraphsFlows.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.

`GraphsFlows.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.

`GraphsFlows.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.

`GraphsFlows.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).

`GraphsFlows.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`

.