Unit 23: Flows

Water from the source to the sink

Every pipe has a capacity. Water enters at the source and leaves at the sink, and at every other junction as much goes out as comes in.

How much can flow at once? Here 5 — because the two pipes leaving the source hold 3 and 2, and nothing can beat that.

Python

pipes = [(0, 1, 3), (0, 2, 2), (1, 2, 1), (1, 3, 2), (2, 3, 3)]

out_of_source = sum(c for a, b, c in pipes if a == 0)
into_sink = sum(c for a, b, c in pipes if b == 3)
print(out_of_source, into_sink)

It prints

5 5

Greedy paths get stuck

Take any route with room left, push as much as it holds, repeat. On this little graph — every pipe holding 1 — the route 0, 1, 2, 3 uses up the middle pipe and blocks both of the others.

Greedy stops at 1. The real answer is 2.

Python

pipes = [(0, 1, 1), (0, 2, 1), (1, 2, 1), (1, 3, 1), (2, 3, 1)]

print("route 0-1-2-3 carries", 1)
print("then 0-1-3 is blocked at 0-1, and 0-2-3 is blocked at 2-3")
print("greedy total", 1)

It prints

route 0-1-2-3 carries 1
then 0-1-3 is blocked at 0-1, and 0-2-3 is blocked at 2-3
greedy total 1

So allow a later route to undo an earlier one

When 1 unit flows from 1 to 2, record room for 1 unit going backwards, from 2 to 1. That backwards pipe is not real — using it means cancelling part of the earlier route.

Now the route 0 to 2, backwards to 1, then 1 to 3 works, and the total is 2. The residual graph is what makes the whole subject possible.

Python

n = 4
cap = [[0] * n for i in range(n)]
for a, b, c in [(0, 1, 1), (0, 2, 1), (1, 2, 1), (1, 3, 1), (2, 3, 1)]:
    cap[a][b] = c

def push(route, amount):
    for i in range(len(route) - 1):
        a = route[i]
        b = route[i + 1]
        cap[a][b] -= amount
        cap[b][a] += amount

push([0, 1, 2, 3], 1)
print(cap[2][1], cap[1][2])
push([0, 2, 1, 3], 1)
print(cap[2][1], cap[1][2])
print("total", 2)

It prints

1 0
0 1
total 2

What the numbers mean afterwards

After the second push the middle pipe is back where it started — one route sent water through it and the other sent water back. What actually happens is 0 to 1 to 3 and 0 to 2 to 3, which is obvious in hindsight and was not obvious to the greedy walk.

The algorithm never has to be clever. It only has to be allowed to change its mind.

Find a route, push, repeat

While a route from source to sink still has room, push the most it can hold and update both directions.

Finding the route with BFS — fewest pipes — makes it Edmonds–Karp, which is guaranteed to finish in n * m * m steps. Finding it with DFS can crawl.

Python

from collections import deque

n = 4
cap = [[0] * n for i in range(n)]
for a, b, c in [(0, 1, 3), (0, 2, 2), (1, 2, 1), (1, 3, 2), (2, 3, 3)]:
    cap[a][b] += c

def find_route(source, sink):
    parent = [-1] * n
    parent[source] = source
    queue = deque([source])
    while queue:
        node = queue.popleft()
        for nxt in range(n):
            if parent[nxt] == -1 and cap[node][nxt] > 0:
                parent[nxt] = node
                queue.append(nxt)
    return parent

flow = 0
while True:
    parent = find_route(0, 3)
    if parent[3] == -1:
        break
    amount = 10 ** 9
    node = 3
    while node != 0:
        amount = min(amount, cap[parent[node]][node])
        node = parent[node]
    node = 3
    while node != 0:
        cap[parent[node]][node] -= amount
        cap[node][parent[node]] += amount
        node = parent[node]
    flow += amount
    print("pushed", amount)

print("max flow", flow)

It prints

pushed 2
pushed 2
pushed 1
max flow 5

Reading the run

