Поиск паросочетаний графов с помощью T-SQL. Часть 3

Перед вами третья статья из серии о задачах паросочетаний графов. В первой статье я рассказал о том, что такое паросочетание графов, и изложил сопутствующие концепции. Во второй статье были представлены решения для задачи нахождения наибольшего паросочетания; в завершение читателям была предложена задача нахождения паросочетания максимальной мощности.

Предположим, у вас есть набор X (например, соискатели рабочих мест), не пересекающийся с множеством Y (например, рабочие места), и двудольный граф G, соединяющий вершины двух наборов (пары «соискатель — рабочее место», где соискатель обладает достаточной квалификацией для выполнения работы). Паросочетание M в графе G представляет подмножество ребер в G, где никакие два ребра не совпадают (не имеют общей вершины). Наибольшее паросочетание представляет собой то, к которому нельзя добавить больше ребер в графе. Паросочетание максимальной мощности — это наибольшее паросочетание с максимально возможным числом ребер из графа. На рисунке 1 показаны примеры паросочетаний графов.

Рисунок 1. Примеры паросочетания в графе

В нашем примере «соискатели — рабочие места» нужно найти паросочетание максимальной мощности, чтобы максимально задействовать соискателей и заполнить рабочие места.

Тестовые данные

Чтобы продемонстрировать и испытать решение для паросочетания максимальной мощности, будут использованы те же тестовые данные, что и в предыдущих статьях. Воспользуйтесь программным кодом листинга 1, чтобы создать малый набор данных для проверки правильности решения.

Используйте программный код листинга 2, чтобы создать большой набор тестовых данных (~1000000 ребер) для тестирования производительности решения.

Если вы используете SQL Server 2016 или более новую версию, обязательно создайте пустой столбчатый индекс columnstore для оптимизации с оператором Window Aggregate пакетного режима:

CREATE NONCLUSTERED COLUMNSTORE
   INDEX idx_cs_dummy
ON dbo.G (x) WHERE x = 'yes' AND x = 'no';

Алгоритм поиска паросочетания максимальной мощности

В алгоритме поиска паросочетания максимальной мощности используется увеличивающийся путь (разновидность чередующегося пути). Напомню, что при паросочетании M в графе G чередующийся путь, или M-чередующийся путь в G, — это путь, состоящий из ребер в G, которые меняются от присутствующих в паросочетании к отсутствующим в паросочетании. Увеличивающийся путь — это чередующийся путь, который начинается и заканчивается на свободных вершинах. На рисунке 2 показаны типы путей.

Рисунок 2. Типы путей

Ниже приводится алгоритм поиска паросочетания максимальной мощности M в G.

• Начните с любого паросочетания M в G (пустого или непустого).
• Повторяйте шаги, пока верно следующее утверждение:

— задать M = M ⊕ P (симметрическая разность M и P), где P = M-чередующийся путь в G;

— если увеличивающийся путь не обнаружен, прервать.

