[ 読者の想定 ]

ネットワーク/最大フロー問題が分かっている
preflow-push (preflow push-relabel) アルゴリズムを知っている
preflow-push アルゴリズムを改良したい!

なおPython3.7で実装したプログラムをGitHubで公開していますので, ぜひ.

概要

preflow-push algorithm [1][2] はネットワーク$G=(V, E)$上の最大フローを求めるアルゴリズムです. 以下では始点(source)を$s$, 終点(sink, target)を$t$と書くことにします.

preflowとはフロー保存則を無視したフローのことでノードから出るフロー量 - ノードに入るフロー量(=: excess value(超過量) )が0よりも大きいことを許したものです. このアルゴリズムではまず始点sから流せるだけpreflowを流し 距離ラベルd を適切に管理しながら, 流しすぎた分を始点に返していくことで最終的にフロー保存則を満たすmaxフローを取得します.

超過量が正の点を active node(活動点) と呼び, active nodeがグラフからなくなるまであるactive nodeに対し, もしその点を始点とする admissible arc(可能辺) があれば push 操作を, そうでなければ relabel 操作を繰り返します. 擬似コードで書くとこんな感じ.

preprocess # set distance label and flow each arc (s, j) in E
while network contains active node:
	select an active node i
    if the network contains an admissible arc (i, j):
        push(i, j)
    else:
        relabel(i)

push操作, relabel操作, その他の用語については[3]もしくは[2]を参考にしてください. これをGeneric prelow-push algorithmと呼ぶことにします.

擬似コードを見てわかるように, このアルゴリズムは非常にシンプルなので次のような任意性を含みます[4]

活動点選択の任意性
- 一度選ばれたactive node $i$について, iがnon active nodeになるか, $i$から可能辺がなくなるまでiを選択し続ける
- active nodeをどの順番に選ぶか
流量の可能性
- push操作においてどれほどの流量を流すか
データ構造の選択の任意性
他の技術との併用の任意性

任意性があるということは改良の余地があるということ!!

この記事では, 計算量を削減する改良として FIFO Preflow-Push AlgorithmとHighest-Label Preflow-Push Algorithmを, 最悪計算量は変わらないheuristicsな改善手法として Global labeling, Gap-relabeling, Freeze operation[5]を紹介したいと思います.

計算量のまとめ

$n := |V|, m := |E|$

手法	計算量
Generic preflow-push algorithm	$O(n^2m)$
FIFO preflow-push algorithm	$O(n^3)$
Highest-label preflow-push algorithm	$O(n^2\sqrt{m})$
Excess scaling algorithm (今回紹介なし)	$O(nm+n^2logU)$

計算量改善

FIFO preflow-push algorithm

FIFO preflow-push algorithmは Generic preflow-push alogirthmに次のような工夫を行ったものです.

active nodeはqueueで管理する. 新たにactive nodeが生まれる or relabelされるたびにqueueの末尾に追加する
push/relabel対象のactive node $i$はqueueの先頭から取り出す
active node $i$がnon active または relabel されるまで $i$を選択し続ける

preprocess # set distance label and flow each arc (s, j) in E
LIST = queue({j: (s, j) in E})
while the network contains an active node:
	select an active node i
	if the network contains an admissible arc (i, j):
		push(i)
	else:
		relabel(i)

Highest preflow-push algorithm

Highest preflow-push algorithmは Generic preflow-push alogirthmに次のような工夫を行ったものです

距離ラベルが最大のactive nodeを push/relabel対象とする.
距離ラベルが取りうる値は$0 から 2n-1$までの整数値[2]なので, バケツソートの要領で最大active nodeを取り出すことができる.

preprocess # set distance label and flow each arc (s, j) in E
LIST(0) = {j: (s, j) in E}
hstar = 0 # hstar is the max label of active nodes
while LIST is not empty:
    while LIST(hstar) is empty:
        hstar = hstar - 1
	pop active node i from LIST(hstar)
    while excess value of i > 0 or admissible arc (i, j):
		push(i, j)
        if j not in LIST:
            add j to LIST(d(j))
    if excess value of i > 0:
        relabel(i)
        add i to LIST(d(i))
        if d(i) > hstar:
            hstar = d(i)

実験その1

このネットワークで実験. $s$を青色, $t$を緑色, active nodeを赤色, excess valueをその濃さ, non active nodeを水色で, アルゴリズム実行中のノードについている番号は距離ラベルを表しています. また, アルゴリズムの良さを, push/relabel operationの回数で測ることにします.

Genetic preflow-push algorithm

operation	回数
push	19回
relabel	20回

FIFO preflow-push algorithm

operation	回数
push	16回
relabel	14回

Highest preflow-push algorithm

operation	回数
push	16回
relabel	11回

FIFO, Highsetの方がGeneticよりも, より少ないpush/relabelの回数でmaxフローが求められていることがわかります。

Heuristics