Three routes, carrying 2, 2 and 1 — five in total, which matches the 5 that could possibly leave the source.

The third push is only found because the earlier ones can be partly undone. Take the backwards updates out and the answer comes out too small.

A bigger one

Six junctions and eight pipes. The answer is 7, and no amount of staring will get you there faster than running it.

This is where flow stops being something to do in your head, which is the point at which people start trusting the algorithm.

Python

from collections import deque

n = 6
cap = [[0] * n for i in range(n)]
for a, b, c in [(0, 1, 5), (0, 3, 4), (1, 2, 6), (2, 5, 8), (3, 1, 3), (3, 4, 1), (4, 5, 2), (2, 4, 3)]:
    cap[a][b] += c

def maxflow(source, sink):
    flow = 0
    while True:
        parent = [-1] * n
        parent[source] = source
        queue = deque([source])
        while queue:
            node = queue.popleft()
            for nxt in range(n):
                if parent[nxt] == -1 and cap[node][nxt] > 0:
                    parent[nxt] = node
                    queue.append(nxt)
        if parent[sink] == -1:
            return flow
        amount = 10 ** 9
        node = sink
        while node != source:
            amount = min(amount, cap[parent[node]][node])
            node = parent[node]
        node = sink
        while node != source:
            cap[parent[node]][node] -= amount
            cap[node][parent[node]] += amount
            node = parent[node]
        flow += amount

print(maxflow(0, 5))

It prints

7

The grid is for teaching, not for contests

An n by n grid of capacities is easy to read and impossible at 100000 nodes. Real code keeps an edge list where each edge stores the index of its own reverse, so the update is edge.cap -= f and reverse.cap += f.

Same algorithm, same two lines, different bookkeeping.

The narrowest place in the network

Split the junctions into the source's side and the sink's side. Add up the capacities of the pipes crossing from one side to the other: that is a cut.

No flow can beat any cut. And the astonishing part is that the best flow always equals the smallest cut.

Finding it: whatever the last search could still reach

When the flow finishes, run the search once more on what is left. The junctions it can still reach are the source's side; everything else is the sink's side.

The pipes crossing that line are exactly full, and their total is the flow.

Python

from collections import deque

n = 4
pipes = [(0, 1, 3), (0, 2, 2), (1, 2, 1), (1, 3, 2), (2, 3, 3)]
cap = [[0] * n for i in range(n)]
for a, b, c in pipes:
    cap[a][b] += c

flow = 0
while True:
    parent = [-1] * n
    parent[0] = 0
    queue = deque([0])
    while queue:
        node = queue.popleft()
        for nxt in range(n):
            if parent[nxt] == -1 and cap[node][nxt] > 0:
                parent[nxt] = node
                queue.append(nxt)
    if parent[3] == -1:
        break
    amount = 10 ** 9
    node = 3
    while node != 0:
        amount = min(amount, cap[parent[node]][node])
        node = parent[node]
    node = 3
    while node != 0:
        cap[parent[node]][node] -= amount
        cap[node][parent[node]] += amount
        node = parent[node]
    flow += amount

side = [i for i in range(n) if parent[i] != -1]
crossing = [(a, b, c) for a, b, c in pipes if a in side and b not in side]
print(flow)
print(side)
print(crossing, sum(c for a, b, c in crossing))

It prints

5
[0]
[(0, 1, 3), (0, 2, 2)] 5

Matching people to things is a flow

Three children, three books, and a list of who would read what. Give each child one book, each book to one child, as many as possible.

Make a source pointing at every child with capacity 1, every book pointing at a sink with capacity 1, and each "would read" a pipe of capacity 1. The greatest flow is the biggest matching.

Python

from collections import deque

n = 8
source = 6
sink = 7
likes = [(0, 3), (0, 4), (1, 3), (2, 4), (2, 5)]

cap = [[0] * n for i in range(n)]
for child in range(3):
    cap[source][child] = 1
for book in range(3, 6):
    cap[book][sink] = 1
for a, b in likes:
    cap[a][b] = 1

