Graph Matching with T-SQL Part 3: Maximum Matching
This article is the third part in a series about graph matching tasks.
October 12, 2017
"The way forward is sometimes the way back…” --Labyrinth 1986
This article is the third part in a series about graph matching tasks. Part 1 introduced what graph matching is and related concepts. Part 2 covered solutions to the maximal matching task and left you with the challenge to handle the maximum matching task. This third part covers a solution to maximum matching. Make sure that you are familiar with the topics covered in the first two parts before proceeding to this article.
As a reminder, suppose you have a set X (say applicants), a disjoint set Y (say jobs), and a bipartite graph G connecting nodes from the two sets (applicant-job pairs where the applicant is qualified to perform the job). A matching M in graph G represents a subset of the edges in G where no two edges are incident (share a node). A maximal matching is a matching to which you cannot add any more edges of the graph. A maximum matching is a maximal matching with the maximum possible number of edges from the graph. Figure 1 shows graph matching examples.
Figure 1 - Graph matching examples
In our applicants-jobs example, you would want to find a maximum matching to maximize the utilization of applicants and fulfillment of jobs.
Sample data
To demonstrate and test the solution for maximum matching, I’ll use the same sample data that I used in the previous articles. Use the following code to create a small set of sample data in order to test the correctness of the solution:
SET NOCOUNT ON;
USE tempdb;
-- Cleanup
DROP TABLE IF EXISTS dbo.M, dbo.G, dbo.X, dbo.Y;
GO
-- Set X, e.g., 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');
-- Set Y, e.g., 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');
-- Graph G = (X, Y, E), e.g., possible applicant-job connections
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 is a matching in G
CREATE TABLE dbo.M
(
x VARCHAR(10) NOT NULL