最大流問題について その3

2014-03-20最大流問題についてその3

前々回, 前回に引き続き, 最大流問題についてです.

Dinic 法でのボトルネックは, 各ステップで, dfs によりブロッキングフローを求める部分でした.

前回は, $O(nm)$ だったこの部分を $O(n^2)$ に落としたアルゴリズムを二つ紹介しました.

今回は, ここを $O(m \log n)$ , 従って, 全体では $O(mn \log n)$ にするアルゴリズムを紹介します.

前回の二つは, ある意味でまとめて流そうという感じのアルゴリズムでした.

今回のは, どちらかと言えば, Dinic 法の dfs を単純に速くする感じです.

Link/Cut Tree

突然ですが, Link/Cut Tree と呼ばれるデータ構造があります.

Link/Cut Tree は, 有向森(根付き木がいくつかあるもの) に関して, 色々なクエリを処理させられる, 割と強力なデータ構造です.

まず, 森の形状を変えるための基本的なクエリとして次の 4 つが挙げられます.

$\mathrm{link}(u, v)$ : ある木の根 $u$ の親を $v$ にする.
$\mathrm{cut}(u)$ : 頂点 $u$ を根とする部分木を切り離す.
$\mathrm{find}(u)$ : 頂点 $u$ を含む木の根を探す.
$\mathrm{evert}(u)$ : $u$ を含む木に含まれる辺の向きを変え, $u$ が根になるようにする.

他に, 例えば次のようなクエリを処理出来ます.

$\mathrm{set}(u, x)$ : 頂点 $u$ に値 $x$ をセットする.
$\mathrm{getMinInPath}(u)$ : 頂点 $u$ から, $u$ を含む木の根までのパスのうち, セットされた値が最小のものを返す.
$\mathrm{addToPath}(u, x)$ : 頂点 $u$ から, $u$ を含む木の根までのパスに含まれる各頂点に対し, セットされた値に $x$ を足しこむ.
$\mathrm{size}(u)$ : 頂点 $u$ を根とする部分木のサイズを取得する.

これらのようなクエリを, (償却計算量の意味で)対数オーダーで処理出来るデータ構造です.

誤解を恐れずに言えば, 切れる Union-Find Tree で, 木構造っぽいクエリの他に, 頂点を端点とする path に Segment Tree と同じような操作をサポートさせられるような感じです.

Link/Cut Tree の実装について.

次の 3 つを読むとよいです.

自分が実装した時の印象は, 次のような感じでした.

基本的なクエリはそこまで難しくはない. ( $\mathrm{evert}$ はちょっと面倒かも.)
頂点, パスに含まれる頂点へのクエリもそこまで難しくはない.
(上では挙げなかった)辺に対するクエリは, 直接実装するのは難しい. (諦めた)
- 各辺の間に頂点を追加して, 頂点に対する操作に書き直すと楽.
木に対する操作は, パスに対する操作よりちょっと面倒くさい. (多分アーベル群程度あれば可能ではある)
- $u$ を頂点とする部分木のサイズを取得するとか.

Link/Cut Tree を用いた Dinic 法

参考文献1 の 26 ページ下部のあたりから読むのが手っ取り早いです.

Dinic 法の dfs の途中の状態を見てみましょう.

各頂点に対し, 今見ている辺を, $\mathrm{iter}$ なる変数に格納していましたが, これに対応する辺に注目します.

例えば, 次の図のようになっています.

$\mathrm{iter}$ に対応する辺だけ見ると, 次の図のように, ( $T$ に近い側を根として持つ, 内側向きな有向)森になっています.

dfs を進めるのあたって, 森の上では次のような操作が行われています.

$\mathrm{iter}(u)$ を進める <=> $u$ の親を入れ替える.
dfs を一段階深くする <=> 注目している頂点を, 今の頂点の親にする.
$S$ から $T$ へのパスが見つかる <=> $S$ を含む木の根が $T$ .
見つかったパスに流れるフロー量 <=> $S$ から根に向けたパスのうち, 容量が最も少ないヤツ.
見つかったパスにフローを流す <=> $S$ から根に向けたパスにフローを流す.

ちょっと考えると, 次の操作をサポートする Link/Cut Tree を用意すれば, 対応する操作を Link/Cut Tree 上で実現出来る事が解ります. (容量は, 辺ではなく, 辺の下側の頂点に持たせます)

$\mathrm{link}(u, v)$ : ある木の根 $u$ の親を $v$ にする.
$\mathrm{cut}(u)$ : 頂点 $u$ を根とする部分木を切り離す.
$\mathrm{find}(u)$ : 頂点 $u$ を含む木の根を探す.
$\mathrm{set}(u, x)$ : 頂点 $u$ に値 $x$ をセットする.
$\mathrm{get}(u)$ : 頂点 $u$ にセットされた値を見る.
$\mathrm{getMinInPath}(u)$ : 頂点 $u$ から, $u$ を含む木の根までのパスに含まれる頂点のうち, セットされた値が最小のものを返す.
$\mathrm{addToPath}(u, x)$ : 頂点 $u$ から, $u$ を含む木の根までのパスに含まれる各頂点に対し, セットされた値に $x$ を足しこむ.

