一般最大マッチング / 一般最大重み付きマッチングの実装

一般最大マッチング $O(n^3)$ と一般最大重み付きマッチング $O(n^2m)$, $O(n^3)$ の C++ での実装例です。一般最大マッチングについては若干アルゴリズムを変更しているため、$\tilde{O}(n^3)$ になっているかもしれません。


アルゴリズムの原理と詳細については省略します)

一般最大マッチング in $O(n^3)$

以下の実装は An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs (pdf) による実装を少し変更したものです。具体的には、

  • L5 での更新を DisjointSet (UnionFind) の find のような形で遅延させる。
  • augmenting path が見つからなかった場合は E7 の処理を飛ばす。

の 2 箇所を変更しています。これらの変更を行うと、疎グラフや最大マッチングを持たないグラフで高速に動作するようになります。


縮約の簡単なイメージ

f:id:Min_25:20161124214002p:plain

縮約前の inner vertex に相当する $v_2$, $v_5$, $v_7$ から join である $u_1$ に向けて augmenting path が伸びる場合、それらは必ず $h$ を通過することになります。なので、それらの頂点にたどり着いた際には、$h$ から両方向に向けて augmenting path を構築すればよいというのが、このラベリング法の面白いところです。

入力に対する制約
  • 各頂点は $1$-indexed で指定する必要があります。
  • 自己ループ・多重辺が存在しても動作します。

一般最大重み付きマッチング in $O(n^2m)$

以下の $O(n^2m)$, $O(n^3)$ の実装は、Guido Schäfer の Master's thesis p.33, Algorithm 1.6.3 の擬似コードを元にしたものです。augmenting path 関連の処理を平易にするため、Gabow の一般最大マッチングにおけるラベリング法を少し改変して用いています。


ラベリングの大体の雰囲気

f:id:Min_25:20161125165700p:plain

ラベリング法の変更点は

  • outer blossom の base のラベルは、その(擬似頂点での)親 と その親の親 との間の枝に設定する。
  • blossom のラベリングは、その base に対して augmenting path が作れるように、再帰的に行う。

の 2 箇所です。これで rematch を 1 回呼ぶだけで augmenting path の構築ができます。

このラベリング法は、短い再帰関数で書け(上の中では label_blossom)、inner blossom を expand した際のラベル変更も楽です。

一般最大重み付きマッチング in $O(n^3)$

$O(n^2 m)$ から $O(n^3)$ に改善することは、$O(n^2m)$ の実装に比べると比較的楽です。先に挙げた Master's thesis の pp.37-38 や An O(EV log V) Algorithm for Finding a Maximal Weighted Matching in General Graphs (pdf) の pp.126-127 で説明されている処理を実装すると計算量を改善できます。


入力に対する制約
  • 各頂点は $1$-indexed で指定する必要があります。
  • 各辺の重み $w$ は非負整数かつ、inf / 2 未満($< 2^{29}$, $< 2^{61}$ など)でなくてはなりません(内部的に 2 倍されるため)。
  • 自己ループ・多重辺が存在しても動作します。

感想

  • Gabow の一般最大マッチングはとても速い。
  • $O(n^2m)$ の一般最大重み付きマッチングについては、ボトルネックになる部分は $\delta_2$, $\delta_3$ の計算のみなので、うまい人が書けば 200 行程度で済むかも ?

追記 [2017-08-12]