Flow Networks:Maximum Flow & Ford-Fulkerson Algorithm

Posted by Chiu CC on 3 20, 2016


先備知識與注意事項

考慮如下情境:

在某個污水處理廠的某一道程序裡,有一個「進水孔」,和一個「排水孔」,中間由許多「孔徑不一」的水管連接起來,因為水管的「孔徑大小」會影響到「每單位時間的流量」,因此要解決的問題,就是找到每單位時間可以排放「最大流量(flow)」的「排水方法」。

cc

圖一。

以圖一為例,進水孔為vertex(S),排水孔為vertex(T),中間要經過污水處理站vertex(A)與vertex(C)。
edge代表水管,edge之weight(以下將稱為capacity)表示水管的「孔徑」。

考慮兩種「排水方法」的flow

  1. 第一種「分配水流」的方法,每單位時間總流量為\(20\)
    1. \(Path:S-A-T\)上每單位時間流了\(5\)單位的水;
    2. \(Path:S-A-C-T\)上每單位時間流了\(10\)單位的水(問題出在這,占去了edge(C,T)的容量);
    3. \(Path:S-C-T\)上,因為edge(C,T)上只剩下「\(5\)單位的容量」,因此每單位時間流了\(5\)單位的水;
  2. 第二種「分配水流」的方法,每單位時間總流量為\(25\)
    1. \(Path:S-A-T\)上每單位時間流了\(10\)單位的水;
    2. \(Path:S-A-C-T\)上每單位時間流了\(5\)單位的水;
    3. \(Path:S-C-T\)上,因為edge(C,T)上剛好還有「\(10\)單位的容量」,因此每單位時間流了\(10\)單位的水;

從以上兩種「排水方式」可以看得出來,解決問題的精神,就是如何有效利用水管的「孔徑容量」,讓最多的水可以從「進水孔」流到「排水孔」。

這就是在Flow Networks上找到Maximum Flow(最大流量)的問題。

以下將介紹Ford-Fulkerson Algorithm(若使用BFS搜尋路徑,又稱為Edmonds-Karp Algorithm)來回應此問題。


目錄


Flow Networks基本性質

Flow Networks是一個weighted,directed graph,其edge(X,Y)具有非負的capacity\(c(X,Y)\geq 0\),如圖二(a)。
(此處以capacity取代weightcapacity就是「水管孔徑」。)

  • 若不存在edge(X,Y),則定義\(c(X,Y)=0\)
  • 特別區分兩個vertex:
    • source:表示Flow Networks的「流量源頭」,以s表示;
    • sink:表示Flow Networks的「流量終點」,也稱為termination,以t表示。

cc

圖二(a)。

而水管裡的「水流」,flow,必須滿足以下條件,見圖二(b):

  1. Capacity constraint:從vertex(X)流向vertex(Y)的flow,不能比edge(X,Y)的capacity還大,\(f(X,Y)\leq c(X,Y)\)
    • 若每單位時間內,水管孔徑只能容納\(5\)單位,那flow最多就是\(5\)單位。
    • 以圖二(b)為例,在\(Path:S-A-C-D-T\)上的edge之capacity皆大於\(6\),因此在此路徑上流入\(6\)單位的flow是可行的。
  2. Skew symmetry:若定義「從vertex(X)指向vertex(Y)」之edge(X,Y)上,有\(5\)單位的flow\(f(X,Y)=5\),這就等價於,從vertex(Y)到vertex(X)之edge(Y,X)上,有\(-5\)單位的flow\(f(Y,X)=-5\)
    • 與「電子流(負電荷)」與「電流(正電荷)」之概念雷同,從「左到右的電流」與「從右到左的電子流」具有等價的物理意義。
  3. Flow conservation:對Graph中除了sourcesink以外的vertex(X)而言,所有「流進flow」之總和要等於所有「流出flow」的總和。
    • 也就是水流不會無故增加或無故減少,可視為一種能量守恆
    • 以圖二(b)為例,流入vertex(A)的flow\(6\),流出vertex(A)的flow也是\(6\),對vertex(C)、vertex(D)也是。

cc

圖二(b)。


Ford-Fulkerson Algorithm

Ford-Fulkerson Algorithm需要兩個輔助工具:

  1. Residual Networks(剩餘網路)
  2. Augmenting Paths(增廣路徑)

Residual Networks(剩餘網路)

Residual Networks的概念為,記錄Graph上之edge還有多少「剩餘的容量」可以讓flow流過。

以圖三(a)為例,若在\(Path:S-A-C-D-T\)上的所有edge都有\(6\)單位的flow流過,那麼這些edge(edge(S,A)、edge(A,C)、edge(C,D)、edge(D,T))的可用「剩餘capacity」,都應該要「減\(6\)」,例如,edge(S,A)只能「再容納\(9-6=3\)單位」的flow,edge(C,D)只能「再容納\(7-6=1\)單位」的flow

