Max flow algorithms
LightGraphsFlows.boykov_kolmogorov_impl
— Functionboykov_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)
LightGraphsFlows.discharge!
— Functiondischarge!(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!
— Methodenqueue_vertex!(Q, v, active, excess)
Push inactive node v
into queue Q
and activates it. Requires preallocated active
and excess
vectors.
LightGraphsFlows.gap!
— Functiongap!(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!
— Functionpush_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.relabel!
— Functionrelabel!(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!
— Functionblocking_flow!(residual_graph, source, target, capacity_matrix, flow-matrix, P)
Like blocking_flow
, but requires a preallocated parent vector P
.
LightGraphsFlows.blocking_flow
— Methodblocking_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
— Functionfunction 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!
— Methodaugment_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
— Functionedmonds_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
— Functionfetch_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!
— Functionfetch_path!(residual_graph, source, target, flow_matrix, capacity_matrix, P, S)
Like fetch_path
, but requires preallocated parent vector P
and successor vector S
.