Perfect matching check in a bipartite graph using PL/pgSQL

bipartite-perfect-match-plpgsql.sql

/**
    This file shows how to do a perfect matching check in a bipartite graph using PL/pgSQL.
*/

-- Use the pg_temp schema to avoid conflicts with other sessions

SET search_path TO pg_temp;

CREATE EXTENSION IF NOT EXISTS plpgsql;
CREATE TABLE IF NOT EXISTS lhs (
    id serial primary key
);

CREATE TABLE IF NOT EXISTS rhs (
    id serial primary key
);

CREATE TABLE IF NOT EXISTS edges (
    lhs_id integer references lhs(id),
    rhs_id integer references rhs(id),
    primary key (lhs_id, rhs_id)
);


/**
 * This SQL function checks if a perfect match exists between two sets of elements.
 * It takes no input parameters and returns a boolean value indicating whether a perfect match exists or not.
 * A perfect match exists if there is a one-to-one mapping between the elements of the two sets, such that each
 * element from the first set is matched with exactly one element from the second set.
 * The function uses a breadth-first search algorithm to find the perfect match.
 * 
 * @returns {boolean} - Returns true if a perfect match exists, false otherwise.
 */
CREATE OR REPLACE FUNCTION pg_temp.perfect_match_exists()
RETURNS boolean AS $$
DECLARE
    lhs_count integer;
    rhs_count integer;
    matching integer[];
    visited boolean[];
    queue integer[];
    v integer;
    u integer;
BEGIN
    SELECT COUNT(*) INTO lhs_count FROM lhs;
    SELECT COUNT(*) INTO rhs_count FROM rhs;
    
    IF lhs_count <> rhs_count THEN
        RETURN false;
    END IF;

    -- If there are not enough edges, there can't be a perfect matching
    IF (SELECT COUNT(*) FROM edges) < lhs_count THEN
        RETURN false;
    END IF;
    
    matching := ARRAY(SELECT 0 FROM generate_series(1, rhs_count));
    visited := ARRAY(SELECT false FROM generate_series(1, lhs_count));
    
    FOR i IN 1..lhs_count LOOP
        IF NOT visited[i] THEN
            queue := ARRAY[i];
            
            WHILE array_length(queue, 1) > 0 LOOP
                v := queue[1];
                queue := queue[2:];
                
                IF NOT visited[v] THEN
                    visited[v] := true;
                    
                    FOR u IN SELECT rhs_id FROM edges WHERE lhs_id = v LOOP
                        IF matching[u] = 0 THEN
                            matching[u] := v;
                            EXIT;
                        ELSE
                            queue := array_append(queue, matching[u]);
                        END IF;
                    END LOOP;
                    
                    IF NOT EXISTS (SELECT 1 FROM edges WHERE lhs_id = v AND rhs_id = matching[v]) THEN
                        RETURN false;
                    END IF;
                END IF;
            END LOOP;
        END IF;
    END LOOP;
    
    RETURN true;
END;
$$ LANGUAGE plpgsql;

-- Test Case 1: Perfect matching exists
\echo 'Test Case 1: Perfect matching exists';
TRUNCATE lhs, rhs, edges;
INSERT INTO lhs VALUES (1), (2), (3);
INSERT INTO rhs VALUES (1), (2), (3);
INSERT INTO edges VALUES (1, 1), (2, 2), (3, 3);
SELECT
    true as expected,
    pg_temp.perfect_match_exists() as actual,
    true = pg_temp.perfect_match_exists() as passed;

-- Test Case 2: No perfect matching (unequal number of vertices)
\echo 'Test Case 2: No perfect matching (unequal number of vertices)';
TRUNCATE lhs, rhs, edges;
INSERT INTO lhs VALUES (1), (2), (3);
INSERT INTO rhs VALUES (1), (2);
INSERT INTO edges VALUES (1, 1), (2, 2);
SELECT
    false as expected,
    pg_temp.perfect_match_exists() as actual,
    false = pg_temp.perfect_match_exists() as passed;

-- Test Case 3: No perfect matching (unequal number of edges)
\echo 'Test Case 3: No perfect matching (unequal number of edges)';
TRUNCATE lhs, rhs, edges;
INSERT INTO lhs VALUES (1), (2), (3);
INSERT INTO rhs VALUES (1), (2), (3);
INSERT INTO edges VALUES (1, 1), (2, 2);
SELECT
    false as expected,
    pg_temp.perfect_match_exists() as actual,
    false = pg_temp.perfect_match_exists() as passed;

-- Test Case 4: Perfect matching with multiple edges
\echo 'Test Case 4: Perfect matching with multiple edges';
TRUNCATE lhs, rhs, edges;
INSERT INTO lhs VALUES (1), (2), (3);
INSERT INTO rhs VALUES (1), (2), (3);
INSERT INTO edges VALUES (1, 1), (1, 2), (2, 2), (3, 3);
SELECT
    true as expected,
    pg_temp.perfect_match_exists() as actual,
    true = pg_temp.perfect_match_exists() as passed;

