graphs.gale_shapley_bigraph
===========================

.. py:module:: graphs.gale_shapley_bigraph


Functions
---------

.. autoapisummary::

   graphs.gale_shapley_bigraph.stable_matching


Module Contents
---------------

.. py:function:: 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]