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 (juliohm@stanford.edu)

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.

enqueue_vertex!(Q, v, active, excess)

Push inactive node v into queue Q and activates it. Requires preallocated active and excess vectors.

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

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, andQ` vectors.

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.

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.

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

Like blocking_flow, but requires a preallocated parent vector P.

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_matrixand then backtrack from target to source, augmenting flow along all possible paths.

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.

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.

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.

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

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.