這些「剩餘capacity」就稱為residual capacity,以\(c_f\)表示。
若edge(X,Y)上有flow流過,\(f(X,Y)\),便將edge(X,Y)上的residual capacity定義為:

  • \(c_f(X,Y)=c(X,Y)-f(X,Y)\)
    • \(c(X,Y)\)為原來水管孔徑大小;
    • \(f(X,Y)\)表示目前水管已經有多少流量;
    • \(c_f(X,Y)\)表示水管還能再容納多少流量。

cc

圖三(a)。

Residual Networks也是一個directed graph,其中:

  • vertex集合與原directed graph完全相同;
  • edge之capacityresidual capacity取代,見圖三(a)右。

最關鍵的是,若「從vertex(A)指向vertex(C)」之edge(A,C)上,有\(6\)單位的flow流過,\(f(A,C)=6\),那麼在其Residual Networks上,會因應產生出一條「從vertex(C)指向vertex(A)」的edge(C,A),並具有\(6\)單位的residual capacity\(c_f(C,A)=6\)

  • 因為Skew symmetry\(f(C,A)=-f(A,C)\)
  • 再根據定義,\(c_f(C,A)=c(C,A)-f(C,A)=c(C,A)+f(A,C)=0+6=6\)

其物理意義呢?可以用「如果想要重新配置水流方向」來理解。

舉例來說,如果現在想經過\(Path:S-C-A-B-T\)流過\(2\)單位的flow,若觀察最一開始「還沒有flow經過」的directed graph(圖二(a)),其實並不存在從vertex(C)指向vertex(A)的edge(C,A),因此\(c(C,A)=0\),但是因為在圖三(a)已經有\(6\)單位的flow從vertex(A)流向vertex(C),使得現在可以從edge(A,C)上把\(2\)單位的flow「收回」,轉而分配到edge(A,B)上,而edge(A,C)上,就剩下\(4\)單位的flow,最後的結果如圖三(b)左所示。
在新增一條「增加flow的Path」後,Residual Networks更新如圖三(b)右。

cc

圖三(b)。

經過圖三(a)以及圖三(b)之後,流入sink(或稱termination)的flow累加到\(8\)單位。


Augmenting Paths(增廣路徑)

Residual Networks裡,所有能夠「從source走到termination」的路徑,也就是所有能夠「增加flow的path」,就稱為Augmenting Paths

cc

圖四(a)。

若以圖四(a)的Residual Networks為例,見圖四(b),Augmenting Paths有許多可能,例如:

  • \(Path:S-A-B-T\)\(3\)單位的flow
    • 因為在路徑上,所有edge中最小的capacity\(c(A,B)=3\),因此,flow可以容許從\(1\)單位到\(3\)單位。
  • \(Path:S-C-B-D-T\)\(2\)單位的flow
    • 同理,因為在路徑上,所有edge中最小的capacity\(c(B,D)=c(D,T)=2\),因此,flow可以容許\(1\)單位或\(2\)單位。
  • 以及其他。

cc

圖四(b)。

綜合以上可以確定,以圖四(c)為例:

  • 若要看當前流入termination的「總流量」,要在圖四(c)左,edge上標示「flow/capacity」的Graph上找。
    • 如圖四(c),流入vertex(T)的總flow\(8\)單位。
  • 若要找「還能夠增加多少流量」,也就是找Augmenting Paths,需要在Residual Networks上找,如圖四(c)右。
    • 若在\(Path:S-A-B-T\)\(Path:S-A-C-D-T\)\(Path:S-C-B-T\)流入「不超過該路徑上最低residual capacity」之flow,都是圖四(c)上的Augmenting Paths

cc

圖四(c)。


演算法概念

