maximum_flow(flow_graph, source, target[, capacity_matrix][, algorithm][, restriction])

Generic maximumflow function for `flowgraphfromsourcetotargetwith capacities incapacity_matrix. Uses flow algorithmalgorithmand cutoff restrictionrestriction`.

• If capacity_matrix is not specified, DefaultCapacity(flow_graph) will be used.
• If algorithm is not specified, it will default to PushRelabelAlgorithm.
• If restriction is not specified, it will default to 0.

Return a tuple of (maximum flow, flow matrix). For the Boykov-Kolmogorov algorithm, the associated mincut is returned as a third output.

Usage Example:

julia> flow_graph = Graphs.DiGraph(8) # Create a flow-graph
julia> flow_edges = [
(1,2,10),(1,3,5),(1,4,15),(2,3,4),(2,5,9),
(2,6,15),(3,4,4),(3,6,8),(4,7,16),(5,6,15),
(5,8,10),(6,7,15),(6,8,10),(7,3,6),(7,8,10)
]

julia> capacity_matrix = zeros(Int, 8, 8)  # Create a capacity matrix

julia> for e in flow_edges
    u, v, f = e
    Graphs.add_edge!(flow_graph, u, v)
    capacity_matrix[u,v] = f
end

julia> f, F = maximum_flow(flow_graph, 1, 8) # Run default maximum_flow (push-relabel) without the capacity_matrix

julia> f, F = maximum_flow(flow_graph, 1, 8, capacity_matrix) # Run default maximum_flow with the capacity_matrix

julia> f, F = maximum_flow(flow_graph, 1, 8, capacity_matrix, algorithm=EdmondsKarpAlgorithm()) # Run Edmonds-Karp algorithm

julia> f, F = maximum_flow(flow_graph, 1, 8, capacity_matrix, algorithm=DinicAlgorithm()) # Run Dinic's algorithm

julia> f, F, labels = maximum_flow(flow_graph, 1, 8, capacity_matrix, algorithm=BoykovKolmogorovAlgorithm()) # Run Boykov-Kolmogorov algorithm

EdmondsKarpAlgorithm <: AbstractFlowAlgorithm

Forces the maximum_flow function to use the Edmonds–Karp algorithm.

DinicAlgorithm <: AbstractFlowAlgorithm

Forces the maximum_flow function to use Dinic's algorithm.

Forces the maximum_flow function to use the Push-Relabel algorithm.

BoykovKolmogorovAlgorithm <: AbstractFlowAlgorithm

Forces the maximum_flow function to use the Boykov-Kolmogorov algorithm.

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)

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.

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.