給我們一份無向、無權重的 connected graph，要找到他的邊連通度 (edge connectivity)，以及其 edge。
如以下圖，邊連通度為 2，可以在 (2-5) 以及 (4-7) 畫兩刀達成。
作業要求使用 Ford-Fulkerson + Edmonds-Karp 演算法來達成。
要求邊連通度，相當於求出這整張圖的最小最小割 (minimum-cut)，也就是求出這整張圖所有任兩個點間最小的 min-cut。但是根據作業提示(ex. 26.2-11)，O(n) max flow computations are sufficient for finding a min cut，也就是說，我們只要求出一個點到其他點之間最小的 min-cut 即可。
求 min-cut 可以利用最大流最小割原理取得，這裡作業直接要求使用 Ford-Fulkerson + Edmonds-Karp 演算法。
使用該演算法得到 maximum-flow 之後，判斷該 max-flow 是否為最小，如果是，那麼其 min-cut 也會為最小，把 min-cut 求出之後儲存起來，等待下一個更小的出現。
最後印出儲存的 min-cut 數及其分別連接的點，完成！
由於 Ford Fulkerson + Edmonds-Karp 演算法是設計給有向圖的，而且會有「反向流量」的情形發生，因此，我們先把無向無權圖的每個 edge 拆成 正反 兩個方向，並且每個管子賦予他一個最大流量 1
進入演算法，我們鎖定輸入的第一個點為起點 source，開始找與其他點的 max-flow
開始 Ford Fulkerson / Edmonds-Karp，踏上尋找 max-flow 的旅程。
第一步，尋找 Augmenting Path，這個 path 有以下幾個規則
- 從 source 走到 sink
- 經過的管子不能是滿的 (residualPath: flow < capacity 才能通過)
- 不能重複走同樣的管子
這裡我們採用 BFS 來取得此路徑，也就是 Edmonds-Karp 演算法。
第二步，尋找此路徑間最窄小的管徑(在這裡通常是 1)，並將這之間所有的管子按以下規則灌水
- 流經管子的 flow 會增加 1
- 流經管子的反向，flow 會減少 1，允許負數產生
- 紀錄總流量增加 1，等下會用到
重複上面的步驟直到找不到 Argumenting Path。
完成之後就可以直接得到 max-flow (就是前面紀錄的總流量)，並算出 min-cut 了。
當然，如果 max-flow 是我們目前求過的最小值，我們才需要去算 min-cut。如果不是的話，就直接進到下一個點。
min-cut 是由以下規則求出，遞迴圖中：
- 從 source 出發
- 經過的管子不能是滿的 (residualPath: flow < capacity 才能通過)
- 不能重複走同樣的管子
完成後，記錄經過的所有 Vertex 點 中
- 有被遞迴過
- 但其某條 edge 指向的 vertex 沒被遞迴過
的所有這種 edge，這個概念很像是海峽兩岸，你一路沿著陸地(管子沒滿)的路上到了海邊，發現所有的跨海大橋都堵住了(管子滿了)。總之，這些 edge 即為 min-cut，把他存下來吧！
這裡我們使用的是 DFS
到這裡，這個點的計算就結束了，可以進行下一個點的計算：重新開始算 max-flow，繼續努力。
或是，如果我們已經把所有點爬過了，到這裡我們就可以印出我們儲存的最小 max-flow 與 min-cut 了
int min_maxFlow = int.max
List<Edge> min_minCut
for(int i = 0; i < graph.vertex.count; i++)
if(i == 0)
continue;
while(true)
argumentingPath = FindArgumentingPath(graph.vertex[0], graph.vertex[i])
if(argumentingPath == null)
if(totalFlow < min_maxFlow)
min_maxFlow = totalFlow
min_minCut = FindMinCut(graph.vertex[0])
int flow = FindSmallestResidual(argumentingPath)
totalFlow += cfp; // Fm += Cf(p)
foreach Edge e in augmentingPath:
e.flow += flow;
e.flow.reverse -= flowFindArgumentingPath(source, sink)
從 source 到 sink 進行 BFS，其中只能經過 residualPath，取得遞迴順序陣列 parent[]
List<Edge> result
從 sink，沿著 parent 加進 result
return result FindSmallestResidual(augmentingPath)
int minFlow = int.max
foreach Edge e in augmentingPath:
if(minFlow > e.capacity)
minFlow = e.capacity
return minFlowFindMinCut(source)
從 source 進行 DFS，其中只能經過 residualPath，取得點是否被遞迴陣列 visited[]
List<Edge> result
foreach(Vertex v in graph)
foreach(Edge e in v.edges)
if(visted[v] && !visited[v.e.dest])
result.Add(e)
return result
當初在看作業要求時沒看到有限制要用什麼語言寫，我就拿 Unity 來硬幹啦
編輯器 繪圖 演算法 全部自己來
除了痛苦的理解演算法是要怎麼跑的過程外，製作過程其實還滿快樂的。
看來我果然不是製作演算法的料ww
Anyway, 如果之後有時間有閒，我可以試著把其他演算法這樣 visualize，這樣應該比較好理解 (還是我專題要做這個? hmmmmmmmm
打到這裡想起來還有加分題沒做....
-
Unit 10 Maximum Flow https://ncueeclass.ncu.edu.tw/media/doc/28212
-
Ford Fulkerson algorithm for Max Flow https://youtu.be/hmIrJCGPPG4
-
Find minimum s-t cut in a flow network https://www.geeksforgeeks.org/minimum-cut-in-a-directed-graph/
-
Algorithm - Ch5 網路流 與 最大流最小割定理 Network Flow and Maximum Flow Minimum Cut Theorem https://mropengate.blogspot.com/2015/01/algorithm-ch4-network-flow.html
-
Finding edge connectivity of a network by using Maximum Flow algorithm https://stackoverflow.com/questions/16384151/finding-edge-connectivity-of-a-network-by-using-maximum-flow-algorithm
-
Minimum Cuts in Near-Linear Time https://arxiv.org/abs/cs/9812007
-
Edge connectivity / Vertex connectivity https://cp-algorithms.com/graph/edge_vertex_connectivity.html
-
Finding the max flow of an undirected graph with Ford-Fulkerson https://math.stackexchange.com/questions/677743/finding-the-max-flow-of-an-undirected-graph-with-ford-fulkerson
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent