The stable marriage problem has been stated as follows:

Given n men and n women, where each person has ranked all members of the opposite sex
in order of preference, marry the men and women together such that
there are no two people of opposite sex who would both rather have each other
than their current partners.
When there are no such pairs of people, the set of marriages is deemed stable.

def smp(A, B):
    A_unpaired = list(A.keys())
    pairs = {}

    while A_unpaired:
        a = A_unpaired.pop(0)
        A_preferences = A[a]
        b = A_preferences.pop(0)
        edge = pairs.get(b)
        if not edge:
            pairs[b] = a
        else:
            B_preferences = B[b]
            index_old = B_preferences.index(edge)
            index_new = B_preferences.index(a)
            if index_new < index_old:
                pairs[b] = a
                if len(A[edge]):  # has more preferences
                    A_unpaired.append(edge)
            else:
                if A_preferences:
                    A_unpaired.append(a)
    return pairs

def example_1():
    A = {
        1: [2, 1, 3, 4],
        2: [4, 1, 2, 3],
        3: [1, 3, 2, 4],
        4: [2, 3, 1, 4],
    }

    B = {
        1: [1, 3, 2, 4],
        2: [3, 4, 1, 2],
        3: [4, 2, 3, 1],
        4: [3, 2, 1, 4],
    }

    pairs = smp(A, B)
    edges = {v: u for (u, v) in sorted(pairs.items())}
    assert edges == {1: 1, 2: 4, 3: 3, 4: 2}
    print(edges)

$ python smp.py
{1: 1, 4: 2, 3: 3, 2: 4}

from pprint import pprint


A = {
 "abi":  ["bob", "fred", "jon", "gav", "ian", "abe", "dan", "ed", "col", "hal"],
 "bea":  ["bob", "abe", "col", "fred", "gav", "dan", "ian", "ed", "jon", "hal"],
 "cath": ["fred", "bob", "ed", "gav", "hal", "col", "ian", "abe", "dan", "jon"],
 "dee":  ["fred", "jon", "col", "abe", "ian", "hal", "gav", "dan", "bob", "ed"],
 "eve":  ["jon", "hal", "fred", "dan", "abe", "gav", "col", "ed", "ian", "bob"],
 "fay":  ["bob", "abe", "ed", "ian", "jon", "dan", "fred", "gav", "col", "hal"],
 "gay":  ["jon", "gav", "hal", "fred", "bob", "abe", "col", "ed", "dan", "ian"],
 "hope": ["gav", "jon", "bob", "abe", "ian", "dan", "hal", "ed", "col", "fred"],
 "ivy":  ["ian", "col", "hal", "gav", "fred", "bob", "abe", "ed", "jon", "dan"],
 "jan":  ["ed", "hal", "gav", "abe", "bob", "jon", "col", "ian", "fred", "dan"]}

B = {
 "abe":  ["abi", "eve", "cath", "ivy", "jan", "dee", "fay", "bea", "hope", "gay"],
 "bob":  ["cath", "hope", "abi", "dee", "eve", "fay", "bea", "jan", "ivy", "gay"],
 "col":  ["hope", "eve", "abi", "dee", "bea", "fay", "ivy", "gay", "cath", "jan"],
 "dan":  ["ivy", "fay", "dee", "gay", "hope", "eve", "jan", "bea", "cath", "abi"],
 "ed":   ["jan", "dee", "bea", "cath", "fay", "eve", "abi", "ivy", "hope", "gay"],
 "fred": ["bea", "abi", "dee", "gay", "eve", "ivy", "cath", "jan", "hope", "fay"],
 "gav":  ["gay", "eve", "ivy", "bea", "cath", "abi", "dee", "hope", "jan", "fay"],
 "hal":  ["abi", "eve", "hope", "fay", "ivy", "cath", "jan", "bea", "gay", "dee"],
 "ian":  ["hope", "cath", "dee", "gay", "bea", "abi", "fay", "ivy", "jan", "eve"],
 "jon":  ["abi", "fay", "jan", "gay", "eve", "bea", "dee", "cath", "ivy", "hope"]}


A_names = {n: i for i, n in enumerate(A.keys(), 1)}
B_names = {n: i for i, n in enumerate(B.keys(), 1)}