flow = 0
while True:
    parent = [-1] * n
    parent[source] = source
    queue = deque([source])
    while queue:
        node = queue.popleft()
        for nxt in range(n):
            if parent[nxt] == -1 and cap[node][nxt] > 0:
                parent[nxt] = node
                queue.append(nxt)
    if parent[sink] == -1:
        break
    node = sink
    while node != source:
        cap[parent[node]][node] -= 1
        cap[node][parent[node]] += 1
        node = parent[node]
    flow += 1

print(flow)
for a, b in likes:
    if cap[b][a] == 1:
        print(a, "reads", b)

It prints

3
0 reads 4
1 reads 3
2 reads 5

Why capacity 1 does the work

A capacity of 1 from the source means a child can be given at most one book; a capacity of 1 into the sink means a book goes to at most one child.

That is the whole modelling trick, and it is the skill flow problems are really testing: not the algorithm, which you copy, but seeing that a problem is a flow.

Now every pipe charges by the litre

Each pipe has a capacity and a price per unit. Send a required amount from source to sink as cheaply as possible.

This is how delivery lorries, job assignments and network routing are actually modelled — and it is max flow with one change.

Always augment along the cheapest route

Instead of the shortest route in pipes, take the cheapest route in money — a shortest-path search where the length of a pipe is its price.

And the backwards pipes carry the negative of the price, because undoing a unit gives the money back. Negative lengths mean Dijkstra is out and unit 9's Bellman–Ford is in.

One unit, then two, then three

Five pipes. Sending one unit costs 2, two units cost 5, and all three cost 9 — the price per unit goes up, because the cheap routes fill first.

That is always true, and it is why augmenting cheapest-first is safe: no later route can make an earlier choice look wrong.

Python

from collections import deque

def min_cost_flow(n, pipes, source, sink, need):
    graph = [[] for i in range(n)]

    def add(a, b, capacity, price):
        graph[a].append([b, capacity, price, len(graph[b])])
        graph[b].append([a, 0, -price, len(graph[a]) - 1])

    for a, b, capacity, price in pipes:
        add(a, b, capacity, price)

    big = 10 ** 9
    sent = 0
    spent = 0
    while sent < need:
        dist = [big] * n
        dist[source] = 0
        inside = [False] * n
        from_node = [-1] * n
        from_edge = [-1] * n
        queue = deque([source])
        inside[source] = True
        while queue:
            node = queue.popleft()
            inside[node] = False
            for i in range(len(graph[node])):
                nxt, capacity, price, back = graph[node][i]
                if capacity > 0 and dist[node] + price < dist[nxt]:
                    dist[nxt] = dist[node] + price
                    from_node[nxt] = node
                    from_edge[nxt] = i
                    if not inside[nxt]:
                        queue.append(nxt)
                        inside[nxt] = True
        if dist[sink] == big:
            break
        amount = need - sent
        node = sink
        while node != source:
            amount = min(amount, graph[from_node[node]][from_edge[node]][1])
            node = from_node[node]
        node = sink
        while node != source:
            edge = graph[from_node[node]][from_edge[node]]
            edge[1] -= amount
            graph[node][edge[3]][1] += amount
            node = from_node[node]
        sent += amount
        spent += amount * dist[sink]
    return sent, spent

pipes = [(0, 1, 2, 1), (0, 2, 2, 3), (1, 3, 1, 1), (1, 2, 1, 1), (2, 3, 2, 1)]
print(min_cost_flow(4, pipes, 0, 3, 1))
print(min_cost_flow(4, pipes, 0, 3, 2))
print(min_cost_flow(4, pipes, 0, 3, 3))

It prints

(1, 2)
(2, 5)
(3, 9)

Reading the answer

The first unit goes 0 to 1 to 3 and costs 2. The second goes 0 to 1 to 2 to 3 and costs 3, bringing the total to 5. The third has to use the dear pipe 0 to 2 and costs 4, so 9.

Ask for more than the network can carry and it stops early, returning what it managed — which is what the sent value is for.