-- Test Case 5: No perfect matching (disconnected graph)
\echo 'Test Case 5: No perfect matching (disconnected graph)';
TRUNCATE lhs, rhs, edges;
INSERT INTO lhs VALUES (1), (2), (3);
INSERT INTO rhs VALUES (1), (2), (3);
INSERT INTO edges VALUES (1, 1), (2, 2);
SELECT
    false as expected,
    pg_temp.perfect_match_exists() as actual,
    false = pg_temp.perfect_match_exists() as passed;

-- Test Case 6: Empty graph
\echo 'Test Case 6: Empty graph';
TRUNCATE lhs, rhs, edges;
SELECT
    true as expected,
    pg_temp.perfect_match_exists() as actual,
    true = pg_temp.perfect_match_exists() as passed;

-- Test Case 7: Single vertex in each set
\echo 'Test Case 7: Single vertex in each set';
TRUNCATE lhs, rhs, edges;
INSERT INTO lhs VALUES (1);
INSERT INTO rhs VALUES (1);
INSERT INTO edges VALUES (1, 1);
SELECT
    true as expected,
    pg_temp.perfect_match_exists() as actual,
    true = pg_temp.perfect_match_exists() as passed;


-- Test Case 8: Multiple perfect matchings
\echo 'Test Case 8: Multiple perfect matchings';
TRUNCATE lhs, rhs, edges;
INSERT INTO lhs VALUES (1), (2), (3);
INSERT INTO rhs VALUES (1), (2), (3);
INSERT INTO edges VALUES (1, 1), (1, 2), (2, 1), (2, 2), (3, 3);
SELECT
    true as expected,
    pg_temp.perfect_match_exists() as actual,
    true = pg_temp.perfect_match_exists() as passed;

-- Test Case 9: No perfect matching (unequal number of edges in each set)
\echo 'Test Case 9: No perfect matching (unequal number of edges in each set)';
TRUNCATE lhs, rhs, edges;
INSERT INTO lhs VALUES (1), (2), (3);
INSERT INTO rhs VALUES (1), (2), (3);
INSERT INTO edges VALUES (1, 1), (1, 2), (2, 1), (3, 2);
SELECT
    false as expected,
    pg_temp.perfect_match_exists() as actual,
    false = pg_temp.perfect_match_exists() as passed;

-- Test Case 10: Perfect matching with maximum edges
\echo 'Test Case 10: Perfect matching with maximum edges';
TRUNCATE lhs, rhs, edges;
INSERT INTO lhs VALUES (1), (2), (3);
INSERT INTO rhs VALUES (1), (2), (3);
INSERT INTO edges VALUES (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3);
SELECT
    true as expected,
    pg_temp.perfect_match_exists() as actual,
    true = pg_temp.perfect_match_exists() as passed;

-- Test Case 11: No perfect matching (isolated vertices)
\echo 'Test Case 11: No perfect matching (isolated vertices)';
TRUNCATE lhs, rhs, edges;
INSERT INTO lhs VALUES (1), (2), (3), (4);
INSERT INTO rhs VALUES (1), (2), (3), (4);
INSERT INTO edges VALUES (1, 1), (2, 2), (3, 3);
SELECT
    false as expected,
    pg_temp.perfect_match_exists() as actual,
    false = pg_temp.perfect_match_exists() as passed;

-- Test Case 12: Perfect matching with maximum edges
\echo 'Test Case 12: Perfect matching with maximum edges';
TRUNCATE lhs, rhs, edges;
INSERT INTO lhs VALUES (1), (2), (3);
INSERT INTO rhs VALUES (1), (2), (3);
INSERT INTO edges VALUES (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3);
SELECT
    true as expected,
    pg_temp.perfect_match_exists() as actual,
    true = pg_temp.perfect_match_exists() as passed;

-- Test Case 13: No perfect matching (no edges)
\echo 'Test Case 13: No perfect matching (no edges)';
TRUNCATE lhs, rhs, edges;
INSERT INTO lhs VALUES (1), (2), (3);
INSERT INTO rhs VALUES (1), (2), (3);
SELECT
    false as expected,
    pg_temp.perfect_match_exists() as actual,
    false = pg_temp.perfect_match_exists() as passed;

-- Test Case 14: Large graph with perfect matching
\echo 'Test Case 14: Large graph with perfect matching';
TRUNCATE lhs, rhs, edges;
INSERT INTO lhs SELECT generate_series(1, 100);
INSERT INTO rhs SELECT generate_series(1, 100);
INSERT INTO edges SELECT i, i FROM generate_series(1, 100) AS i;
SELECT
    true as expected,
    pg_temp.perfect_match_exists() as actual,
    true = pg_temp.perfect_match_exists() as passed;

-- Test Case 15: Edges all into one vertex
\echo 'Test Case 15: Edges all into one vertex';
TRUNCATE lhs, rhs, edges;
INSERT INTO lhs VALUES (1), (2), (3), (4), (5);
INSERT INTO rhs VALUES (1), (2), (3), (4), (5);
INSERT INTO edges VALUES (1, 1), (2, 1), (3, 1), (4, 1), (5, 1);
SELECT
    false as expected,
    pg_temp.perfect_match_exists() as actual,
    false = pg_temp.perfect_match_exists() as passed;