## Lecture 20. Network Flow
- Flow network & Maximum flow problem
- Ford-Fulkerson Algorithm
- Minimum Cut
- Dinic's Algorithm
Note:
https://www.hackerearth.com/practice/algorithms/graphs/maximum-flow/tutorial/
https://cp-algorithms.com/graph/edmonds_karp.html#flow-network
---
### Flow Network
- A flow network is defined as a directed graph involving a **source**(`S`) and a **sink**(`T`) and several other nodes connected with edges. Each edge has an individual **capacity** which is the maximum limit of flow that edge could allow.
- A **flow** in a flow network is function $f$ , that again assigns each edge $e$ a non-negative integer value, namely the flow.
---
#### Flow Network
Flow in the network:
- The source vertex $s$ only has an outgoing flow, and the sink vertex $t$ has only incoming flow.
- For any non-source and non-sink node, the input flow is equal to output flow.
- For any edge $e$ in the network, the flow of an edge cannot exceed the capacity: $0 \le f(e) \le c(e)$.
- Total flow out of the source node is equal total to flow in to the sink node.
---
#### Flow Network
- Flow network: The first value of each edge represents the flow, which is initially 0, and the second value represents the capacity.
<img src="https://cdn.ucode.vn/uploads/1/upload/HfMvRVSn.png" class="element-left content-img" />
---
#### Flow Network
In this chapter, we focus on the following two problems:
- Finding a **maximum flow**: What is the maximum amount of flow we can send from a node to another node?
- Finding a **minimum cut**: What is a minimum-weight set of edges that separates two nodes of the graph?
---
#### Maximal Flow
- How much **water** can we push through the pipes from the source to the sink?
- The **value of the flow** of a network is the sum of all the flows that get produced in the source $s$ , or equivalently to the sum of all the flows that are consumed by the sink $t$ .
- A **maximal flow** is a flow with the maximal possible value.
---
#### Maximal Flow
<img src="https://cdn.ucode.vn/uploads/1/upload/GZUvfNeR.png" class="element-left content-img" />
<img src="https://cdn.ucode.vn/uploads/1/upload/KCMWydIh.png" class="element-left content-img" />
---
#### Maximal Flow
<img src="https://cdn.ucode.vn/uploads/1/upload/DmyjFQWB.png" class="element-left content-img" />
<img src="https://cdn.ucode.vn/uploads/1/upload/sVPbnAFO.png" class="element-left content-img" />
---
#### Minimum cut
<img src="https://cdn.ucode.vn/uploads/1/upload/enzbIDpG.png" class="element-left content-img" width="60%"/>
- A maximum flow and a minimum cut are always **equally large**, so the concepts are two sides of the same coin.
---
#### Ford-Fulkerson Algorithm
- The Ford–Fulkerson algorithm finds the **maximum flow** in a graph.
- The algorithm begins with an **empty flow**, and at each step finds a **path** from the source to the sink that **generates more flow** until the maximum flow has been found.
---
### Ford-Fulkerson Algorithm
- Each original edge has a **reverse edge** in another direction. The weight of each edge indicates how much more flow we could route through it.
- At the beginning of the algorithm, the weight of each original edge equals the capacity of the edge and the weight of each reverse edge is **zero**.
<img src="https://cdn.ucode.vn/uploads/1/upload/DmyjFQWB.png" class="element-left content-img" />
<img src="https://cdn.ucode.vn/uploads/1/upload/vgJSxygf.png" class="element-left content-img" />
---
#### Ford-Fulkerson Algorithm
- On each round, the algorithm finds **any path** from the source to the sink such that each edge on the path has a **positive weight**.
<img src="https://cdn.ucode.vn/uploads/1/upload/coBykWKu.png" class="element-left content-img" width="60%" />
---
#### Ford-Fulkerson Algorithm
- The flow then increases by x units, where x is the smallest edge weight on the path
- The weight of each edge on the path decreases by x and the weight of each reverse edge increases by x.
<img src="https://cdn.ucode.vn/uploads/1/upload/coBykWKu.png" class="element-left content-img" />
<img src="https://cdn.ucode.vn/uploads/1/upload/UdrKUyte.png" class="element-left content-img" />
---
#### Ford-Fulkerson Algorithm
- The algorithm increases the flow as long as there is a path from the source to the sink through positive-weight edges.
<img src="https://cdn.ucode.vn/uploads/1/upload/elzsjDJM.png" class="element-left content-img" />
---
#### Ford-Fulkerson Algorithm
<img src="https://cdn.ucode.vn/uploads/1/upload/elzsjDJM.png" class="element-left content-img" />
<img src="https://cdn.ucode.vn/uploads/1/upload/tDUhbdOY.png" class="element-left content-img" />
---
#### Ford-Fulkerson Algorithm
- Two more rounds before reaching the maximum flow: eg., 1→2→3→6 and 1→4→5→3→6. Both paths increase the flow by 1, and the final graph:
<img src="https://cdn.ucode.vn/uploads/1/upload/URtiIhhS.png" class="element-left content-img" width="60%" />
- The algorithm terminates and the maximum flow is 7.
---
#### Ford-Fulkerson Algorithm: Finding paths
- The efficiency of the algorithm depends on the way the paths are chosen.
- A simple way: DFS. In the worst case, each path only increases the flow by 1 and the algorithm is slow.
- The complexity of Ford-Fulkerson is $O(m F)$ , where $F$ is the maximal flow of the network.
---
#### Ford-Fulkerson Algorithm: Finding Paths
- **Edmonds–Karp algorithm**: using BFS for finding augmenting paths
- Chooses each path so that the number of edges on the path is as small as possible $\rightarrow$ this guarantees that the flow increases quickly, and the time complexity of the algorithm is $O(m^2n)$.
---
#### Ford-Fulkerson Algorithm: Finding Paths
- **Scaling algorithm**: uses DFS to find paths where each edge weight is at least a **threshold value**.
- If a path cannot be found, the threshold value is divided by $2$.
- $O(m^2 \log c)$, where $c$ is the initial threshold value.
---
### Minimum cuts
- Once the Ford–Fulkerson algorithm has found a maximum flow, it has also determined a **minimum cut**.
- Let $A$ be the set of nodes that can be reached from the source using positive-weight edges. In the example graph, A contains nodes 1, 2 and 4.
<img src="https://cdn.ucode.vn/uploads/1/upload/hNjjYxjH.png" class="element-left content-img" />
---
#### Minimum cuts
- Now the minimum cut consists of the edges of the original graph that **start** at some node **in A**, **end** at some node **outside A**, and whose capacity is **fully used** in the maximum flow.
- In the below graph, such edges are 2 → 3 and 4 → 5, that correspond to the minimum cut 6 + 1 = 7.
<img src="https://cdn.ucode.vn/uploads/1/upload/hNjjYxjH.png" class="element-left content-img" />
---
#### Ford-Fulkerson Algorithm: Another example
<img src="https://cdn.ucode.vn/uploads/1/upload/HZgfYKdK.png" class="element-left content-img" />
- **Augmenting Path**: It is the path available in a flow network.
- **Residual Graph**: It represents the flow network that has additional possible flow.
- **Residual Capacity**: It is the capacity of the edge after subtracting the flow from the maximum capacity.
---
#### Ford-Fulkerson Algorithm
- The flow of all the edges is 0 at the beginning.
<img src="https://cdn.ucode.vn/uploads/1/upload/HZgfYKdK.png" class="element-left content-img" />
---
#### Ford-Fulkerson Algorithm
- Select any arbitrary path from $S$ to $T$. In this step, we have selected path $S-A-B-T$
<img src="https://cdn.ucode.vn/uploads/1/upload/ESAUrYVD.png" class="element-left content-img" />
---
#### Ford-Fulkerson Algorithm
- The minimum capacity among the three edges is $2$ ($B-T$). Update the flow/capacity for each path.
<img src="https://cdn.ucode.vn/uploads/1/upload/zDipYdWM.png" class="element-left content-img" />
---
#### Ford-Fulkerson Algorithm
- Select another path $S-D-C-T$. The minimum capacity among these edges is $3$ ($S-D$)
<img src="https://cdn.ucode.vn/uploads/1/upload/zvBkMXbm.png" class="element-left content-img" />
---
#### Ford-Fulkerson Algorithm
- Update the capacities according to this
- No more augumenting path $\rightarrow$ maximum flow: $5$.
<img src="https://cdn.ucode.vn/uploads/1/upload/skYOOHUc.png" class="element-left content-img" />
---
#### Ford-Fulkerson Algorithm
```python=
from collections import defaultdict
class Graph:
def __init__(self, graph):
self.graph = graph
self.N = len(graph)
def bfs(self, s, t, parent):
visited = [False] * self.N
queue = [s]
visited[s] = True
while queue:
u = queue.pop(0)
for ind, val in enumerate(self.graph[u]):
if not visited[ind] and val > 0:
queue.append(ind)
visited[ind] = True
parent[ind] = u
return visited[t]
def ford_fulkerson(self, source, sink):
parent = [-1] * self.N
max_flow = 0
while self.bfs(source, sink, parent):
path_flow = float("Inf")
s = sink
while s != source:
path_flow = min(path_flow, self.graph[parent[s]][s])
s = parent[s]
# Adding the path flows
max_flow += path_flow
# Updating the residual values of edges
v = sink
while v != source:
u = parent[v]
self.graph[u][v] -= path_flow
self.graph[v][u] += path_flow
v = parent[v]
return max_flow
```
---
#### Ford-Fulkerson Algorithm
```python=
graph = [[0, 8, 0, 0, 3, 0],
[0, 0, 9, 0, 0, 0],
[0, 0, 0, 0, 0, 2],
[0, 0, 0, 0, 0, 5],
[0, 0, 7, 4, 0, 0],
[0, 0, 0, 0, 0, 0]]
g = Graph(graph)
source = 0
sink = 5
print("Max Flow: %d " % g.ford_fulkerson(source, sink))
# Max Flow: 5
```
---
### Dinic's algorithm
- Dinic's algorithm solves the maximum flow problem in $O(n^2m)$ .
- Maximum flow = minimum cut and BFS is used as a sub-routine.
Note:
https://python.algorithmexamples.com/web/graphs/dinic.html
---
#### Dinic's algorithm
- Includes construction of **level graphs** and **residual graphs** and finding of **augmenting paths** along with **blocking flow**.
- **Level graph** is one where value of each node is its shortest distance from source.
- **Blocking flow** is a flow that every path from $s$ to $t$ contains at least one edge which is **saturated** by this flow. Note that a blocking flow is not necessarily maximal.
---
#### Dinic's algorithm
<iframe width="560" height="315" src="https://www.youtube.com/embed/M6cm8UeeziI?si=dk5ZGlXO90YI858d" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" allowfullscreen></iframe>
---
#### Dinic's algorithm: Example
<img src="https://cdn.ucode.vn/uploads/1/upload/pLeCjjMw.png" class="element-left content-img" />
<img src="https://cdn.ucode.vn/uploads/1/upload/VgpbXBSE.png" class="element-left content-img" />
Note:
S-B-D-T instead of S-A-D-T
---
#### Dinic's algorithm: Example
<img src="https://cdn.ucode.vn/uploads/1/upload/JczjWjGr.png" class="element-left content-img" />
<img src="https://cdn.ucode.vn/uploads/1/upload/toyBrSgV.png" class="element-left content-img" />
---
#### Dinic's algorithm: Example
<img src="https://cdn.ucode.vn/uploads/1/upload/bYRgWnnz.png" class="element-left content-img" />
<img src="https://cdn.ucode.vn/uploads/1/upload/yFAXucwc.png" class="element-left content-img" />
---
#### Dinic's algorithm
```cpp=
struct FlowEdge {
int v, u;
long long cap, flow = 0;
FlowEdge(int v, int u, long long cap) : v(v), u(u), cap(cap) {}
};
struct Dinic {
const long long flow_inf = 1e18;
vector<FlowEdge> edges;
vector<vector<int>> adj;
int n, m = 0;
int s, t;
vector<int> level, ptr;
queue<int> q;
Dinic(int n, int s, int t) : n(n), s(s), t(t) {
adj.resize(n);
level.resize(n);
ptr.resize(n);
}
void add_edge(int v, int u, long long cap) {
edges.emplace_back(v, u, cap);
edges.emplace_back(u, v, 0);
adj[v].push_back(m);
adj[u].push_back(m + 1);
m += 2;
}
bool bfs() {
while (!q.empty()) {
int v = q.front();
q.pop();
for (int id : adj[v]) {
if (edges[id].cap - edges[id].flow < 1)
continue;
if (level[edges[id].u] != -1)
continue;
level[edges[id].u] = level[v] + 1;
q.push(edges[id].u);
}
}
return level[t] != -1;
}
long long dfs(int v, long long pushed) {
if (pushed == 0)
return 0;
if (v == t)
return pushed;
for (int& cid = ptr[v]; cid < (int)adj[v].size(); cid++) {
int id = adj[v][cid];
int u = edges[id].u;
if (level[v] + 1 != level[u] || edges[id].cap - edges[id].flow < 1)
continue;
long long tr = dfs(u, min(pushed, edges[id].cap - edges[id].flow));
if (tr == 0)
continue;
edges[id].flow += tr;
edges[id ^ 1].flow -= tr;
return tr;
}
return 0;
}
long long flow() {
long long f = 0;
while (true) {
fill(level.begin(), level.end(), -1);
level[s] = 0;
q.push(s);
if (!bfs())
break;
fill(ptr.begin(), ptr.end(), 0);
while (long long pushed = dfs(s, flow_inf)) {
f += pushed;
}
}
return f;
}
};
```
---
#### Dinic's algorithm
```python=
INF = float("inf")
class Dinic:
def __init__(self, n):
self.lvl = [0] * n
self.ptr = [0] * n
self.q = [0] * n
self.adj = [[] for _ in range(n)]
"""
Here we will add our edges containing with the following parameters:
vertex closest to source, vertex closest to sink and flow capacity
through that edge ...
"""
def add_edge(self, a, b, c, rcap=0):
self.adj[a].append([b, len(self.adj[b]), c, 0])
self.adj[b].append([a, len(self.adj[a]) - 1, rcap, 0])
# This is a sample depth first search to be used at max_flow
def depth_first_search(self, vertex, sink, flow):
if vertex == sink or not flow:
return flow
for i in range(self.ptr[vertex], len(self.adj[vertex])):
e = self.adj[vertex][i]
if self.lvl[e[0]] == self.lvl[vertex] + 1:
p = self.depth_first_search(e[0], sink, min(flow, e[2] - e[3]))
if p:
self.adj[vertex][i][3] += p
self.adj[e[0]][e[1]][3] -= p
return p
self.ptr[vertex] = self.ptr[vertex] + 1
return 0
# Here we calculate the flow that reaches the sink
def max_flow(self, source, sink):
flow, self.q[0] = 0, source
for l in range(31): # noqa: E741 l = 30 maybe faster for random data
while True:
self.lvl, self.ptr = [0] * len(self.q), [0] * len(self.q)
qi, qe, self.lvl[source] = 0, 1, 1
while qi < qe and not self.lvl[sink]:
v = self.q[qi]
qi += 1
for e in self.adj[v]:
if not self.lvl[e[0]] and (e[2] - e[3]) >> (30 - l):
self.q[qe] = e[0]
qe += 1
self.lvl[e[0]] = self.lvl[v] + 1
p = self.depth_first_search(source, sink, INF)
while p:
flow += p
p = self.depth_first_search(source, sink, INF)
if not self.lvl[sink]:
break
return flow
```
---
## The End
{"metaMigratedAt":"2023-06-17T19:46:16.815Z","metaMigratedFrom":"YAML","breaks":true,"description":"View the slide with \"Slide Mode\".","slideOptions":"{\"theme\":\"white\"}","title":"Thuc Nguyen's ADSA Course - Lecture 20. Network Flow","contributors":"[{\"id\":\"476f9158-9a39-4a2d-bb09-ce08dd7eb978\",\"add\":16965,\"del\":539}]"}