- Water irrigation
- Transferring money between accounts with transfer limits
- Traffic flow in a city
- Moving electricity from production power plants to cities
Dinitz's Algorithm
Solving maxflow problems intuitively
By: Rany Tith
Graph algorithms are also just fun!
Let \(G = (V,E, c) \) be a capacited directed graph. Where we have \(c\) denote the capacity function \(c: E \rightarrow \mathbb{R}^{+}\) assigning a capacity to each edge.
The above solution tells us that there exists a flow of 19. Note that this constructed flow follows the capacity and flow constraint. This also so happens to be the max flow. And so how do we construct this flow and guarantee that it is the maximum?
\[ c_{f}(u,v) = \begin{cases} c(u,v) - f(u,v) & \text{ if } (u,v) \in E \\ 0 & \text{otherwise} \end{cases} \]
Let \(f'\) be the current flow of the graph. A blocking flow is that here is no path from source to sink in the follow graph: \[ G' = ((V, E'_{L}), s, t) \] where \[ E'_{L} =\{(u,v) : f'(u,v) < c_{f}|_{E_{L}} (u,v) \} \] Or in other words, its a graph where all the saturated edges are removed.
Input: \(G = ((V,E),c,s,t) \)
Output: A \(s-t\) path with a maximal flow
Given \(G_{f}\) we want to be able to construct the level graph.
The goal here is to given the current flow graph, give a level to each vertex if the flow on that edge is less than the capacity.
bool bfs() {
std::queue next_verts;
next_verts.push(s);
// Keeping track of distance of each vertex
level = std::vector(col_size, 0);
level[s] = 1;
while(!next_verts.empty()) {
int cur_vert = next_verts.front();
next_verts.pop();
for(unsigned int i=0; i < row_size; i++) {
// Not visited and flow is less than capacity
if (flow[cur_vert][i] < data[cur_vert][i] &&
(level[i] == 0)
) {
// Grab the current level the vert is add and every node it is connected to is + 1
level[i] = level[cur_vert] + 1;
next_verts.push(i);
}
}
}
// sink is reachable from source
return level[t] > 0;
}
Notice that there are 3 blocking flows:
Now note that the smallest capacity along these edges gives us:
This gives us in the flow for this phase to be: \[ f_{total} = f_{1} + f_{2} + f_{3} = 14 \]
int dfs(int start, int cap) {
int tmp_targ = cap;
if (start == row_size-1) {
return tmp_targ;
}
for (unsigned int i=0; i < row_size; i++) {
if (
level[i] == (level.at(start)+1) &&
flow[start][i] < data.at(start).at(i)
) {
// Grab the smallest capacity that we can find
int local_min = std::min(tmp_targ,
data.at(start).at(i) - flow.at(start).at(i));
int prop_flow = dfs(i, local_min);
flow[start][i] = flow[start][i] + prop_flow;
tmp_targ = tmp_targ - prop_flow;
}
}
return cap - tmp_targ;
}
/**
* Solves max flow problem
*/
int solve() {
int max_flow = 0;
while(bfs()) {
max_flow = max_flow + dfs(s, 100);
}
return max_flow;
}
Let us consider a single phase of Dinitz's algorithm.
First consider we have to build our level graph using BFS. During the building of the level graph it is possible that we have to visit every edge as they meet our capacity requirement and is unvisited. This gives us \(O(|E|)\) so far.Now consider our DFS to find a blocking flow which is of length \(l\). That gives us \(O(l|E|) = O(|V||E|) \) for a single phase. Now how many times is this phase done?
Proposition: There is at most \(|V| - 1\) phases of Dinitiz's algorithm.
Proof: Notice that the distance between the source and target cannot exceed the number of vertices minues one.
Thus we have in total \(O(|V|^{2}|E|)\).
Model name: 11th Gen Intel(R) Core(TM) i5-1135G7 @ 2.40GHz
CPU family: 6
Model: 140
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
Stepping: 1
CPU max MHz: 4200.0000
CPU min MHz: 400.0000
...
Caches (sum of all):
L1d: 192 KiB (4 instances)
L1i: 128 KiB (4 instances)
L2: 5 MiB (4 instances)
L3: 8 MiB (1 instance)
...
total used free shared buff/cache available
Mem: 31Gi 3.0Gi 23Gi 1.9Gi 4.8Gi 25Gi
Swap: 8.0Gi 0B 8.0Gi
Instead of using adjacency matrices you can use compressed sparse row matrix.
Consider: \[ \begin{pmatrix} 0 & 119 & 116 & 0 & 0 & 0 \\ 0 & 0 & 244 & 237 & 0 & 0 \\ 0 & 0 & 0 & 108 & 188 & 0 \\ 0 & 0 & 0 & 0 & 101 & 182 \\ 0 & 0 & 0 & 0 & 0 & 204 \end{pmatrix} \]
We can reduce this matrix to CSR format: \[ \text{offsets} = \begin{pmatrix} 1 & 3 & 5 & 7 & 9 & 10 & 0 \\ \end{pmatrix} \] \[ \text{end_vert} = \begin{pmatrix} 2 & 3 & 3 & 4 & 4 & 5 & 5 & 6 & 6 \end{pmatrix} \] \[ \text{weights} = \begin{pmatrix} 119 & 116 & 244 & 237 & 108 & 188 & 101 & 182 & 204 \end{pmatrix} \]Runtime:
| Size (nxn) | CSR (s) | Adj Matr. (s) |
|---|---|---|
| 5 | 2.22E-05 | 2.77E-05 |
| 100 | 0.0003850460052 | 0.006009817123 |
| 500 | 0.002076864243 | 0.5234670639 |
| 1000 | 0.004136323929 | 2.249393702 |
| 1500 | 0.006240844727 | 10.91037941 |
A dynamic tree is a data structure that contains multiple trees (forest). In particular, this data structure allows us to do the following:
findroot(v) returns the root of the tree containing vertex v.
findcost(v) returns a pair (w,x). x is the minimum weight on the tree path of v to findroot(v). w is the last vertex on the path with weight v.
addcost(v,x) adds x to the cost of every vertex on the path v to findroot(v).
During depth first search when finding the blocking flow we can speed up Dinitz's algorithm by using a dynamic tree. Normally DFS will have an asymptotic runtime of \(O(|V||E|)\). However, by using a dynamic tree to reuse visited paths on \(G_{f}\) we can have a run time of \(O(|E|\log(|V|))\) for finding a blocking flow instead. This gives us a total runtime of \(O(|V||E|\log(|V|))\).
Note that we can add to the flow of our graph by using addcost(v,x). We can also find the portion of the blocking path by using findcost(v). In other words, we can start DFS until we run into a vertex that is in our dynamic tree, then use the dynamic tree to find the rest of the cost from there.
Input:
a flow network G = (V, E, c, s, t)
a feasible flow f, in G (equal to zero by default)
Initialization:
compute ∀e ∈ E: c_f(e) = c(e) - f(e);
dowhile
begin
compute ∀e ∈ V: rank(v) = dist(v,t), by BFS from t on edges with c_f > 0
in the inverse edge direction;
if ranks(s) = infinity then begin f = c - c_f; return f; end;
while DFS from s do
begin
any edge (x,y) s.t. c_f(x,y) = 0 or rank(y) != rank(x)-1 is skipped;
if (x == t) then
begin
/* P denotes current DFS path */
epsilon = min {c_f(e): e is in P};
for edges (v,u) of P, from t downto s do
begin
c_f(v,u) = c_f(v,u) - epsilon;
c_f (u,v) = = c_f(u,v) + epsilon
if c_v(u,v) = 0 then x = u;
end
end
end
end
Ask me anything (AMA)
Longer than it should have.
See above.
Yes 😀
Using amortized analysis, the proof I saw uses the potential method. Very cool stuff.