# Understanding the Maximum Flow algorithm

## Sample applications

1. Given a list of connected pipes with different flow-capacities, find the amount of water that can go from a starting point to a given ending point.

2. You have a lot of cars that you want to take from city ‘s’ to city ‘t’. Each road between two cities has a limit on the number of cars that can go there. What is the maximum number of cars that you can take from ‘s’ to ‘t’?

The two above problems can be visualized in the following way:

In Problem 1, each letter represents a pipe, and each number represents the flow-capacity between two pipes. That is, maximum amount of water that can go from** s **to **a **is 11 units, **a **to **b** is 12 units and so on.

In Problem 2, each letter represents a city, and each number represents the maximum number of cars that can go from the two cities. Similar to the situation in Problem 1, the number of cars that can go from **s **to **a** is 11, from **a **to **b** is 12 etc.

# Solution

What is one way to solve these two problems? It is obvious that here we deal with a Network Flow problem. There are a few known algorithms: **Ford–Fulkerson algorithm, Edmond Karp algorithm and Dinic’s algorithm.**

Here we discuss the** Edmond Karp **algorithm, which is almost identical to Ford-Fulkerson, except that the search order is **defined**.

With **defined**, it means that it uses Breadth-First-Search to find the paths in terms of hops between the *source* and the *sink. *All these paths that start in *source *and end in *sink *are called **augmenting paths**.

## And then what? What do we do after we find the augmenting paths between *source *and *sink?*

Here comes the key part of the algorithm: We find the minimum edge-weight *(number in Figure 1) *that is part of our path. For example, referring to our sample graph in Figure 1, if we run BFS from **s** to **t, **initially we will end up with the first augmenting path** p1** = [ s — c — d — t ].

If we now refer to Problem 1, we can say that the minimum flow capacity of each pipe in the augmenting path **p1** lies in the edge **d — t** which is 4 units.

## And then what? What do we do after we find the minimum edge-weight in the augmenting path?

*Now we will do two important steps:*

- Decrease all the flow-capacities of the forward edges by the minimum edge-weight.
- Increase all the flow-capacities of the backward edges by the minimum edge-weight.

Considering our augmenting path **p1**, we decrease the following edges [ s-c, c-d, d-t ] and increase the backward edges [ c-s, d-c, t-d ] (if its bi-directional).

The reason for decreasing forward edges is to not mark the already used edge capacities and for increasing backward edges is to allow future flow to cancel the misused capacity used from some earlier flow.

## And then what? What do we do after we decrease and increase the flow-capacities of forward and backward edges?

We do this repeatedly until the **minimum edge capacity is 0. **That would mean that there is no more any augmenting path from **s **to **t.**

## How do we calculate the maximum flow?

To calculate the maximum flow from **s **to **t** we add all the minimum edge capacities of all the augmenting paths found.

# Pseudo Code

MAX_FLOW = 0

MIN_EDGE_W = 0

AUG_PATH = EMPTY LIST

SOURCE, SINKAUGMENT(SINK, MIN_EDGE) -> function that augments (finds the min_edge_w and increases/decreases edges)while(true):

MIN_EDGE_W = 0

RUN BFS FROMSOURCE TO SINK (storing the spanning tree in AUG_PATH)AUGMENT(SINK, MIN_EDGE) - calls the function*in this point we have found the MIN_EDGE_Wif( MIN_EDGE_W == 0 ): -> if it's 0 then stop the program

BREAKMAX_FLOW += MIN_EDGE_W -> add to max flow///RESULT INMAX_FLOW

I wrote the algorithm in C++. You can find it in my repository. Or alternatively play with the code in repl.it.

## Run the program with the sample Graph in Figure 1.

My code can only find max flow in a graph where nodes are given as numbers.

The input is in the following format:

`line 1: `**edges** #number of edges

line 2: **source sink** #given as numbers

following *edges*** **lines: **a b c **# node a,b and weight c

Output will show the max_flow and the augmenting paths.

Sample run:

in input.txt file6

0 1

0 2 100

0 3 50

2 1 5

2 4 5

4 1 125

3 4 100in output.txt fileAugmenting paths...

Path: [ 0 -> 2 -> 1 ] flow: 5

Path: [ 0 -> 2 -> 4 -> 1 ] flow: 5

Path: [ 0 -> 3 -> 4 -> 1 ] flow: 50

Maximum flow: 60

Running time? O(V*E) BFS iterations

xO(V) per BFS = O(V²*E), where V is the number of vertices and E is the number of edges

**Exercise**: Change my code to also support strings as nodes and find the max flow in Figure 1 graph and do a pull request to my repository.

*References: CP3 book by Steven Halim, Wikipedia*