A = {A_names[aname]: [B_names[bname] for bname in A[aname]] for aname in A}
B = {B_names[bname]: [A_names[aname] for aname in B[bname]] for bname in B}

pprint(A)
pprint(B)

{1: [2, 6, 10, 7, 9, 1, 4, 5, 3, 8],
 2: [2, 1, 3, 6, 7, 4, 9, 5, 10, 8],
 3: [6, 2, 5, 7, 8, 3, 9, 1, 4, 10],
 4: [6, 10, 3, 1, 9, 8, 7, 4, 2, 5],
 5: [10, 8, 6, 4, 1, 7, 3, 5, 9, 2],
 6: [2, 1, 5, 9, 10, 4, 6, 7, 3, 8],
 7: [10, 7, 8, 6, 2, 1, 3, 5, 4, 9],
 8: [7, 10, 2, 1, 9, 4, 8, 5, 3, 6],
 9: [9, 3, 8, 7, 6, 2, 1, 5, 10, 4],
 10: [5, 8, 7, 1, 2, 10, 3, 9, 6, 4]}

{1: [1, 5, 3, 9, 10, 4, 6, 2, 8, 7],
 2: [3, 8, 1, 4, 5, 6, 2, 10, 9, 7],
 3: [8, 5, 1, 4, 2, 6, 9, 7, 3, 10],
 4: [9, 6, 4, 7, 8, 5, 10, 2, 3, 1],
 5: [10, 4, 2, 3, 6, 5, 1, 9, 8, 7],
 6: [2, 1, 4, 7, 5, 9, 3, 10, 8, 6],
 7: [7, 5, 9, 2, 3, 1, 4, 8, 10, 6],
 8: [1, 5, 8, 6, 9, 3, 10, 2, 7, 4],
 9: [8, 3, 4, 7, 2, 1, 6, 9, 10, 5],
 10: [1, 6, 10, 7, 5, 2, 4, 3, 9, 8]}

from data import A_names, B_names, A, B
from pprint import pprint


def example_2():
    pairs = smp(A, B)
    edges = {v: u for (u, v) in sorted(pairs.items())}

    A = {i: n for i, n in enumerate(A_names.keys(), 1)}
    B = {i: n for i, n in enumerate(B_names.keys(), 1)}

    expected = {
        "abi": "jon",
        "bea": "fred",
        "cath": "bob",
        "dee": "col",
        "eve": "hal",
        "fay": "dan",
        "gay": "gav",
        "hope": "ian",
        "ivy": "abe",
        "jan": "ed",
    }
    got = {A[k]: B[v] for k, v in edges.items()}
    for ek, ev in expected.items():
        assert got[ek] == ev, "%s (got %s, expected: %s)"  % (ek, got[ek], ev)
    pprint(got)
    pprint(edges)

{'abi': 'jon',
 'bea': 'fred',
 'cath': 'bob',
 'dee': 'col',
 'eve': 'hal',
 'fay': 'dan',
 'gay': 'gav',
 'hope': 'ian',
 'ivy': 'abe',
 'jan': 'ed'}

Edges: {1: 10, 2: 6, 3: 2, 4: 3, 5: 8, 6: 4, 7: 7, 8: 9, 9: 1, 10: 5}

CREATE TABLE A (
       id SERIAL PRIMARY KEY,
       src INTEGER NOT NULL -- person 'a', 
       dst INTEGER NOT NULL -- preference in 'B',
       is_processed BOOLEAN DEFAULT FALSE
);

CREATE UNIQUE INDEX ON A(src, dst);

CREATE TABLE B (
       id SERIAL PRIMARY KEY,
       src INTEGER NOT NULL -- person 'b', 
       dst INTEGER NOT NULL -- preference in 'A'
);

CREATE UNIQUE INDEX ON B(src, dst);

CREATE TABLE edges (
       src INTEGER NOT NULL -- person 'a',
       dst INTEGER NOT NULL -- person 'b'
);

CREATE UNIQUE INDEX ON edges(src, dst);

CREATE TABLE A_unpaired (
       id SERIAL PRIMARY KEY,
       a INTEGER NOT NULL
);

