Skip to main content

Maximum Flow

Description​

Maximum Flow problem in optimization theory regards finding the maximum possible flow going through a flow network from source to sink nodes. A flow network, or a transportation network, is a directed graph with edge weights representing flow capacity. The incoming flow must equal outgoing flow for every node, except the source and sink nodes. Such networks can be used to model computer networks, fluids in pipes, currents in an electrical circuit, road and railway networks.

Having a variety of applications, max flow can be used for maximum matching, edge-disjoint paths and node-disjoint paths, to name a few. The max-flow min-cut theorem states that having found a maximum flow of a graph, we can also find its minimum cut.

Multiple algorithms exist for solving the Maximum Flow problem, such as the Ford-Fulkerson method, Edmonds-Karp and push-relabel algorithm.

maximum-flow-algorithm

Example of augmenting paths in max flow with edge property -> {flow / capacity}, max flow is 19, the sum of inflows to sink (or outflows from source)

Materials​

Implementation​

Maximum Flow

Maximum Flow

Maximum Flow is implemented as part of the MAGE project. Be sure to check it out in the link above. ☝️

Use cases​

Transportation

In transportation networks, max flow can be used for finding the throughput of a network or a part of it, finding the road or railway with the largest load or analysing which roads need to be expanded.

Telecommunication

Finding max flow means calculating the maximum throughput of a network, as well as identifying which connections are heavily relied upon.

Power Grids

Relevant for calculating the capacity of a power network.