# ***push-relabel 演算法***
在閱讀本篇前，若先閱讀過前一篇
https://hackmd.io/@ePnWCUeGTEWuQzDUZZZkHw/Hyekh6h39
關於 *Edmonds-karp* 演算法觀念，會對接下來的內容有比較好的理解
與 *Edmonds-karp* 不同的是 , *Edmonds-karp* 在每個階段針對 *residual network* 中
from s to t 的 *path* , 也就是針對一整條路徑(多個點)來看
而 *push-relabel* 則是在每個階段針對每個點的 *flow* 值做操作
## ***excess flow***
*push-relabel* 裡 , 我們將每一個 vertex 視為一個容器 , 每個容器會有流進及流出的 flow
一個合法的 *flow network* , 對於所有除了$\{s , t\}$之外的點 , 流進以及流出的 flow 要相等
若有容器的流進大於流出 (此演算法的流程不會有流出大於流進的狀況)
則稱此點(容器) *overflowing*
對於一點 $u$
定義 *excess flow* : $e(u) = \displaystyle\sum_{v \in V}f(v,u) - \displaystyle\sum_{v \in V}f(u,v)$
即是所有流進減去流出的
當 $u$ *overflowing* 時 , $e(u) > 0$
## ***height function***
*height function* 為代表一個點的高度的函式，$h(u)$ 及是 $u$ 點的高度
此高度會決定 flow 的流向，同時能將時間複雜度限制在一定的大小內(後面證明)
當一個點$u\in V-\{s,t\}$ *overflowing*了，則會需要將 flow 分給別的點
我們把 flow 分給別點的這個動作稱作 push , 若想 push from $u$ to $v$，則有兩條件
- $(u,v) \in E_f$
- $h(u) - 1 = h(v)$
若不存在此 $v$ , 也就是沒有人可分 , 無法 *push* 時
我們就會讓 $u$ 點的高度增加，也就是增加 $h(u)$ , 使他能找到可 *push* 之 $v$
我們把增加高度的這個動作稱作 *relabel*
$h(s)$ 恆等於 $|V|$
並且 $h(t)$ 恆等於 0 , 不會有 *push* 或 *relabel* 發生在 $t$ 上 (因 $t$ 是要匯集的點)
這就是 *push-relabel* 的概念
## ***push***
$u\in V-\{s,t\} \ , \ e(u) > 0$
$v$ 為 $u$ 要 *push* 的對象
$val$ 為 *push* 的大小 , $val = min(e(u)\ ,\ c_f(u,v))$
不能 *push* 超過 $c_f(u,v)$，這是理所當然的
此時 , $e(u)$ -= $val$ , $e(v)$ += $val$
$c_f(u,v)$ -= $val$ , $c_f(v,u)$ += $val$
若 *push* 完後 $c_f(u,v)=0$，則此 *push* 稱作 *saturating push*, 反之稱作 *unsaturating push*
若 $e(u)$ 在此 *push* 完之後仍大於 0 , 則要繼續找到其他點push
若已經沒有點可以 push，進行 *relabel*
## ***relabel***
承上的 $u$ 點，*relabel* 會找到所有的 $v$ 點 $\in V$ , $(u,v) \in E_f$
且更新 $h(u)$
$h(u) = min(h(v))+1$
能確定當 $u$ *overflowing* 時 , 至少有一點 $(u,v) \in E_f$
因為要能 *overflowing* 需要有 $v$ 點給予 $u$ flow，則此時 $c_f(u,v)$ 就會>0
也就是$(u,v) \in E_f$
在更新完值後，就能繼續 *push*，因為 $h(u) = h(v)+1$ 且 $(u,v) \in E_f$
## ***演算法流程***
為了方便比較，這裡採用跟 *edmonds-karp* 一樣的圖
*push-relabel* 針對點的 $e$ 及 $h$，而不是針對$s$ to $t$的 *path* , 所以此只附上 *flow network*
上原始圖的 *network flow*
vertex 裡為 *key* / *height*
edge 上為 *flow* / *capacity*
若$u \in V-\{s,t\}$ *overflowing*，則 $u$ 標示為紅色
在初始時，令 $h(s)=|V|，h(t)=0$ (註1)
且點 $s$ 會把 flow 分給所有 $v\ ,\ (s,v) \in E_f$
##
overfllowing vertex queue {***1*** ***2***}
對 ***1*** 進行操作，因沒有可 *push* 的點，所以須先 *relabel*
$\Rightarrow$ $h(1) = 1$
##
overfllowing vertex queue {***1*** ***2***}
將 ***1*** *push* ***3***，*push* 的值為 $12$
此時 ***3*** 也 *overflowing*，但 $e(1)=4$ 且已經沒有點可以 *push* 了，因此需要 *relabel*
(此 *push* 為 *saturating push*)
$\Rightarrow$ $h(1) = 7$
此為上述操作完之圖
##
overfllowing vertex queue {***1*** ***2*** ***3***}
繼續對 ***1*** 操作，將 ***1*** *push* ***s***，*push* 的值為 $4$
此時 $e(1) = 0$，可以從 queue 裡 pop 出來
##
overfllowing vertex queue {***2*** ***3***}
將 ***2*** *relabel* 後 $\Rightarrow$ $h(2) = 1$
再將 ***2*** *push* ***4***，*push* 的值為 $13$ , ***2*** 從 queue pop 出來
##
overfllowing vertex queue {***3*** ***4***}
將 ***3*** *relabel* 後 $\Rightarrow$ $h(3) = 1$
再將 ***3*** *push* $t$，*push* 的值為 $12$ ， ***3*** 從 queue pop 出來
##
overfllowing vertex queue {***4***}
這裡將 ***4*** *relabel* 了兩次
前後分別 *push* 給 $t$ , ***3*** , ***2***
##
overfllowing vertex queue {***2*** ***3***}
將 ***3*** *push* $t$，*push* 的值為 $7$
將 ***2*** *relabel*，再 *push* $s$，*push* 的值為 $2$
## 引理證明
為了求出 *push-relabel* 的時間複雜度 需要先知道以下幾個 lemma
##
### lemma1:
若 $(u,v) \in E_f$
則 $h(u) \le h(v) + 1$
### proof:
此證明用了數學歸納法
當演算法一開始時，$h(s)=|V| \ ,\ h(v)=0\ ,\ v \in V - \{s\}$
且不存在點 $(s,v) \in E_f$
$\Rightarrow$ 成立
假設現階段成立，則分別執行
1. push
若$u$ *push* 給 $v$，則 $h(u)$ = $h(v)+1$
此時 $(v,u) \in E_f$ , 而 $h(v) = h(u)-1 \le h(u)+1$
$\Rightarrow$ 成立
2. relabel
假設要對 $u$ relabel
且若現階段成立，則對於$v \in V\ ,\ h(v) < h(u)$ 之 $(u,v)$ 皆不存在
$h'(u)$ 為 relabel 後的高度
對於 $(w,u) \in E_f \ ,\ h(w) \le h(u)+1 < h'(u)+1$
$\Rightarrow$ $h(w) < h'(u)+1$
對於 $(u,v) \in E_f \ , \ h(v) \ge min(h(v)) = h'(u) - 1$
$\Rightarrow$ $h'(u) \le h'(v)+1$
$\Rightarrow$ 成立
原本成立 , 則下階段也成立
固可確保 $(u,v) \in E_f$ 則 $h(u) \le h(v) + 1$
##
### lemma2:
對於任何一個 *overflowing* 的點 $u$，在 *residual network* 必存在一條 path from $u$ to $s$
### proof:
一個 overflowing 的點 $x$
令 $U = \{v : G_f$ 存在 path from x to v$\}$
$\ \ \ \ \overline U= \{v : G_f$ 不存在 path from x to v$\}$
$\displaystyle\sum_{u\in U}e(u)$
$\ \ \ \ \ \ \ = \displaystyle\sum_{u\in U}(\displaystyle\sum_{v\in V}f(v,u)-\displaystyle\sum_{v\in V}f(u,v))$
$\ \ \ \ \ \ \ = \displaystyle\sum_{u\in U}
((\displaystyle\sum_{v\in U}f(v,u)+\displaystyle\sum_{v\in\bar U}f(v,u))-
(\displaystyle\sum_{v\in U}f(u,v)+\displaystyle\sum_{v\in \bar U}f(u,v)))$
$\ \ \ \ \ \ \ = \displaystyle\sum_{u\in U}\displaystyle\sum_{v\in \bar U}f(v,u)-
\displaystyle\sum_{u\in U}\displaystyle\sum_{v\in \bar U}f(u,v)$
假設 $s \not\in U$ , 也就是 $x$ 沒有 *path* 到 $s$ (最後再證出矛盾，即可得知 $s \in U$)
$x \in U$ (graph的定義)
$e(x) > 0$ $\Rightarrow$ $\displaystyle\sum_{u\in U}e(u) > 0$
$\Rightarrow$ $\displaystyle\sum_{u\in U}\displaystyle\sum_{v\in \bar U}f(v,u)-
\displaystyle\sum_{u\in U}\displaystyle\sum_{v\in \bar U}f(u,v) > 0$
因為 $\displaystyle\sum_{u\in U}\displaystyle\sum_{v\in \bar U}f(u,v) \ge 0$
$\Rightarrow$ $\displaystyle\sum_{u\in U}\displaystyle\sum_{v\in \bar U}f(v,u) > 0$
$\Rightarrow$ 存在$f(v,u) > 0$
若 $f(v,u) > 0$ 則 $(u,v) \in E_f$
根據 $u \in U$ 的定義 , 存在 path from $x$ to $u$
又因 $(u,v) \in E_f$ , 固 $v \in U$
$\Rightarrow$ 與 $v \in \bar U$ 矛盾
### 結論
不論 $x$ 為何點 , $s$ 必 $\in U$
如此 $\displaystyle\sum_{u\in U}e(u)$ 才會 $\le$ 0 , 才不會矛盾
##
### lemma3:
對於任何一點 $u \in V-\{s,t\}$ , 則 $h(u)$ 的最大值為 $2|V|-2$
### proof:
當任意一點 $u$ 要增加高度時 , 須透過 *relabel* , 且此時 $u$ 為 *overflowing*
根據 **lemma2** , $G_f$ 必有 *path* from $u$ to $s$
假設 path 為 $p : (u , v_0, v_1, v_2, ..., v_k, s)$
根據 **lemma1** 可得知 , $h(x) - h(v_0) = h(v_0) - h(v_1)=\ ...\ = h(v_k) - h(s) = 1$
又 $h(s) = v$
$\Rightarrow$ $h(u)$ 的最大值為 $h(s) + |V|-2 = 2|V|-2$
##
### lemma4:
在 *push-relabel* 裡面 , *relabel* 的次數 < $2|V|^2$
### proof:
能 *relabel* 的有 $|V|-2$ 個
每次 *relabel* 的高度至少增加 1 ， 又高度最高為 $2|V|-2$
故整個演算法 *relabel* 的次數 < $(|V|-2) * (2|V|-2)$ < $2|V|^2$
##
### lemma5:
在 *push-relabel* 裡面 , *saturating push* 的次數 < $2|V||E|$
### proof:
設有兩點 $u$,$v$ , 且之間存在 edge
若 $u$ *saturating push* 給 $v$ , *push* 後 $(u,v) \not\in E_f$
若要再對 $(u,v)$ 做 *saturating push* , 則u 的高度須比原本的高度增加至少2
且$v$可能也會 *saturating push* 給$u$ , 又最大高度為 $2|V|-2$,
因此任兩個之間存在 edge 的點 , *nonsaturating push* 的數最大為 $2|V|-2$
(由高度 $1$ *push* 高度 $0$ 到 高度 $2|V|-2$ *push* 高度 $2|V|-3$)
所以 *saturating push* 的總數 < $(2|V|-2)(|E|)$ < $2|V||E|$
## 時間複雜度證明
定義 *potential function* $\Phi = \sum_{v:e(v)>0}h(v)$
最初 $\Phi = 0$ , 演算法結束後 , 只有 $e(t) > 0$ , 但$h(t) = 0$ , 故 $\Phi = 0$
分別算出不同狀況下，對 $\Phi$ 的影響
但是，要計算的時間複雜度為最大時間複雜度，也就是最壞狀況
因此會讓 $\Phi$ 盡可能的大 (此句話重要)
##
1. relabel
對 $u$ 進行 *relabel* , 增加的高度最大為 $2|V|-2$
故 *relabel* 後 $\Phi$ 最大加 $2|V|-2$
2. nonsaturating push
對 $u$ 進行 *nonsaturating push* 後 , $e(u) = 0$ , $\Phi$ -= $h(u)$
並且 *push* 給 $v$ 點 , $v$ 點原本為 *overflowing* 或 *nonoverflowing*
若原本為 *nonoverflowing* 則$\Phi$ += $h(v)$
又 $h(u) = h(v) + 1$
故 *nonsaturating push* 後 $\Phi$ 至少減少 $1$ (也可能是減少 $h(u)$ , 但取最壞狀況)
3. saturating push
對 $u$ 進行 *saturating push* 給 $v$
$e(u)$ 不一定等於 $0$ , 而$v$可能由 *non-overflowing* 變成 *overflowing*
故最壞狀況下 , $e(u)$ += $h(v)$ , $\Phi$ 最大增加 $|V|-3$
##
由上可知，因演算法結束後$\Phi = 0$，*nonsaturating push* 至少能減少 $\Phi$ 1
故 *nonsaturating push* 的最大次數小於
$(2|V|^2)(|V|) + (2|V||E|)(2|V|)$ = $O(V^2E)$
最後統整各個操作的時間複雜度 :
nonsaturating push : $O(V^2E)$
saturating push : $O(VE)$
relabel : $O(V^2)$
若可以用 $O(1)$ 的時間找出 *overflowing* 的 $u$ 點即要對哪個點 *push*
則 *push-relabel* 的時間複雜度即為 $O(V^2E)$
## code
```cpp=
#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
#include <time.h>
using namespace std;
struct node{
int val;
node *next;
node(int x, node* r) {
val = x, next = r;
}
};
class solution {
public:
vector<vector<int>> rcf; //residual capacity graph
vector<node*> floor;
vector<int> h, exf; //excess flow
queue<int> que;
int n;
vector<vector<int>> *edgs;
//--- 給定不改變的元素
solution(int tn, vector<vector<int>> *tedgs) {
n = tn, edgs = tedgs;
}
void initial(int s, int t) {
h = vector<int> (n, 1);
exf = vector<int> (n, 0);
rcf = vector<vector<int>> (n, vector<int>(n,0));
floor = vector<node*> (n<<2-1, nullptr); //課本說是-1 但其實是-2 但因為我的最底是1 所以是檢1
for(vector<int> &v : *edgs)
rcf[v[0]][v[1]] = v[2];
for(int ver=0; ver<n; ver++) { //將source全部傳出去
if(rcf[s][ver] > 0) {
exf[s] -= rcf[s][ver];
exf[ver] = rcf[s][ver];
if(ver != t)
que.emplace(ver);
swap(rcf[s][ver], rcf[ver][s]);
}
}
h[s] = n+1;
floor[n+1] = new node(s, nullptr);
for(int i=0; i<s; i++) {
node *head = new node(i, floor[1]);
floor[1] = head;
}
for(int i=s+1; i<n; i++) {
node *head = new node(i, floor[1]);
floor[1] = head;
}
}
int get_max_flow(int s, int t) {
initial(s,t);
while(que.size()) //if still has the excess flow ver
{
int u = que.front();
while(1) {
int down_h = h[u] - 1;
for(node *r=floor[down_h]; r && exf[u]>0; r=r->next) {
if(rcf[u][r->val] > 0)
push(u, r->val, t);
}
if(exf[u] > 0)
relabel(u);
else
break;
}
que.pop();
}
return exf[t];
}
void relabel(int u) {
int newh = INT32_MAX;
for(int i=0; i<n; i++)
if(rcf[u][i])
newh = min(newh, h[i]);
deleteroom(u);
h[u] = newh+1;
node *head = new node(u, floor[h[u]]);
floor[h[u]] = head;
}
void push(int cur, int nex, int t) {
int flow = min(exf[cur], rcf[cur][nex]);
exf[cur] -= flow;
exf[nex] += flow;
if(exf[nex] == flow && nex != t)
que.emplace(nex);
rcf[cur][nex] -= flow;
rcf[nex][cur] += flow;
}
void deleteroom(int key) {
node *r = floor[h[key]];
if(r->val == key)
floor[h[key]] = r->next;
else {
while(r->next->val != key)
r = r->next;
r->next = r->next->next;
}
}
};
int main(void) {
int n, m;
cin >> n >> m; //vertexs and edges num
int u,v,cap,s,t;
vector<vector<int>> edgs(m);
for(int i=0; i<m; i++) {
cin >> u >> v >> cap;
edgs[i] = vector<int>{u,v,cap};
}
s = 0, t=n-1;
double start = clock();
solution S = solution(n,&edgs);
cout << "the maximun flow is : " << S.get_max_flow(s,t) << '\n';
double end = clock();
cout << end - start;
return 0;
}
```
本篇還會再做一些修改 , 程式的部分也會修一下 (8/6)
## 註
### 註1 :
Sign in with Wallet
Connect another wallet