graphs.gale_shapley_bigraph

Functions

stable_matching(→ list[int])

Finds the stable match in any bipartite graph, i.e a pairing where no 2 objects

Module Contents

graphs.gale_shapley_bigraph.stable_matching(donor_pref: list[list[int]], recipient_pref: list[list[int]]) → list[int]

Finds the stable match in any bipartite graph, i.e a pairing where no 2 objects prefer each other over their partner. The function accepts the preferences of oegan donors and recipients (where both are assigned numbers from 0 to n-1) and returns a list where the index position corresponds to the donor and value at the index is the organ recipient.

To better understand the algorithm, see also: https://github.com/akashvshroff/Gale_Shapley_Stable_Matching (README). https://www.youtube.com/watch?v=Qcv1IqHWAzg&t=13s (Numberphile YouTube).

>>> donor_pref = [[0, 1, 3, 2], [0, 2, 3, 1], [1, 0, 2, 3], [0, 3, 1, 2]]
>>> recipient_pref = [[3, 1, 2, 0], [3, 1, 0, 2], [0, 3, 1, 2], [1, 0, 3, 2]]
>>> stable_matching(donor_pref, recipient_pref)
[1, 2, 3, 0]