二部グラフの最大マッチングの発見問題 - SQLによる解法
本文は後で書こう.
とりあえず使えそうなSQL文だけ載せておく.次に示すSQL文は,二部グラフについて,最大マッチングを発見する.これをそのまま実行すると,次のに対して最大マッチングを発見する.
WITH edges(source, sink) AS ( VALUES (1, 6), (1, 7), (2, 9), (3, 6), (4, 8), (4, 9), (5, 10) ) SELECT * FROM ( WITH RECURSIVE aug(phase, id, source, sink) AS ( SELECT 0, ROW_NUMBER() OVER(), * FROM ( SELECT source, sink FROM edges UNION SELECT -1, source FROM edges UNION SELECT sink, -2 FROM edges ) AS init UNION SELECT phase + 1, id, source, sink FROM ( WITH aug_cpy(phase, id, source, sink) AS ( SELECT * FROM aug ), flip(route) AS ( SELECT * FROM ( WITH RECURSIVE search(start, goal, route) AS ( VALUES(-1, -1, ARRAY[]::BIGINT[]) UNION SELECT start, sink, route || id FROM aug_cpy, search WHERE goal = source AND id <> ALL(route) ) SELECT route FROM search WHERE start = -1 AND goal = -2 LIMIT 1 ) AS flip_obj ) SELECT phase, id, CASE WHEN id = ANY(route) THEN sink ELSE source END, CASE WHEN id = ANY(route) THEN source ELSE sink END FROM aug_cpy, flip ) AS next_phase ) SELECT sink AS a, source AS b FROM aug WHERE phase = (SELECT MAX(phase) FROM aug) INTERSECT SELECT source, sink FROM edges ) AS result ORDER BY a ;
このSQL文を実行すると,次の結果を得る.
a | b ----+---- 1 | 7 2 | 9 3 | 6 4 | 8 5 | 10 (5 rows)
この実行結果からグラフの辺の部分集合
を得る. より, は明らかにグラフの最大マッチングである.
このSQL文はWITH句にVALUES句を含むので今のところPostgreSQLでしか動かない.PostgreSQL以外のRDBMSを用いる場合,VALUES句はSELECT文とUNION演算子によって置き換えられよう.また,MySQLはWITH句による一時表の作成をサポートしていない.