scipyで最大流問題を解く
はじめに
scipyにはsparse.csgraph.maximum_flowが用意されていて最大流問題が解けるようになっています。
しかしこれといって日本語の解説記事が見当たらないので書いてみます。
scipy.sparse.csgraph.maximum_flowについて
scipy.sparse.csgraph.maximum_flow(csgraph, source, sink)
maximum_flowのパラメーターは3つです。
csgraph : グラフを示す疎行列(csr_matrix形式)
source : フローを流す元のindex
sink : フローの流す先のindex
返り値はMaximumFlowResultという形式です。後述しますがflow_valueとresidualの2つの値を持っています。
flow_value : sourceからsinkに流れたフローの量
residual : グラフの状態を示す疎行列(csr_matrix形式)
なお内部実装はEdmonds–Karp algorithmのようです。
実際に使ってみる
ここでは例として以下のグラフの0→3の最大流を考えます(括弧内は容量)。
0 →(3)→ 1 ↓ ↓ (1) (2) ↓ ↓ 2 →(2)→ 3
前準備
csr_matrixとmaximum_flowをimportします。
from scipy.sparse import csr_matrix from scipy.sparse.csgraph import maximum_flow
csr_matrixを用意する
グラフの情報を疎行列であるcsr_matrixに変換するには以下の方式があります。
多分後者の方が速いですがお好きな方をどうぞ。
なお容量は整数でないとValueErrorとなります。
① 密行列から直接変換する方式
graph = csr_matrix([
[0, 3, 1, 0],
[0, 0, 0, 2],
[0, 0, 0, 2],
[0, 0, 0, 0]
])
② フローの始点、終点、容量を表す配列をそれぞれ用意して変換する方式
(coo_matrix().tocsr()とした方が早い説もあります *1 )
src = [0, 0, 1, 2] # 始点 dst = [1, 2, 3, 3] # 終点 cap = [3, 1, 2, 2] # 容量 graph = csr_matrix((cap, (src, dst)), shape=(4, 4), dtype=int)
変換後のグラフは以下のようになります。
print(graph) # (0, 1) 3 # (0, 2) 1 # (1, 3) 2 # (2, 3) 2
フローを流す
maximum_flowを呼び出すだけです。
res = maximum_flow(graph, 0, 3)
最大容量
流せた量はflow_valueに格納されています。
print(res.flow_value) # 3
各辺に流れた量はresidualに格納されています。csr_matrix形式です。 なお逆の流れの場合は容量はマイナスで返されます。
print(type(res.residual)) # <class 'scipy.sparse.csr.csr_matrix'> print(res.residual) # (0, 1) 2 # (0, 2) 1 # (1, 0) -2 # (1, 3) 2 # (2, 0) -1 # (2, 3) 1 # (3, 1) -2 # (3, 2) -1
0→1→3の流れは容量2、0→2→3の流れは容量1となり合計3となるはずなのでとりあえず合っていそうです。
解いてみた
AtCoder Library Practice ContestのD - Maxflowを解いてみました。 atcoder.jp
最後に
速度的なメリットはあまり感じなかったのですが、簡潔にコードを書きたいときは使ってみても良いと思います。