具体的には, 次のようにすればよいです.

であれば, パスが見つかっているので, 流すフェーズへ. そうでなければパスを探すフェーズへ.
- からへのパスを探すフェーズ:
  - $u = \mathrm{find}(S)$ とする.
  - $\mathrm{iter}(u)$ を進め, 使える辺 (容量正かつ $T$ 方面に行く辺) を探す.
  - 使える辺があった時:
    - $\mathrm{iter}(u)$ に対応する辺を $e=(u, v)$ とする.
    - $\mathrm{set}(u, e.\mathrm{cap})$ し, $\mathrm{link}(u, v)$ する.
    - 1. へ戻る.
  - 使える辺が無かった時: (現状のフローで, - がブロッキングされている.)
    - $u = S$ の時, ブロッキングフローになっているので, 今使われている辺 $e$ に対し, $\mathrm{unuse}(e)$ をして停止.
    - $u \neq S$ とする. $u$ を使えない頂点としてマークし, 以後使わない事にする.
    - 今使われている $e = (w, u)$ の形の辺に対し, $\mathrm{unuse}(e)$ を行う.
    - 1. へ戻る.
- からへのパスに流すフェーズ:
  - $f = \mathrm{get}(\mathrm{getMinInPath}(S))$ とする.
  - $\mathrm{addToPath}(S, -f)$ する.
  - である間, 次を繰り返す.
    - $u = \mathrm{getMinInPath}(S)$ とする.
    - $\mathrm{iter}(u)$ に対応する辺を $e$ に対し, $\mathrm{unuse}(e)$ する.
  - 1. へ戻る.

ここで, $e = (u, v)$ に対する $\mathrm{unuse}(e)$ は, 次のような操作です.

使われたフロー量 $f = e.\mathrm{cap} - \mathrm{get}(u)$ を, $e$ と $e$ の逆辺に適用する.
$\mathrm{cut}(u)$ をし, $\mathrm{set}(u, \infty)$ する.

また, 実装がややこしくなりますが, Dinic 法と同じく, bfs と dfs を逆から行うことが出来ます.

計算量

各辺につき, 高々一回ずつ $\mathrm{link}$ , $\mathrm{cut}$ する.

また, $\mathrm{getMinInPath}$ とか $\mathrm{addToPath}$ は, 高々 $\mathrm{cut}$ と同じくらいしかしない.

従って, ブロッキングフローを求めるのに, $O(m \log n)$ , 合計 $O(mn \log n)$ .

ソース

ここに置いておきました.

拡張のしやすさとか, 機能と拡張性を犠牲にして, 速さとかを重視しているので, Link/Cut Tree 部分がごちゃごちゃしています. (つってもそんなに速くないかもしれないですが.)

あと, L/C Tree は, Dinic だとこういうクエリしか来ないからとかいうので, 本来であれば必要なコードを削っていたりもするので, このままライブラリに転用はしないほうが良いです.

実測

例によって, どういうデータが欲しいかに従って, 自分で計測して下さい.

前回と同じデータで, Dinic 法と比較してみると, 次のようになっていました.

前と同様, グラフの構築にかかる時間は無視しています.

ケース	頂点数	辺数	Dinic (sec)	L/C Dinic (sec)	Wave (sec)
ランダムを80ケース(合計)	5000	1000000	1.9	1.8	5.3
ランダムを40ケース(合計)	50000	1000000	2.0	2.1	10.0
ランダムを13ケース(合計)	500000	1000000	1.9	2.3	10.0
密なランダムを5ケース(合計)	5000	約 $n(n-1)/2$	2.1	1.1	3.2
完全グラフを15ケース(合計)	2000	$n(n-1)$	2.0	1.9	3.6
ワーストケース1つ目	7000	13997	1.9	5.3	5.1
ワーストケース2つ目	628	33491	2.0	0.7	0.1

実測でも, 思ったほど遅くないです.

ワーストケースの一つ目は, dfs が $O(n)$ 回必要だけど, 各 dfs では割と自明なフローをひょいと流すだけなので, ブロッキングフローを探すアルゴリズムによる差は出にくく, 逆に定数倍が大きく出てくるので, そんな感じになっています.

結論

まぁ, 使うかどうかは置いておいて, 面白い.

次回予告

やる気と時間があれば, Push/Relabel 法について.

やりたい事が大体終わってきたので, 続かない確率割と高まっている.

参考文献

1. は no title から読めます.

Daniel D. Sleator, Robert Endre Tarjan (1983), A data structure for dynamic trees, Journal of Computer and System Sciences, vol.26, no.3, pp. 362-391

コメントを書く

れんしゅうちょう。

2014-03-20最大流問題について その3