CREATE OR REPLACE FUNCTION smp()
RETURNS SETOF edges
AS $$
DECLARE
    n_unpaired_ INTEGER;      -- number of unpaired in A

    person_a_ INTEGER;        -- person 'a'
    person_b_ INTEGER;        -- person 'b'
    edge_ INTEGER;            -- matched pair

    index_old_ INTEGER;       -- preference priority
    index_new_ INTEGER;       -- preference priority

    n_preferences_ INTEGER;   -- number of preferences remaining for person_a_
BEGIN
    -- Initialize A_unpaired with all distinct proposors (A).
    INSERT INTO A_unpaired(a) SELECT DISTINCT(src) FROM A ORDER BY src;

    -- Do rounds
    WHILE TRUE LOOP
       -- Check if there are any unpaired proposors. Exit if none.
       SELECT COUNT(*) FROM A_unpaired INTO n_unpaired_;
       IF n_unpaired_ = 0 THEN
             EXIT;
       END IF;

       -- Remove next person 'a' from A_unpaired.
       DELETE FROM A_unpaired WHERE id IN (
              SELECT id FROM A_unpaired ORDER BY id LIMIT 1
       ) RETURNING a INTO person_a_;

       -- Fetch next preference of person_a_.
       SELECT dst FROM A WHERE src = person_a_ AND NOT is_processed
              ORDER BY id
              LIMIT 1 INTO person_b_;

       -- Mark this preference of person_a_ as already processed.
       UPDATE A SET is_processed = TRUE WHERE src = person_a_ AND dst = person_b_;

       IF person_b_ IS NOT NULL THEN
           -- Check if person_b_ is already paired.
           SELECT dst FROM edges WHERE src = person_b_ INTO edge_;  

           IF NOT FOUND THEN
              -- person_b_ had no pair, make a - b pair.
              INSERT INTO edges(src, dst) VALUES(person_b_, person_a_);
           ELSE
              -- person_b_ already has a pair, check if they
              -- prefer this person_a_ over their current pair.
              SELECT id FROM B WHERE src = person_b_ AND dst = edge_ INTO index_old_;
              SELECT id FROM B WHERE src = person_b_ AND dst = person_a_ INTO index_new_;

              IF index_new_ < index_old_ THEN
                 -- Found a better match, remove old pair and pair person_b_ with person_a_.
                 DELETE FROM edges WHERE src = person_b_;
                 INSERT INTO edges(src, dst) VALUES(person_b_, person_a_);
                 -- If previous paired 'a' has other preferences,
                 -- move it back to the pool of unpaired.
                 SELECT COUNT(*) FROM A WHERE src = edge_
                        AND NOT is_processed INTO n_preferences_;

                 IF n_preferences_ > 0 THEN
                    INSERT INTO A_unpaired (a) VALUES(edge_);
                 END IF;
              ELSE
                 -- No match, but if person_a_ has other preferences, move it back
                 -- to the pool of unpaired.
                 SELECT COUNT(*) FROM A WHERE src = person_a_
                        AND NOT is_processed INTO n_preferences_;

                 IF n_preferences_ > 0 THEN
                    INSERT INTO A_unpaired (a) VALUES(person_a_);
                 END IF;
              END IF;
           END IF;
       END IF;

       END LOOP;

    -- Return all pairs.
    RETURN QUERY SELECT dst, src FROM edges ORDER BY dst;
END
$$
LANGUAGE plpgsql;

$ GRAPH=graph-simple.sql make
dropdb --if-exists smptest;
createdb smptest;
psql -1q smptest < schema.sql
psql -1q smptest < graph-simple.sql
psql -1q smptest < smp.sql 
psql smptest -c "SELECT * FROM smp()"
 src | dst 
-----+-----
   1 |   1
   2 |   4
   3 |   3
   4 |   2
(4 rows)

$ GRAPH=graph-rosetta-code.sql make
dropdb --if-exists smptest;
createdb smptest;
psql -1q smptest < schema.sql
psql -1q smptest < graph-rosetta-code.sql
psql -1q smptest < smp.sql 
psql smptest -c "SELECT * FROM smp()"
 src | dst 
-----+-----
   1 |  10
   2 |   6
   3 |   2
   4 |   3
   5 |   8
   6 |   4
   7 |   7
   8 |   9
   9 |   1
  10 |   5
(10 rows)