# Maximum Flow Algorithm

March 08, 2024

## 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*E^{2}).

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