Подробные сведения об этом алгоритме, а также его обоснование и оценку сложности можно найти в лекции по паросочетанию в двудольном графе (http://math.mit.edu/~goemans/18433 S07/matching-notes.pdf).

На рисунке 3 показано применение этого алгоритма с малым набором тестовых данных, начиная с пустого паросочетания.

Рисунок 3. Алгоритм поиска максимума паросочетаний

Обратите внимание, что мощность паросочетания увеличивается на единицу на каждом шаге. Это означает, что, если отправной точкой является паросочетание с мощностью n (0 для пустого паросочетания в качестве отправной точки) и мощность паросочетания максимальной мощности — m, алгоритм совершит m — n итераций увеличения.

В предыдущей статье были представлены различные решения для поиска наибольшего паросочетания. В большинстве представленных решений среднее время поиска каждого ребра в наибольшем паросочетании значительно меньше времени поиска увеличивающегося пути и применения приращения. Поэтому полезно начинать с наибольшего паросочетания в качестве отправной точки для поиска паросочетания максимальной мощности.

Решения для наибольшего паросочетания

Напомню, что в Решении 5 для поиска наибольшего паросочетания было создано паросочетание большей мощности, чем во всех других решениях. Поэтому воспользуемся этим решения для поиска наибольшего паросочетания, которое послужит отправной точкой для поиска паросочетания максимальной мощности.

Если это еще не сделано, сначала выполните следующий программный код для создания пустого индекса columnstore, чтобы обеспечить оптимизацию с использованием оператора Window Aggregate пакетного режима:

CREATE NONCLUSTERED COLUMNSTORE
   INDEX idx_cs_dummy
ON dbo.G (x) WHERE x = 'yes' AND x = 'no';

Затем выполните программный код листинга 3 для создания процедуры MaximalMatching, которая реализует Решение 5 из предыдущей статьи.

Процедура MaximalMatching заполняет таблицу M наибольшим паросочетанием в G.

Алгоритм поиска увеличивающегося пути

Для паросочетания M в двудольном графе G, которое соединяет вершины из набора X с вершинами из набора Y, в этом разделе описан алгоритм поиска M-увеличивающегося пути в G. Алгоритм создает остаточный направленный граф G’. Сформируйте остаточный граф следующим образом:

• добавьте исходную вершину s и создайте направленные ребра, указывающие из s ко всем свободным вершинам x (вершины x, не совпадающие ни с одной из вершин в M);
• добавьте целевую вершину t и создайте направленные ребра из всех свободных вершин y (вершины y, которые не принадлежат никаким ребрам в M), указывающие на t;
• для каждого ребра в M создайте направленное ребро в G’, указывающее из y в x;
• для каждого ребра в G, которое отсутствует в M, создайте направленное ребро в G’, указывающее из x в y.

Примените алгоритм поиска преимущественно в глубину (depth-first search, DFS) или поиска в ширину (breadth-first search, BFS), чтобы найти кратчайший путь между s и t. Этот путь, без первого и последнего ребер из s в t, является M-увеличивающимся путем в G. На рисунке 4 дано графическое представление этого алгоритма. Слева находится некоторое паросочетание M в графе G. В центре — остаточный граф G’, созданный из M и G на основе приведенных выше инструкций. Справа — выделенный кратчайший путь из s к t: s->D->3->B->1->A->2->t. После удаления первого и последнего ребра в пути вы получите D->3->B->1->A->2, что является M-увеличивающимся путем в G. Наша цель — вернуть увеличивающийся путь как подмножество вершин из G: {(D, 3), (B, 3), (B, 1), (A, 1), (A, 2)}.

Рисунок 4. Нахождение увеличивающегося пути

Реализация алгоритма поиска увеличивающегося пути

В нашем решении для паросочетания максимальной мощности применяется последовательность приращений, каждое из которых устанавливает M равной симметрической разности M и увеличивающегося пути в M. По этой причине удобно реализовать решение поиска увеличивающегося пути как многооператорной, определенной пользователем функции (с именем AugmentingPath), которая возвращает табличную переменную @P с набором ребер, формирующих путь. Функция реализует следующие действия.

• Пытается идентифицировать увеличивающийся путь размера 1 и записать его в @P. Это любое ребро в G со свободной x и свободной y. Если такой путь обнаружен, возврат.
• Если увеличивающегося пути размера 1 не существует, функция ищет все потенциальные начала для более длинных увеличивающихся путей (свободные вершины x из G, соединенные с соответствующими вершинами y) и записывает их в табличную переменную @X. Если ни одно не обнаружено, увеличивающегося пути не существует, возврат.
• Повторяет, пока увеличивающийся путь не обнаружен:

— Добавляет в табличную переменную @Y отдельные соответствующие вершины y из G, которые имеют родительскую вершину в @X из предыдущей итерации и которых еще нет в @Y. Использует MIN (x) для y в качестве родителя, поскольку в конечном итоге нам нужен только один увеличивающийся путь. В случае нескольких родительских x не имеет значения, из которого мы идем к y. Все обработанные «родители» находятся в @X, поэтому не приходится повторно посещать пути в последующих итерациях. Если таких вершин y не обнаружено, увеличивающийся путь не существует, возврат.

— Если существуют новые вершины y, функция ищет соответствующие вершины x в M. Они должны существовать и быть отдельными (поскольку соединенные вершины y с преды­дущего уровня сопоставлены).

— Добавьте к @P любое ребро со свободной y и x из текущего уровня в @X. Если такая вершина существует, мы обнаружили увеличивающийся путь.

• Если вы пришли к этому шагу, увеличивающийся путь должен существовать и его длина больше чем один сегмент. Сконструируйте путь из @P, @X и @Y.

Запустите программный код листинга 4, чтобы создать полную функцию AugmentingPath.

Обратите внимание, что в действительности это решение не строит остаточный граф G’, но воспринимает его как виртуальный. Опущена часть с источником s и приемником t; они полезны на концептуальном уровне. Решение начинается со свободными вершинами x и завершается со свободными вершинами y, а прерывается, если обнаружить увеличивающийся путь не удается.

Используйте следующий программный код для проверки функции (сначала с малым набором тестовых данных):

SELECT * FROM dbo.AugmentingPath ();

Если выполнить этот программный код с пустым M, то будет получен путь с одной вершиной. Вы можете вручную заполнить M любым начальным паросочетанием, а затем запустить функцию, чтобы убедиться в ее успешном выполнении.

Реализация алгоритма поиска паросочетания максимальной мощности

Как отмечалось выше, алгоритм поиска паросочетания максимальной мощности имеет следующий вид.

• Начать с любого паросочетания M в G (пустого или не пустого).
• Повторять, пока верно следующее условие:

— задать M = M ⊕ P (симметрическая разность M и P), где P = M-увеличивающийся путь в G;

— если увеличивающийся путь не обнаружен, прервать.

В нашем решении используется наибольшее паросочетание в качестве отправной точки после выполнения подготовленной ранее процедуры MaximalMatching.

Затем в цикле с условием, которое всегда истинно (например, WHILE 1 = 1), реализуются два шага.

1. Предложение MERGE, которое задает M значение симметрической разности M и результата функции AugmentingPath. Эта инструкция определяет M как цель, а функция AugmentingPath (с псевдонимом P) как источник. Предикат объединения — M.x = P.x AND M.y = P.y. Если обнаружено паросочетание, целевая строка удаляется; если паросочетание не обнаружено, исходная строка вставляется в цель.
2. Если число строк, на которые воздействует инструкция MERGE, равно 0, то операция завершена, поэтому происходит выход из цикла.

В листинге 5 приводится реализация этого решения с несколькими дополнительными строками программного кода для измерения времени выполнения каждой из двух основных частей: поиска наибольшего паросочетания и применения оставшихся приращений.

Этот программный код в основном прост, но может возникнуть вопрос относительно цели пустого оператора в действии UPDATE в предложении MERGE, поскольку на практике оно никогда не активируется:

WHEN MATCHED AND 0 = 1 THEN UPDATE
   SET x = 'Thanks, Paul White!', y = 1759

Без этого предложения в результате ошибки инструкция MERGE может привести к сбою из-за нарушения промежуточного повторяющегося ключа, если производится внутренняя обработка вставок перед удалениями. Решение Пола Уайта состоит в добавлении предложения с действием UPDATE. В результате оптимизатор выдает широкий (для каждого индекса) план обновления с разбиением, сортировкой и свертыванием, что исключает промежуточные повторяющиеся ключи. Более подробно об этом рассказано в его журнале (http://sqlblog.com/blogs/paul_white/archive/2012/12/10/merge-bug-with-filtered-indexes.aspx).

Запуск этого решения с малым набором тестовых данных приводит к выходным данным, показанным на экране 1.

Экран 1. Результат работы кода листинга 5 с малым набором тестовых данных

Запуск этого решения с большим набором тестовых данных приводит к выходным данным (сокращенно), как на экране 2.

Экран 2. Результат работы кода листинга 5 с большим набором тестовых данных

Как оказалось, процедура MaximalMatching обнаружила наибольшее паросочетание, которое также является паросочетанием максимальной мощности. Это идеальный случай, поэтому на первом проходе не удалось найти увеличивающийся путь, и цикл был прерван.

Итак, в этой серии статей мы рассмотрели задачи паросочетаний графов, начиная с изложения принципов и описания сопутствующих концепций, с последующим представлением решений для наибольшего паросочетания и, наконец, решения для паросочетания максимальной мощности. Я лишь поверхностно коснулся этого предмета. Существует множество связанных задач с дополнительными уровнями сложности, в том числе с учетом весов (например, приоритета) и т. д. Если вы хотите более подробно рассмотреть эту тему, обратите внимание на такие вопросы, как паросочетание графов (https://en.wikipedia.org/wiki/Matching_ (graph_theory)) и потоки в сетях (https://en.wikipedia.org/wiki/Flow_network). Я надеюсь, что по мере совершенствования функциональности графов в SQL продукт будет дополнен инструментарием, который сделает более эффективным решение подобных задач.

SET NOCOUNT ON;
USE tempdb;

-- Очистка
DROP TABLE IF EXISTS dbo.M, dbo.G, dbo.X, dbo.Y;
GO

-- Набор X, например Applicants
CREATE TABLE dbo.X
(
  x VARCHAR(10) NOT NULL CONSTRAINT PK_X PRIMARY KEY,
  moreonx VARCHAR(20) NOT NULL
);

INSERT INTO dbo.X(x, moreonx) VALUES
  ('A', 'Applicant A'),
  ('B', 'Applicant B'),
  ('C', 'Applicant C'),
  ('D', 'Applicant D');

-- Набор Y, например Jobs
CREATE TABLE dbo.Y
(
  y INT NOT NULL CONSTRAINT PK_Y PRIMARY KEY,
  moreony VARCHAR(20) NOT NULL
);

INSERT INTO dbo.Y(y, moreony) VALUES
  (1, 'Job 1'),
  (2, 'Job 2'),
  (3, 'Job 3'),
  (4, ‘Job 4’);

-- Граф G = (X, Y, E), например возможные соединения «соискатель-рабочее место»
CREATE TABLE dbo.G
(
  x VARCHAR(10) NOT NULL
    CONSTRAINT FK_G_X FOREIGN KEY REFERENCES dbo.X,
  y INT NOT NULL
    CONSTRAINT FK_G_Y FOREIGN KEY REFERENCES dbo.Y,
  CONSTRAINT PK_G PRIMARY KEY (x, y)
);

INSERT INTO dbo.G(x, y) VALUES
  ('A', 1),
  ('A', 2),
  ('B', 1),
  ('B', 3),
  ('C', 3),
  (‘C’, 4),
  (‘D’, 3);
GO


-- M является паросочетанием в G
CREATE TABLE dbo.M
(
  x VARCHAR(10) NOT NULL
    CONSTRAINT UQ_M_x UNIQUE,
  y INT NOT NULL
    CONSTRAINT UQ_M_y UNIQUE,
  CONSTRAINT PK_M PRIMARY KEY (x, y),
  CONSTRAINT FK_M_G FOREIGN KEY (x, y) REFERENCES dbo.G(x, y)
);

-- Очистка
SET NOCOUNT ON;
USE tempdb;

DROP TABLE IF EXISTS dbo.M, dbo.G, dbo.X, dbo.Y;
DROP FUNCTION IF EXISTS dbo.GetNums;
GO

-- Вспомогательная функция dbo.GetNums
CREATE FUNCTION dbo.GetNums(@low AS BIGINT, @high AS BIGINT) RETURNS TABLE
AS
RETURN
  WITH
    L0   AS (SELECT c FROM (SELECT 1 UNION ALL SELECT 1) AS D(c)),
    L1   AS (SELECT 1 AS c FROM L0 AS A CROSS JOIN L0 AS B),
    L2   AS (SELECT 1 AS c FROM L1 AS A CROSS JOIN L1 AS B),
    L3   AS (SELECT 1 AS c FROM L2 AS A CROSS JOIN L2 AS B),
    L4   AS (SELECT 1 AS c FROM L3 AS A CROSS JOIN L3 AS B),
    L5   AS (SELECT 1 AS c FROM L4 AS A CROSS JOIN L4 AS B),
    Nums AS (SELECT ROW_NUMBER() OVER(ORDER BY (SELECT NULL)) AS rownum
             FROM L5)
  SELECT TOP(@high - @low + 1) @low + rownum - 1 AS n
  FROM Nums
  ORDER BY rownum;
GO

CREATE TABLE dbo.X
(
  x VARCHAR(10) NOT NULL CONSTRAINT PK_X PRIMARY KEY,
  moreonx VARCHAR(20) NOT NULL
);

CREATE TABLE dbo.Y
(
  y INT NOT NULL CONSTRAINT PK_Y PRIMARY KEY,
  moreony VARCHAR(20) NOT NULL
);

CREATE TABLE dbo.G
(
  x VARCHAR(10) NOT NULL
    CONSTRAINT FK_G_X FOREIGN KEY REFERENCES dbo.X,
  y INT NOT NULL
    CONSTRAINT FK_G_Y FOREIGN KEY REFERENCES dbo.Y,
  CONSTRAINT PK_G PRIMARY KEY (x, y)
);

CREATE TABLE dbo.M
(
  x VARCHAR(10) NOT NULL
    CONSTRAINT UQ_M_x UNIQUE,
  y INT NOT NULL
    CONSTRAINT UQ_M_y UNIQUE,
  CONSTRAINT PK_M PRIMARY KEY (x, y),
  CONSTRAINT FK_M_G FOREIGN KEY (x, y) REFERENCES dbo.G(x, y)
);
GO

DECLARE @n AS INT = 10000000; -- ~ общее количество строк
SET @n = SQRT(@n * 2); -- количество членов арифметической последовательности

INSERT INTO dbo.X(x, moreonx)
  SELECT
    RIGHT('000000000' + CAST(N.n AS VARCHAR(10)), 10) AS x,
    'Applicant ' + RIGHT('000000000' + CAST(N.n AS VARCHAR(10)), 10) AS moreonx
  FROM dbo.GetNums(1, @n) AS N;

INSERT INTO dbo.Y(y, moreony)
  SELECT
    N.n AS y,
    'Job ' + CAST(N.n AS VARCHAR(10)) AS moreonx
  FROM dbo.GetNums(1, @n) AS N;

INSERT INTO dbo.G WITH (TABLOCK) (x, y)
  SELECT RIGHT('000000000' + CAST(X.n AS VARCHAR(10)), 10) AS x, Y.n AS y
  FROM dbo.GetNums(1, @n) AS X
    CROSS APPLY (SELECT TOP (@n - X.n + 1) n
                 FROM dbo.GetNums(1, @n)
                 ORDER BY NEWID()) AS Y;

CREATE OR ALTER PROC dbo.MaximalMatching
AS
SET NOCOUNT, XACT_ABORT ON;
DECLARE @n AS BIGINT, @x AS VARCHAR(10), @y AS INT;
TRUNCATE TABLE dbo.M;
CREATE TABLE #G
(
  n BIGINT NOT NULL,
  x VARCHAR(10) NOT NULL,
  y INT NOT NULL,
  INDEX idx_n_y CLUSTERED(n, y)
);
WITH C AS
(
  SELECT x, y,
    COUNT(*) OVER(PARTITION BY x) AS cnt
  FROM dbo.G
)
INSERT INTO #G (n, x, y)
  SELECT DENSE_RANK() OVER(ORDER BY cnt, x) AS n, x, y
  FROM C;
SELECT TOP (1) @n = n, @x = x, @y = y
FROM #G
ORDER BY n, y;
WHILE @@ROWCOUNT > 0
BEGIN
  INSERT INTO dbo.M(x, y) VALUES(@x, @y);
  SELECT TOP (1) @n = n, @x = x, @y = y
  FROM #G AS G
  WHERE n > @n
    AND NOT EXISTS ( SELECT * FROM dbo.M WHERE M.y = G.y )
  ORDER BY n, y;
END;
DROP TABLE #G;
GO

CREATE OR ALTER FUNCTION dbo.AugmentingPath()
RETURNS @P TABLE
(
  x VARCHAR(10) NOT NULL,
  y INT NOT NULL,
  PRIMARY KEY (x, y)
)
AS
BEGIN
  DECLARE
    @i AS INT = 0, -- Уровень итерации
    @pathfound AS INT = 0; -- Флаг, указывающий на обнаружение увеличивающегося пути
  -- Набор вершин x, рассматриваемый на каждой итерации
  -- Имеет родителя y, который ведет к x
  DECLARE @X AS TABLE
  (
    x VARCHAR(10) NOT NULL PRIMARY KEY,
    parent_y INT NULL,
    i INT NOT NULL
  );
  -- Набор вершин y, обрабатываемый на каждой итерации
  -- Имеет родителя x, который ведет к y
  DECLARE @Y AS TABLE
  (
    y INT NOT NULL PRIMARY KEY,
    parent_x VARCHAR(10) NOT NULL,
    i INT NOT NULL
  );
-- Попытайтесь найти увеличивающийся путь размера 1
  -- An edge from G with a free x and a free y Ребро из G с свободной x и свободной y
  --   («свободной» означает несовпадающей с любой вершиной в M)
  INSERT INTO @P(x, y)
    SELECT TOP (1) x, y
    FROM dbo.G
    WHERE NOT EXISTS ( SELECT * FROM dbo.M WHERE M.x = G.x )
      AND NOT EXISTS ( SELECT * FROM dbo.M WHERE M.y = G.y );
  IF @@ROWCOUNT > 0 RETURN;
  -- Если увеличивающийся путь размером 1 не обнаружен, инициализировать @X
  -- с отдельными свободными вершинами x из G
  -- Мы уже знаем, что если они существуют, то указывают на сопоставленные вершины y
  INSERT INTO @X(x, parent_y, i)
    SELECT DISTINCT x, NULL AS parent_y, @i AS i
    FROM dbo.G
    WHERE NOT EXISTS ( SELECT * FROM dbo.M WHERE M.x = G.x );
  IF @@ROWCOUNT = 0 RETURN;
  -- Пока увеличивающийся путь не обнаружен
  WHILE @pathfound = 0
  BEGIN
 
    SET @i += 1;
-- Добавьте к @Y раздельные сопоставленные вершины y из G, которые имеют
    --   родительскую вершину x в @X из предшествующей итерации
    --   и которых еще нет в y
    -- Используйте MIN(x) для y как родителя, поскольку в конечном итоге нам нужен
    --   только один (любой) увеличивающийся путь, поэтому в случае нескольких
    --   родительских x не имеет значения, из которого мы пришли к y
    --   все обработанные «родители» содержатся в @X, поэтому мы избегаем
    --   повторных обращений на последующих итерациях
    INSERT INTO @Y(y, parent_x, i)
      SELECT G.y, MIN(G.x) AS parent_x, @i AS i
      FROM dbo.G
        INNER JOIN @X AS X
          ON G.x = X.x
          AND X.i = @i - 1
      WHERE NOT EXISTS ( SELECT * FROM @Y AS Y WHERE Y.y = G.y )
      GROUP BY G.y;
      IF @@ROWCOUNT = 0 RETURN;
      -- Если существуют новые вершины y, ищите соответствующие вершины x в M
    -- Они должны существовать и должны отличаться
    --   (поскольку соединенные вершины y с предыдущего уровня сопоставлены)
    INSERT INTO @X(x, parent_y, i)
      SELECT M.x, Y.y AS parent_y, @i AS i
      FROM dbo.M
        INNER JOIN @Y AS Y
          ON M.y = Y.y
          AND Y.i = @i;
-- Добавьте к @P любое ребро из G с свободной y
    --    и x из текущего уровня в @X
    -- Если такая вершина существует, мы обнаружили увеличивающийся путь
    INSERT INTO @P(x, y)
      SELECT TOP (1) G.x, G.y
      FROM dbo.G
        INNER JOIN @X AS X
          ON G.x = X.x
          AND X.i = @i
      WHERE NOT EXISTS ( SELECT * FROM dbo.M WHERE M.y = G.y );
 
    IF @@ROWCOUNT > 0
      SET @pathfound = 1;
  END;

  -- Если пришли сюда, увеличивающийся путь должен существовать, и его длина больше одного сегмента
  -- Сконструируйте путь из @P, @X и @Y
  WHILE @i > 0
  BEGIN
    SET @i -= 1;

    INSERT INTO @P(x, y)
      SELECT X.x, X.parent_y AS y
      FROM @P AS P
        INNER JOIN @X AS X
          ON P.x = X.x
          AND X.i = @i + 1
 
    INSERT INTO @P(x, y)
      SELECT Y.parent_x AS x, Y.y AS y
      FROM @P AS P
        INNER JOIN @Y AS Y
          ON P.y = Y.y
          AND Y.i = @i + 1
  END;
 
  RETURN;

END;
GO

DECLARE @i AS INT = 0, @dt AS DATETIME2 = SYSDATETIME(), @cnt AS INT;
-- Начинаем с поиска наибольшего паросочетания
EXEC dbo.MaximalMatching;
SET @cnt = (SELECT COUNT(*) FROM dbo.M);
PRINT 'Maximal matching with '
  + CAST(@cnt AS VARCHAR(10))
  + ' matches found in '
  + CAST(DATEDIFF(second, @dt, SYSDATETIME()) AS VARCHAR(10))
  + ' seconds.';
SET @dt = SYSDATETIME();

-- Для приращения пути, обнаруженного на последнем проходе, ищем другое и выполняем приращение,
-- то есть задаем M = M ⊕ P (симметрическая разность)
WHILE 1 = 1
BEGIN
  MERGE INTO dbo.M
  USING dbo.AugmentingPath() AS P
    ON M.x = P.x AND M.y = P.y

  -- Ниже добавление для обхода ошибки (благодарность Полу Уайту)
  WHEN MATCHED AND 0 = 1 THEN UPDATE SET x = 'Thanks, Paul White!', y = 1759
  WHEN MATCHED THEN DELETE
  WHEN NOT MATCHED THEN INSERT(x, y) VALUES(P.x, P.y);
  IF @@ROWCOUNT = 0 BREAK;
  SET @i += 1;
END;
PRINT 'Processed ' + CAST(@i AS VARCHAR(10))
  + ' augmenting paths in '
  + CAST(DATEDIFF(second, @dt, SYSDATETIME()) AS VARCHAR(10))
  + ‘ more seconds.’;
-- Возвращается паросочетание максимальной мощности
SELECT x, y
FROM dbo.M;