The Ford-Fulkerson Method

此方法為解決maximum flow的問題，
在閱讀這篇文章之前，
必須先知道flow network的定義。

1. Basic Concept of the Ford-Fulkerson Method

我們稱此為一個「方法」而非演算法，
是因為會因為實作的不同，而有不同的複雜度。
基本概念就是，
用一個剩餘容量圖表示flow network每條邊可以用的容量，
之後在這個剩餘容量圖中，不斷去找出一條可以走的路徑，
這條路徑會去減少每條邊的可用容量，並增加總流量。

2. Residual Networks 

每條管線有各自的流量限制，
每流過一些水，容量就會減少，
而residual network即為每條管線的剩餘容量。
一開始管線都是空的，
因此residual network的初始值即為每條管線的流量上限。

定義residual capacity c_f(u,v)為：

由flow network的限制可知，當(u,v)∈E就代表(v,u)∉E，
因此對於每一對頂點，只會剛好有其中一個case符合。

給一個flow network G=(V,E)以及一個flow f，
定義G的residual network為G_f=(V,E_f)，
其中G_f中的每條edge（residual edge）為
E_f = {(u,v)∈V x V：c_f(u,v)>0}
也就是代表residual network中每條edge可以接受一個大於0的流量。

3. Augmenting Path

在residual network中，
找一條從s->t的路徑，此路徑即為augmenting path（擴充路徑）。
也就是在residual network中，
一直嘗試去尋找這條路徑，
每條路徑都會減少剩餘的容量、以逐漸增加總流量。

給一個flow network G=(V,E)，以及其對應的residual network G_f=(V,E_f)。
若f、f'分別是G與G_f的一個flow，
定義 augmentation of flow f by f' 為一個V x V → R的函數：

一條augmenting path p即為在residual network中，
s->t的其中一條simple path。
而每條p可以增加總流量的最大值稱為residual capacity of p：
c_f(p) = min {c_f(u,v)：(u,v)在p上}

也就是為了避免從s->t的流量超出中途所經的水管負荷，
可以增加的最大流量為這條路徑的所有水管中，
容量最低的那條水管的capacity。

Introduction to Algorithms Fig. 26.4

圖(a)為一個flow network，
每條edge(u,v)上的值為f(u,v)/c(u,v)，其中|f|=19。
之後要慢慢增加每條edge上的f，使得最後|f|的值最大。
（f的詳細定義請參考：flow network）

圖(b)為圖(a)的residual network，
c_f(u,v)>0的值要加入G_f裡。
左圖舉例s<-->v₁的計算方式。


灰色的路徑為其中一條augmenting path p，
其residual capacity為c_f(p)=c_f(v₂,v₃)=4。
之後要用這條path去augment原本的flow network，
如圖(c)，path上的flow（斜線左邊），即為圖(a)的flow加上c_f(p)=4的結果；
同時用這條path去減少residual network的容量，
如圖(d)，即為c_f(u,v)-4、c_f(v,u)+4的結果。（順向容量-c_f(p)，反向容量+c_f(p)）
當capacity為0時則不顯示。

4. Max-Flow Min-Cut Theorem

給一個flow network G=(V,E)，有source s以及sink t，
若f是G裡的一個flow，則以下三個狀況會同時成立：
1. f是G的maximum flow
2. residual network G_f 沒有其他的augmenting path
3. |f| = c(S,T)，for some cut (S,T) of G

G=(V,E)的一個cut (S,T)，
為在V中切一條線分割S、T，其中T=V-S，s∈S，t∈T。
也就是用一條線將整張圖分成兩半，
其中一邊包含source，另一邊包含sink。

若f是一個flow，
則穿過cut(S,T)的net flow f(S,T)定義為：
f(S,T) = ∑(u∈S) ∑(v∈T)f(u,v) - ∑(u∈S) ∑(v∈T)f(v,u)
cut(S,T)的capacity定義為 ：
c(S,T) = ∑(u∈S) ∑(v∈T)c(u,v)

Introduction to Algorithms Fig. 26.5

u∈S、v∈T，
代表就是要計算與虛線有交集的edges。

f的計算方式，
就是從S->T的總流量，減去T->S的總流量。
而c的計算方式為S->T的總容量。

f(S,T) = f(v1,v3) + f(v2,v4) - f(v3,v2) = 19
c(S,T) = c(v1,v3) + c(v2,v4) = 26

一個flow network的minimum-cut，
就是所有cut中capacity最低的。

5. The Basic Ford-Fulkerson Algorithm

接下來我們用一個例子去實作基本的Ford-Fulkerson演算法。

Introduction to Algorithms Fig. 26.6 Part1

Introduction to Algorithms Fig. 26.6 Part2

左邊為residual network G_f，灰色的邊代表augmenting path p；
右邊為augment c_f(p)之後的結果、flow network G。

圖(a)的左邊為input graph，
如前所述，residual network每條邊的capacity初始值，
即為flow network每條邊的capacity。
其中c_f(p)=4，右邊為即為augment c_f(p)之後的結果。
（也就是path上f+4，f為0則省略不寫）

接著去更新residual graph，圖(b)的左圖即為更新後的結果。
即path上c_f(u,v)-4、c_f(v,u)+4。（順向容量-c_f(p)，反向容量+c_f(p)）
接下來一樣，
在圖(b)的左圖找一條augmenting path p，
用c_f(p)=4去augment右邊的圖。

依此類推，
圖(c)的c_f(p)=4、圖(d)的c_f(p)=7、圖(e)的c_f(p)=4，
最後到圖(f)時，residual graph已經找不到任何augmenting path了，
因此圖(e)的右圖即為maximum flow network，
其中 maximum flow = 圖(a)~圖(e) c_f(p)的總和 = 23 = |f| = f(s,v₁) + f(s,v₂)

6. The Edmonds-Karp Algorithm

在FORD-FULKERSON程式碼的第3行，
我們可以使用breadth-first search去找augmenting path，
也就是用找s->t的最短路徑（最少edges數量）的方式去找path，
以優化原本的演算法效率，
我們稱此方式為、使用Ford-Fulkerson method去實作Edmonds-Karp演算法。

例如在上圖（Fig.26.6）(a)中，
我們一開始可以直接選擇 s->v₁->v₃->t 這條路徑，(# of edges = 3)
取代原本的路徑。(# of edges = 5)


※參考資料：演算法筆記－Flow