Maxflow algorithms

Max flow algorithms

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

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

source
enqueue_vertex!(Q, v, active, excess)

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

source
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

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

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

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

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

Like blocking_flow, but requires a preallocated parent vector P.

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

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

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

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

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

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.

source