Network Flow Calculator (Max Flow)

About Network Flow Calculator (Max Flow)

The Network Flow Calculator computes the maximum flow from a chosen source s to a chosen sink t in any capacitated directed network. Under the hood it runs the Ford-Fulkerson method with breadth-first augmenting paths (the Edmonds-Karp algorithm), then records every path it found so you can replay the entire decision process one iteration at a time. The result page also surfaces the min-cut — the bottleneck partition that proves your flow value is truly optimal.

What Is the Maximum Flow Problem?

A flow network is a directed graph G = (V, E) together with a capacity function c: E → ℝ_≥0. Two vertices are distinguished: the source s (where flow originates) and the sink t (where it is consumed). A flow f is any assignment f(u, v) ≥ 0 on edges that obeys:

The maximum flow problem asks for the flow f that maximises |f|. Intuitively: if the edges were water pipes with the given capacities, how many litres per second can you ship from s to t?

How the Algorithm Works — Ford-Fulkerson with BFS

The algorithm maintains a residual graph alongside the current flow. For every edge (u, v) with capacity c and current flow f, the residual graph contains:

• a forward residual edge (u, v) with capacity c − f (how much more can still be pushed), and
• a reverse residual edge (v, u) with capacity f (how much of the committed flow can still be cancelled).

At each iteration it performs a breadth-first search from s to t over the residual graph. If a path is found, the smallest edge capacity on the path — the bottleneck — is added to flow on every forward edge and subtracted on every reverse edge along the path. This is called an augmenting path. When BFS can no longer reach t, the current flow is optimal.

Using BFS (rather than arbitrary path-finding) turns Ford-Fulkerson into Edmonds-Karp, with a guaranteed running time of O(V · E²). It also guarantees termination on irrational capacities, which plain Ford-Fulkerson does not.

The Max-Flow Min-Cut Theorem

A cut is a partition of the vertices into two sets (S, T) with s ∈ S and t ∈ T. Its capacity is the sum of capacities of edges going from S to T:

The max-flow min-cut theorem (Ford & Fulkerson, 1956) states:

This tool finds the min-cut automatically. After Edmonds-Karp terminates, it runs one more BFS from s on the residual graph; the vertices reached form S, the rest form T, and every edge crossing S → T in the original graph is saturated. Their capacities sum to exactly the max-flow value — visible in the hero result as "Min-cut capacity ✓ confirms optimality".

Features Built for Learning

• Step-by-step animation. Replay every augmenting path with play, pause and step controls. See which path BFS picked, which edge was the bottleneck, and how the running total grew.
• Three synchronised matrices. Toggle between the capacity matrix C, the final flow matrix f, and the residual matrix C − f — the three pictures that together characterise any flow.
• Min-cut partition view. S-side and T-side vertices are listed as chips with the crossing saturated edges highlighted in red.
• Edge-by-edge table. For every edge: capacity, flow, residual, utilisation bar, and a saturation pill.
• Layered left-to-right layout. The graph drawing is computed from BFS distances from the source, so water visibly "flows" left to right — exactly how the textbooks draw it.

Input Formats

1. Edge list with capacities

One edge per line. The arrow form is most readable but several alternatives work:

Also accepted: A, B, 10 · A B 10 · A -> B , 10. Multiple edges between the same pair are summed.

2. Capacity matrix

One row per line, values separated by spaces or commas. Entry C[i][j] is the capacity of the edge from vertex i to vertex j. Use 0 for "no edge". The matrix must be square and the diagonal must be 0 (no self-loops).

Enter matching vertex labels in the Matrix labels field (comma- or space-separated). If omitted, labels default to S, A, B, …, T.

Applications of Max Flow

Worked Example

The "Textbook" quick-example encodes a 6-node network with source S and sink T. Running Edmonds-Karp yields four augmenting paths:

1. S → A → B → T with bottleneck 4 (edge A-B is the limiter). Running total: 4.
2. S → A → D → T with bottleneck 6. Running total: 10.
3. S → C → D → T with bottleneck 4 (edge D-T is now the limiter, only 4 left). Running total: 14.
4. S → C → D → B → T with bottleneck 5. Running total: 19.

The algorithm stops — no more augmenting paths exist. The min-cut is (S = {S, C}, T = {A, B, D, T}) with crossing edges S → A (capacity 10) and C → D (capacity 9), summing to 19 — exactly the max flow value.

How to Use This Calculator

1. Choose input format using the tabs — edge list (recommended) or capacity matrix.
2. Enter your network. You can start from a quick example and modify it. For matrix input, also supply labels if you want names other than S, A, B, …, T.
3. Specify source and sink (or leave blank to auto-detect S and T).
4. Click Compute Max Flow. The result page shows the max flow value, min-cut partition, a layered graph visualisation, every augmenting path, an edge utilisation table, and three matrices (capacity, flow, residual).
5. Play the animation beneath the graph to replay the algorithm's decisions. Click any augmenting-path step to jump directly to it.

Limits

• Vertices: up to 30 — keeps the visualisation and matrices readable.
• Edges: up to 200.
• Capacities: non-negative, up to 10⁹. Fractional capacities are allowed.
• No self-loops. Self-loops carry no flow in a standard max-flow formulation and are rejected.

Frequently Asked Questions

What is the maximum flow problem?

Given a directed network where each edge has a non-negative capacity, the maximum flow problem asks: how much flow can be pushed from a designated source vertex s to a designated sink vertex t, subject to the rules that flow on each edge cannot exceed its capacity and flow entering every non-source, non-sink vertex must equal the flow leaving it? The answer is called the max flow value.

What is the Ford-Fulkerson method?

Ford-Fulkerson is a general technique for computing max flow. It repeatedly finds an augmenting path from source to sink in the residual graph and pushes as much flow as possible along that path (the bottleneck capacity), then updates the residual graph. The procedure terminates when no augmenting path exists. When implemented with breadth-first search for path selection, it is called Edmonds-Karp and runs in O(V · E²) time.

What is the min-cut of a flow network?

A cut is a partition of the vertices into two sets S and T such that the source is in S and the sink is in T. The capacity of the cut is the sum of capacities of edges from S to T. A min-cut is a cut of minimum capacity. The famous max-flow min-cut theorem proves that the maximum flow value always equals the minimum cut capacity, so finding one gives you the other for free.

What is the residual graph?

The residual graph tracks how much more flow can still be pushed on each edge. For every original edge (u, v) with capacity c and current flow f, the residual graph contains a forward edge (u, v) with capacity c minus f (remaining capacity) and a reverse edge (v, u) with capacity f (cancellable flow). An augmenting path uses edges of the residual graph, allowing the algorithm to undo earlier decisions.

Why does the tool use BFS for augmenting paths?

Choosing augmenting paths with breadth-first search (Edmonds-Karp) guarantees polynomial-time termination regardless of the edge capacities. Plain Ford-Fulkerson with an arbitrary path-finding strategy can loop for an exponential number of iterations on pathological inputs, and on irrational capacities it may not terminate at all. BFS also produces shortest augmenting paths, which are easier to read and reason about.

What does a saturated edge mean?

An edge is saturated when its flow equals its capacity, so no additional flow can be pushed on it. Saturated edges are bottlenecks of the network, and every min-cut consists entirely of saturated edges from the S-side to the T-side of the cut. The tool highlights saturated edges in red so you can see the bottleneck structure at a glance.

Further Reading

• Maximum flow problem — Wikipedia
• Ford–Fulkerson algorithm — Wikipedia
• Edmonds–Karp algorithm — Wikipedia
• Max-flow min-cut theorem — Wikipedia