Maximum Flow Algorithm
Overview
Maximum Flow Algorithms are intended to solve the problem of how to optimally move something with discrete quantities through a network of connected nodes with fixed capacities. Two points of clarification:
- Discrete quantities: Anything with variable quantity that can be separated into units (e.g. water, people, cars, trains).
- Connected nodes with fixed capacities: Typically, we’re referring to the edges that have fixed capacities that connect these nodes (i.e. vertices).
A list of algorithms to solve these problems can be found in the Wikipedia article for Maximum Flow Problem.
This blog post will examine nuances of this problem while comparing a couple of its pioneering algorithms:
Table of Contents
Simplified Glossary
- Source: Node in a graph where the discrete quantities flow from.
- Sink: Node in a graph where the discrete quantities flow to.
- Residual graph: Graph with the remaining capacity before or after a path has been augmented.
- Augmenting path: Path that does not contain cycles from the source to the sink in a residual graph.
Ford-Fulkerson
Ford-Fulkerson is more of a method or guideline (than an algorithm) for how to solve maximum flow problems (as well as other graphing problems). It provides an outline for systematically discovering the maximum sum of bottlenecks that exist in a graph between a source and sink. The systematic nature of Ford-Fulkerson enables its algorithms to make continual progress without having to backtrack or undo any past history in earlier iterations. How one finds augmenting paths is up to the implementation of Ford-Fulkerson.
A Ford-Fulkerson algorithm can use either DFS (Depth-First Search) or BFS (Breadth-First Search), however, the original description of Ford-Fulkerson uses DFS.
Each iteration often augments the flow moving through a path by the bottleneck (edge with the least residual capacity) in that path. This is a problem if augmenting paths are processed in a suboptimal order such that longer paths with tighter bottlenecks are processed before others. This problem is solved by an optimization that is addressed in Edmonds-Karp in the way that the next augmenting path is chosen to increment the flow.
Edmonds-Karp
Edmonds-Karp is an implementation of Ford-Fulkerson. It prioritizes choosing augmenting paths based on the fewest number of edges between the source and the sink (using BFS) to prioritize paths with greater potential flow, often decreasing the total number of iterations in the algorithm, but not always.
Performance
The worst-case time complexity of Ford-Fulkerson is O(E*mf) where mf is the maximum flow (which isn’t discovered until the algorithm completes). This is because there exists a potential for a single bottleneck bidirectional edge that is not connected to either source or sink. This path should ideally not be used at all. This worst case assumes this edge has a minimum possible value of 1 (assuming integer units) to restrict the flow of each iteration as the suboptimal route is incremented, using this path in a back-and-forth switch behavior.
This situation wouldn’t occur with Edmonds-Karp because it begins processing the shortest paths, so these cases are skipped. It has a worst-case time complexity of O(V*E2).
This blog post is categorized as Advanced in Software.Land because: A-> Software.Land is aimed at those who have never written a line of code before, and B-> these algorithms are seldom used by professionals in software engineering other than in niche specializations. It is the first blog post that is academically, rather than practically, oriented based on the search term (but not the last).
To be updated with a closer look at performance, as well as a look into capacities that are defined on the nodes instead. More background on residual graphs is also merited.
Author
Sam Malayek works in Vancouver, using this space to fill in a few gaps. Opinions are his own.