Ford-Fulkerson法(最大フローを求める)をPythonで実装してみた

最大フローを求めるFord-Fulkerson法を実装したので忘れないうちに詳細を置いておく感じ
AtCoderの類題の他の方のコード読んで学んだことを自分なりにわかりやすいようにまとめた
解説記事とか探すとだいたいC++とかだから，こういう時にいろんな言語の他人のコードたくさん読めるAtCoderさんマジ感謝やで
証明とかはググってください()

最大フロー#とは

この辺が分かりやすかったです(ぶんなげ)
グラフネットワーク〜フロー&カット〜
重み付きの有向グラフが与えられて，それを辺の容量として始点から終点まで最大いくら流せるか
貪欲ではできないのでFord-Fulkersonというものを使う
参考問題
AOJ(まんまverify用)最大流 | グラフ | Aizu Online Judge
AtCoder(良い感じに落とし込める)D - 浮気予防

実装

頂点数:N，辺数:E，始点:Start，終点:Goal
上の参考問題のAOJのやつ(始点->終点への最大フローを求める問題)で通すコードを考える

辺の持ち方

グラフ系の問題だいたいに言えるがdefaultdict(set)で持つとやりやすい
辺コストは別のN*N配列として持つ(他の例えばダイクストラとかならsetの中にtupleとかで一緒に持ってもよい(lines[a].add((b,c))みたいな感じで)が，今回はコストを更新する必要があるのでそれだとややめんどくさい)

lines = defaultdict(set)
cost = [[0]*N for i in range(N)]
for i in range(E):
    a,b,c = inpl()
    if c != 0:
        lines[a].add(b)
        cost[a][b] += c

この形で持っておくと例えばsからラインが存在する辺を全部調べる時

for t in lines[s]:
    #処理

みたいな感じでs->tにラインがあるものは全部列挙できるし，無ければ何も起こらずスルーされる
ちなみにif c != 0をつけないと今回のAOJの問題で入力にコスト0の辺があるので落ちます．例外処理はちゃんとしような

Ford_Fulkerson関数内

def Ford_Fulkerson(s):

で定義．sからフローを流し始める
なかなか長いので分割して

宣言部分

#BFS用のdeque
queue = deque()             
queue.append([s,INF])
#到達済み判定用
ed = [True]*N
ed[s] = False
#ルート
route = [0 for i in range(N)]   
route[s] = -1

幅優先探索(BFS)を行うので探索する点をdequeで持つ． queueの中身は探索する点とそこまでで流せる最大の流量(flow)を入れる． できるだけ流したいので最初はINF流しておく．
BFSするので到達済みに戻らないようにそれ用の配列
routeは始点部分を-1にしておく．詳細は後述

BFS部分

while queue:
    s,flow = queue.pop()
    for t in lines[s]:  #s->t
        if ed[t]: #未到達
            flow = min(cost[s][t],flow)  #flow = min(直前のflow,その辺のコスト)
            route[t] = s
            queue.append([t,flow])
            ed[t] = False
            if t == Goal: #ゴール到達
                ans += flow
                break
    else:
        continue #breakされなければWhile節の先頭に戻る
    break
else:
    return False

普通にBFSするようにqueueを回していく(while queueでqueueが空になるまで回してくれる．便利) flowは直前まで流れていたflowとその辺のコストの小さい方に更新する．
Goalに到達した時はそこまで流れてきたansにflowを加算する．またGoalに到達したらループを抜けたいがPythonではgoto文が無い(外部モジュールにはある) のでfor-elseとwhile-elseを使っていい感じに抜ける．Goalに到達しなかったら一番下のreturn Falseまで流れてFalseが返されて終了する．
参考文献：多重ループを一気に抜ける

また，routeについて
s->tという道を通る時にroute[t]=sと更新していくことで， この配列を使ってルートを逆に辿れる(sを木の根として伸ばしていくイメージ)

辺を更新する部分

Ford-Fulkerson法の肝はBFSでルート求めて通ったルートの辺を潰して，逆向き同コストの辺を張る． ここで上のqueueでまわした時に見た辺を全部更新していくと，Goalにたどり着いたルートで使ってる辺以外も更新してしまうので， 上手いことGoalにたどり着けたルートで使ってる辺だけを更新したい．
ここで先ほど書いたrouteという配列を用いる．先ほど述べたようにこの配列を辿っていけばルートを逆向きに辿れるのでこれを用いて更新していく．(根(始点)にたどり着くまで親を辿り続ける感じ)

#ラインの更新
t = Goal
s = route[t]
while s != -1:
    #s->tのコスト減少，ゼロになるなら辺を削除
    cost[s][t] -= flow
    if cost[s][t] == 0:
        lines[s].remove(t)

    #t->s(逆順)のコスト増加，元がゼロなら辺を作成
    if cost[t][s] == 0:
        lines[t].add(s)
    cost[t][s] += flow

    t = s
    s = route[t]
        
return True

こんな感じでGoalから逆順に辿っていく．
s->t向きの辺は使った辺なのでコストを減少させる． ここで減少分は最後までたどり着いたflowを使う． またその辺のコストがゼロになったらlinesのsetの中から削除しておく(最大でも辺のコスト分しか流れないのでマイナスになることはない)
t->s向きの辺は使った辺の逆向きでコストを増加させる．増加分は同様にflow． またコストを増加させる前に元々辺が無かったらlinesにaddして辺を追加する

実行部分

while True:
    if Ford_Fulkerson(Start):
        continue
    else:
        break
print(ans)

Ford_Fulkerson関数を始点から実行し，Falseが返ってくる(Goalに到達できなかった)まで繰り返すだけ

全体

長いので折り畳み

▶展開

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N,E = inpl()
Start = 0
Goal = N-1
ans = 0

lines = defaultdict(set)
cost = [[0]*N for i in range(N)]
for i in range(E):
    a,b,c = inpl()
    if c != 0:
        lines[a].add(b)
        cost[a][b] += c

def Ford_Fulkerson(s): #sからFord-Fulkerson
    global lines
    global cost
    global ans

    queue = deque()     #BFS用のdeque
    queue.append([s,INF])
    ed = [True]*N    #到達済み
    ed[s] = False
    route = [0 for i in range(N)]   #ルート
    route[s] = -1

    #BFS
    while queue:
        s,flow = queue.pop()
        for t in lines[s]:  #s->t
            if ed[t]:
                flow = min(cost[s][t],flow)  #flow = min(直前のflow,line容量)
                route[t] = s
                queue.append([t,flow])
                ed[t] = False
                if t == Goal: #ゴール到達
                    ans += flow
                    break
        else:
            continue
        break
    else:
        return False

    #ラインの更新
    t = Goal
    s = route[t]
    while s != -1:

        #s->tのコスト減少，ゼロになるなら辺を削除
        cost[s][t] -= flow
        if cost[s][t] == 0:
            lines[s].remove(t)

        #t->s(逆順)のコスト増加，元がゼロなら辺を作成
        if cost[t][s] == 0:
            lines[t].add(s)
        cost[t][s] += flow

        t = s
        s = route[t]
        
    return True

while True:
    if Ford_Fulkerson(Start):
        continue
    else:
        break

print(ans)

感想

FordさんとFulkersonさんが作ったからFord-Fulkerson法というらしいんですが，天才すぎでは…
こういうアルゴリズム系の天才的すぎる発想どっから出てくるのか