Ford-Fulkerson Algorithm(若使用BFS搜尋路徑,又稱為Edmonds-Karp Algorithm的方法如下:

  • Residual Networks上尋找Augmenting Paths
    • 若以BFS()尋找,便能確保每次找到的Augmenting Paths一定經過「最少的edge」。
    • 找到Augmenting Paths上的「最小residual capacity」加入總flow
    • 再以「最小residual capacity」更新Residual Networks上的edge之residual capacity
  • 重複上述步驟,直到再也沒有Augmenting Paths為止。

便能找到Maximum Flow


以圖二(a)之Flow Networks作為範例,尋找Maximum Flow之步驟如下:

  • 先以「flow為零」對residual networks進行初始化,如圖五(a)。
    觀察後發現,Gf就是Adjacency Matrix

cc

圖五(a)。

  • Gf上,以BFS()找到能夠從vertex(S)走到vertex(T),且「egde數最少」的路徑:\(Path:S-A-B-T\),見圖五(b)。
    • 根據「Graph上建立vertex的順序」,BFS()有可能找到都是\(3\)條edge的\(Path:S-A-B-T\)或是\(Path:S-C-D-T\)。這裡以前者為例。

cc

圖五(b)。

  • 觀察\(Path:S-A-B-T\)上之edge,發現edge(A,B)具有「最小residual capacity」,\(c_f(A,B)=3\),便更新「總flow新增\(3\)」。

  • Gf上,更新edge之residual capacity,見圖五(c):

    • \(c_f(S,A)=c(S,A)-f(S,A)=9-3=6\)
    • \(c_f(A,S)=c(A,S)-f(A,S)=0+3=3\)
    • \(c_f(A,B)=c(A,B)-f(A,B)=3-3=0\)
    • \(c_f(B,A)=c(B,A)-f(B,A)=0+3=3\)
    • \(c_f(B,T)=c(B,T)-f(B,T)=9-3=6\)
    • \(c_f(T,B)=c(T,B)-f(T,B)=0+3=3\)

cc

圖五(c)。

  • Gf上,以BFS()找到能夠從vertex(S)走到vertex(T),且「egde數最少」的路徑:\(Path:S-C-D-T\),見圖五(d)。

cc

圖五(d)。

  • 觀察\(Path:S-A-B-T\)上之edge,發現edge(C,D)具有「最小residual capacity」,\(c_f(C,D)=7\),便更新「總flow新增\(7\)」。

  • Gf上,更新edge之residual capacity,見圖五(e):

    • \(c_f(S,C)=c(S,C)-f(S,C)=9-7=2\)
    • \(c_f(C,S)=c(C,S)-f(C,S)=0+7=7\)
    • \(c_f(C,D)=c(C,D)-f(C,D)=7-7=0\)
    • \(c_f(D,C)=c(D,C)-f(D,C)=0+7=7\)
    • \(c_f(D,T)=c(D,T)-f(D,T)=8-7=1\)
    • \(c_f(T,D)=c(T,D)-f(T,D)=0+7=7\)

cc

圖五(e)。

接著繼續重複上述步驟:「更新Residual Networks,尋找Augmenting Paths」,見圖五(f)-(l)。

cc

圖五(f):找到\(Path:S-C-B-T\)

cc

圖五(g):更新Residual Networks。

cc

圖五(h):找到\(Path:S-A-C-B-T\)

cc

圖五(i):更新Residual Networks。

cc

圖五(j):找到\(Path:S-A-C-B-D-T\)

cc

圖五(k):更新Residual Networks。

cc

圖五(l):找到Maximum Flow。

當執行到圖五(l),在Residual Networks上再也找不到任何一條Augmenting Paths,便完成演算法。
Maximum Flow\(17\)


程式碼

程式碼包含幾個部分:

class Graph_FlowNetWorks

  • 使用AdjMatrix建立Graph,並利用AdjMatrix[X][Y]儲存edge(X,Y)的weight。
  • BFSfindExistingPath():利用Breadth-First Search尋找「從source走到termination」的路徑,而且是edge數最少的路徑。
  • FordFulkerson():進行Ford-Fulkerson Algorithm的主要函式,內容如前一小節所述。
  • MinCapacity():用來找到從BFSfindExistingPath()找到的路徑上,最小的residual capacity

以及main():建立如圖二(a)之AdjMatrix,並進行FordFulkerson()

// C++ code
#include <iostream>
#include <vector>
#include <queue>

class Graph_FlowNetWorks{
private:
    int num_vertex;
    std::vector<std::vector<int>> AdjMatrix;
public:
    Graph_FlowNetWorks():num_vertex(0){};
    Graph_FlowNetWorks(int n);
    void AddEdge(int from, int to, int capacity);

    void FordFulkerson(int source, int termination);
    bool BFSfindExistingPath(std::vector<std::vector<int>> graphResidual, 
                             int *predecessor, int source, int termination);
    int MinCapacity(std::vector<std::vector<int>> graphResidual, 
                    int *predecessor, int termination);

};
Graph_FlowNetWorks::Graph_FlowNetWorks(int n):num_vertex(n){
    // constructor
    AdjMatrix.resize(num_vertex);
    for (int i = 0; i < num_vertex; i++)
        AdjMatrix[i].resize(num_vertex);
}

bool Graph_FlowNetWorks::BFSfindExistingPath(std::vector<std::vector<int>> graph, 
                                             int *predecessor, int s, int t){
    int visited[num_vertex];

    for (int i = 0; i < num_vertex; i++){
        visited[i] = 0;     // 0 表示還沒有被找到
        predecessor[i] = -1;
    }

    std::queue<int> queue;
    // BFS 從 s 開始, 也可以規定s一律訂成vertex(0)
    queue.push(s);
    visited[s] = 1;
    while (!queue.empty()) {
        int exploring = queue.front();
        for (int j = 0; j < num_vertex; j++) {
            if (graph[exploring][j]!=0 && visited[j]==0) {
                queue.push(j);
                visited[j] = 1;
                predecessor[j] = exploring;
            }
        }
        queue.pop();
    }
    return (visited[t] == 1);   // 若t有被visited, 表示有path從s到t
                                // 也可以用 if (predecessor[t] != -1) 判斷
}

int Graph_FlowNetWorks::MinCapacity(std::vector<std::vector<int>> graph, 
                                    int *predecessor, int t){
    int min = 100;      // 確保min會更新, 假設graph上的capacity都小於100

    // 用predecessor[idx] 和 idx 表示一條edge
    // 找到在從s到t的path上, capacity最小的值, 存入min
    for (int idx = t; predecessor[idx] != -1; idx = predecessor[idx]){
        if (graph[predecessor[idx]][idx]!=0 && graph[predecessor[idx]][idx] < min) {
            min = graph[predecessor[idx]][idx];
        }
    }
    return min;
}

void Graph_FlowNetWorks::FordFulkerson(int source, int termination){

    // residual networks的初始狀態等於AdjMatrix, 見圖五(a)
    std::vector<std::vector<int>> graphResidual(AdjMatrix);    
    int maxflow = 0;                                           
    int predecessor[num_vertex];

    // BFS finds augmenting path,
    while (BFSfindExistingPath(graphResidual, predecessor, source, termination)) {
        int mincapacity = MinCapacity(graphResidual, predecessor, termination);
        maxflow = maxflow + mincapacity;
        for (int Y = termination; Y != source; Y = predecessor[Y]){
            // 更新 residual graph
            int X = predecessor[Y];
            graphResidual[X][Y] -= mincapacity;
            graphResidual[Y][X] += mincapacity;
        }
    }
    std::cout << "Possible Maximum Flow: " << maxflow << std::endl;
}
void Graph_FlowNetWorks::AddEdge(int from, int to, int capacity){

    AdjMatrix[from][to] = capacity;
}

int main(){
    Graph_FlowNetWorks g11(6);

    g11.AddEdge(0, 1, 9);g11.AddEdge(0, 3, 9);
    g11.AddEdge(1, 2, 3);g11.AddEdge(1, 3, 8);
    g11.AddEdge(2, 4, 2);g11.AddEdge(2, 5, 9);
    g11.AddEdge(3, 2, 7);g11.AddEdge(3, 4, 7);
    g11.AddEdge(4, 2, 4);g11.AddEdge(4, 5, 8);

    g11.FordFulkerson(0, 5);    // 指定source為vertex(0), termination為vertex(5)
    return 0;
}

output:

Possible Maximum Flow: 17

結果與圖五(k)相同。


利用BFS的優點

若在Residual Networks尋找Augmenting Paths的方法中,

  • 沒有用上BFS,稱為Ford-Fulkerson Algorithm,時間複雜度\(O(E|f|)\)
    • 其中,\(E\)為Graph上的edge數;
    • \(|f|\)為「最大流量」。
  • 有用上BFS,稱為Edmonds-Karp Algorithm,時間複雜度\(O(VE^2)\)

顯然,使用BFS的優勢在於時間複雜度。
嚴謹證明請參考David Mix Barrington:The Edmonds-Karp Heuristic
以下僅以一個簡單的例子,奉勸讀者使用BFS沒有害處。

以圖六(a)為例,若使用BFSMaximum Flow只需要「找兩次」Augmenting Paths\(Path:S-A-T\)以及\(Path:S-C-T\)

cc

圖六(a)。

但如果使用DFS()或其他方法,很有可能找到\(Path:S-A-C-T\),因為edge(A,C)的capacity只有\(1\)\(c(A,C)=1\),便限制了每單位時間的流量,見圖六(b)。

若不幸,在下一次挑選Augmenting Paths時,選到\(Path:S-C-A-T\),又只能流入\(1\)單位的flow
若每次都挑選到capacity只有\(1\)的edge,那麼,總共尋找Augmenting Paths的次數恰等於「總flow」的量,以圖六(b)為例,需要找\(20000\)Augmenting Paths,不算有效率的方法。

cc

圖六(b)。


以上便是Ford-Fulkerson Algorithm(說是Edmonds-Karp Algorithm也可以)的介紹。
關於Maximum Flow的應用,請參考Wikipedia:Maximum flow problem



參考資料:


Flow Networks系列文章

Flow Networks:Maximum Flow & Ford-Fulkerson Algorithm

回到目錄:

目錄:演算法與資料結構