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

一般最大マッチング $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 での更新を UnionFind の find のような形で遅延させる。
  • augmenting path が見つからなかった場合は E7 の処理を飛ばす。

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

入力に対する制約

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

Verify 用の問題

実行例

  • 一般 はランダムグラフ、二部 は $|V|/2$ ずつで分けたランダムグラフ。
  • 辺の生成は自己ループ・多重辺込みで一様ランダム。
  • 実行時間の単位は秒。

$V$ $E$ 一般グラフ 二部グラフ
$10^5$ $2 \cdot 10^5$ 0.159 0.105
$10^5$ $3 \cdot 10^5$ 0.124 0.072
$10^6$ $2 \cdot 10^6$ 9.93 13.8
$10^6$ $3 \cdot 10^6$ 6.25 6.41
$10^7$ $2 \cdot 10^7$ 237 938
$10^7$ $3 \cdot 10^7$ 112 397

早めの $O(nm)$ ぐらいで見積もっておくのが、ちょうどいいのかもしれないです。

更新履歴

  • 2017-09-11: rep の使用を削除。

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

以下の $O(n^2m)$, $O(n^3)$ の実装は、Guido Schäfer の Master's thesis p.33, Algorithm 1.6.3 の擬似コードを元にしたものです。

更新履歴

  • 2017-09-11: rep の使用を削除。

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

先に挙げた 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 倍されるため)。
  • 自己ループ・多重辺が存在しても動作します。

verify 用の問題

更新履歴

  • 2017-08-31: LinkedList の実装を少し変更。
  • 2017-09-11: rep の使用を削除。