# Network flow problem: Maximize total amount of flow from s to t

**Problem statement**

Find the maximum flow in a flow network (directed graph) from a source node to a target node subject to two constraints:

– The *flow* on edge doesn’t exceed its *capacity*

– For every node , the incoming flow is equal to outgoing flow.

Consider the graph below. The image on the left depicts the graph with its edge capacities, while the image on the right illustrates the same graph with a maximum flow of :

Notice also on the right image, that for every node , the incoming flow is equal to outgoing flow while the flow does not exceed the edge’s capacity.

**How can we find the maximum flow?**

We will do this by finding **augmenting paths** from node to . An augmenting path is a path whose edges are:

1. Non-full and forward or

2. Non-empty and backward

In other words, it is a path where the **residual capacity** is , with the residual capacity of an edge , being the total capacity minus the flow that goes through . For the above graph we can annotate the edges with their current flow and capacity. At the beginning the flow through each edge is , so their residual capacity is equal to their capacity:

The general algorithm (also known as Ford-Fulkerson algorithm) is as follows:

1. Find an augmenting path (using Breadth-first search or Depth-first search) from to

2. Compute the bottleneck capacity (i.e. an edge in the path with the smallest residual capacity)

3. Augment each edge and the total flow

4. Repeat steps 1-3 until no augmenting path can be found

The first path we can find is with a bottleneck of :

Next, we find the path with a bottleneck of :

The next path is with a bottleneck of :

Finally we cannot find any more augmenting paths so we stop with a maximum flow of .

**What if the paths we choose are different. Is the maximum flow still going to be the same?**

Let us consider choosing the following paths. First we choose the path with a bottleneck of ::

Next, we choose the path with a bottleneck of :

We then go on and choose the path . This path has a *backward edge* . We augment flow through the whole network by removing flow in that path. So when we add units of flow to the edge , we can remove units of flow the backward edge to preserve the local equilibrium. Essentially that units of flow gets transferred through edge and then for the forward edges we add the flow:

Next, we choose the path with a bottleneck of :

We then choose the path with a bottleneck of :

Next, we find the path with a bottleneck of :

Finally we cannot find any more augmenting paths so we stop with a maximum flow of .

**How do we know that this algorithm gives us the maximum flow?**

Suppose this algorithm does not give us the maximum flow. Take a maximum flow and subtract our found flow . Whats left is a valid flow . That is, there exists a path with a residual capacity (augmenting path). But, by algorithm, this path must have been found (see step 4 of algorithm). Contradiction.

**Sample implementation**

public class FordFulkerson { private static class DirectedGraph{ private Map > nodeToNeighbors; private Map > capacity; private Map > residualCapacity; public DirectedGraph() { nodeToNeighbors = new HashMap >(); capacity = new HashMap >(); residualCapacity = new HashMap >(); } public void addNode(T node) { if (!nodeToNeighbors.containsKey(node)) { nodeToNeighbors.put(node, new HashSet ()); } } public void addEdge(T start, T dest, int cap) { nodeToNeighbors.get(start).add(dest); if (!capacity.containsKey(start)) { capacity.put(start, new HashMap ()); } if (!residualCapacity.containsKey(start)) { residualCapacity.put(start, new HashMap ()); } if (!residualCapacity.containsKey(dest)) { residualCapacity.put(dest, new HashMap ()); } capacity.get(start).put(dest, cap); residualCapacity.get(start).put(dest, cap); residualCapacity.get(dest).put(start, 0); } public Set getNodes() { return nodeToNeighbors.keySet(); } public int getResidualCapacity(T start, T dest) { if (!residualCapacity.get(start).containsKey(dest)) { return 0; } else { return residualCapacity.get(start).get(dest); } } public void setResidualCapacity(T start, T dest, int f) { residualCapacity.get(start).put(dest, f); } } // Get BFS backtrack from source -> target private static Map bfs(DirectedGraph graph, String source, String target) { Map backtrack = new HashMap<>(); Set visited = new HashSet<>(); Queue queue = new LinkedList (); queue.add(source); OUTER: while (!queue.isEmpty()) { String node = queue.poll(); visited.add(node); for (String n : graph.getNodes()) { if (!n.equals(node) && !visited.contains(n)) { if (graph.getResidualCapacity(node, n) > 0) { // We have a positive residual capacity to reach n from node queue.add(n); backtrack.put(n, node); if (n.equals(target)) { break OUTER; } } } } } return backtrack; } private static int maxFlow(DirectedGraph graph, String source, String target) { int ans = 0; Map backtrack = bfs(graph, source, target); List path = new LinkedList<>(); do { // Print augmenting path and also find the bottleneck of the path path.clear(); path.add(target); String tail = target; int min = Integer.MAX_VALUE; while (backtrack.containsKey(tail)) { String prev = backtrack.get(tail); min = Math.min(min, graph.getResidualCapacity(prev, tail)); path.add(0, prev); tail = prev; } if (path.size() <= 1) { break; } System.out.println("Found augmenting path '" + path + "' with bottleneck " + min); // Update residualCapacity tail = target; while (backtrack.containsKey(tail)) { String prev = backtrack.get(tail); // Decrement residual capacity for edge prev->tail graph.setResidualCapacity(prev, tail, graph.getResidualCapacity(prev, tail) - min); // Increase residual capacity for backwards edge tail->prev (i.e. open up an edge in the opposite direction) graph.setResidualCapacity(tail, prev, graph.getResidualCapacity(tail, prev) + min); tail = prev; } // Update max flow by min ans += min; // Repeat process: find a new path backtrack = bfs(graph, source, target); } while (path.size() > 1); return ans; } public static void main(String[] args) { DirectedGraph graph = new DirectedGraph (); graph.addNode("s"); graph.addNode("A"); graph.addNode("B"); graph.addNode("C"); graph.addNode("D"); graph.addNode("t"); graph.addEdge("s", "A", 10); graph.addEdge("s", "C", 10); graph.addEdge("A", "B", 4); graph.addEdge("A", "C", 2); graph.addEdge("A", "D", 8); graph.addEdge("B", "t", 10); graph.addEdge("C", "D", 9); graph.addEdge("D", "B", 6); graph.addEdge("D", "t", 10); System.out.println("max flow = " + maxFlow(graph, "s", "t") + "\n"); // 19 graph = new DirectedGraph (); graph.addNode("A"); graph.addNode("B"); graph.addNode("C"); graph.addNode("D"); graph.addNode("E"); graph.addNode("F"); graph.addNode("G"); graph.addEdge("A", "B", 3); graph.addEdge("A", "D", 3); graph.addEdge("B", "C", 4); graph.addEdge("C", "A", 3); graph.addEdge("C", "D", 1); graph.addEdge("C", "E", 2); graph.addEdge("D", "E", 2); graph.addEdge("D", "F", 6); graph.addEdge("E", "B", 1); graph.addEdge("E", "G", 1); graph.addEdge("F", "G", 9); System.out.println("max flow = " + maxFlow(graph, "A", "G") + "\n"); // 5 } }

**References**

https://www.youtube.com/watch?v=GiN3jRdgxU4