nkhrlab~

140字超の記事

二部グラフの最大マッチングの発見問題 - SQLによる解法

本文は後で書こう.

とりあえず使えそうなSQL文だけ載せておく.次に示すSQL文は,二部グラフG = (A, B, E)について,最大マッチングを発見する.これをそのまま実行すると,次のA, B, Eに対して最大マッチングを発見する.
A = \{1, 2, 3, 4, 5\}
B = \{6, 7, 8, 9, 10\}
E = \{\{1, 6\}, \{1, 7\}, \{2, 9\}, \{3, 6\}, \{4, 8\}, \{4, 9\}, \{5, 10\}\}

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)

この実行結果からグラフGの辺の部分集合
M = \{\{1, 7\}, \{2, 9\}, \{3, 6\}, \{4, 8\}, \{5, 10\}\} \subseteq E
を得る.|M| = |A| = |B| = 5 より, Mは明らかにグラフGの最大マッチングである.

このSQL文はWITH句にVALUES句を含むので今のところPostgreSQLでしか動かない.PostgreSQL以外のRDBMSを用いる場合,VALUES句はSELECT文とUNION演算子によって置き換えられよう.また,MySQLはWITH句による一時表の作成をサポートしていない.