次は, heuristicsの方法です. Geneticにそれぞれの手法を適用した場合の擬似コードを載せています.

Global labeling

preprocess 直後に, node $i$($s$以外)の距離ラベルを次のように設定する
- node i から終点までの最短枝数
- これは残余ネットワーク(residual netowrk)上での$t$からの幅優先探索(計算量($O(m)$)で見つけることができる.
気持ちとしては, 例えば$t$とつながるnodeはtへフローを流すために, relabelによって距離ラベルをいつかは最低終点までの最短ホップ数は増やすことになるので, それならば最初から増やしておこうというものです

preprocess # set distance label and flow each arc (s, j) in E
global_laveling # set distance from t label by BDS
while the network contains an active node:
    ...

Gap-relabeling

アルゴリズム中, 距離ラベルdがちょうど$g (0 < g < n)$ となる点が存在しないとき, $n > d(v) > g$ であるnode $v$のラベルを$n$に変更する

ギャップが生じた瞬間に, そのギャップ間を新しくフローが流れることはない

preprocess # set distance label and flow each arc (s, j) in E
while the network contains an active node:
	select an active node i
    if the network contains an admissible arc (i, j):
        push(i, j)
    else:
        relabel(i)
        if exists g (0 < g < n) such that there is not node i where d(i) = g:
            for node i where g < d(i) < n:
                relabel d(i) = n

Freeze operation

$d(v) \geq n$ であるようなnode $v$ を**Freeze(凍結)**し,これ以降activeとは考えず, push操作とrelabel操作は適用しない
アルゴリズム終了後に, 超過量が正の点から$s$に超過量分戻していく (計算量$O(nm)$で可能)
- super souceを用意し, 超過量が正の点へ, 容量が超過量であるような枝を張ると, 始点終点の任意の点で, 常に入ってくる枝の容量の和が, 出ていく枝の容量の和以下であるようなネットワーク上のmaxflow問題として変換できる. この場合, maxflow値はsuper souceから出る枝の容量の和であるので, あとは実際にフローを求めれば良い. 次のようなアルゴリズムを考えました
- frozen nodeがネットワークからなくなるまで以下を繰り返す.
  - sからの距離が最大のfrozen node uを選択する
  - frozen node uの超過量が0になるまで以下を繰り返す.
    - DFSによりuから深さ優先探索により残余ネットワーク上のパスを探索していく
    - $s$または他のfrozen nodeにたどり着いたら, その点に向かってパス上をmin(超過量, min(パス上の枝の残余ネットワーク容量))分のフローを流す
- 今回考えたアルゴリズムが最良かどうかは分かりません.

preprocess # set distance label and flow each arc (s, j) in E
while the network contains an active node:
	select an active node i
    if the network contains an admissible arc (i, j):
        push(i, j)
    else:
        relabel(i)
        if d(i) >= n:
            freeze node i and change i to non active
    
if the network contains a freeze node:
    select a frozen node u with the distance from s being largest
    while excess value of u > 0:
        find (u-v) path on the residual network with v is t or other frozen node by DFS
        delta = min(excess value of u, min(capacity of edge which the path has in the residual network))
        push delta flow u to v

実験その2

このネットワークで実験. Highest preflow-push algorithmにこれらを適用していきます. 凍結点を灰色で表しています.

Global labeling

operation	回数
push	16
relabel	8

Gap-relabeling

operation	回数
push	16
relabel	13

Freeze operation

operation	回数
push	14
relabel	11

これらのheuristicsは組み合わせることができます.

Global labeling & Gap-relabeling & Freeze operation

operation	回数
push	13
relabel	7

まとめ

Genetic preflow-push algorithmに改良を施すことで, アルゴリズム全体のpush/relabelの回数を減らすことができた. Global labeling と Gap-relabelingは実装が簡単で, 効果が大きい. (Freeze operationは実装が少し大変)

計算量の観点では, 今回紹介していない, Excess scaling algorithmが最小なので, 動的木と合わせて勉強したいです.

参考文献

[1] Goldberg, Andrew V., and Robert E. Tarjan. A new approach to the maximum-flow problem. Journal of the ACM (JACM)* 35.4 (1988): 921-940.
[2] R.K. Ahuja, T.L. Magnanti, and J.B. Orlin. Network Flows Theory, Algorithms, and Applications. (1993) Prentice-Hall.
[3]@a-lilas, 最大流問題をプリフロー・プッシュ (Push-Relabel) 法で解く
[4] 岩野和生, 最大流アルゴリズムの最近の発展とその背景-II, 情報処理 Vol. 31 No.1 (1990)
[5] J.Kleinberg, E. Tardos(著), 浅野孝夫, 浅野泰仁, 小野孝男, 平田富夫(翻訳) (2009) アルゴリズムデザイン, 共立出版.

今回作成したコード

Git Hub上で公開しています。

https://github.com/nariaki3551/max-flow