We are given a bipartite graph
G = (A B, E)
in which the
edges incident to every vertex are linearly ordered. The order expresses preferences.
A matching M
is stable if there is no pair
(a, b) E M
such that (1) a
is unmatched or prefers b
over its partner in M
and (2) b
unmatched or prefers a
over its partner in M
. In such a situation
has the intention to switch to b
has the intention to
switch to a
, i.e., the
pairing is unstable.
We provide a function to compute a correct input graph from the preference data, a function that computes the stable matching when the graph is given and a function that checks whether a given matching is stable.
|void||StableMatching(const graph& G, const list< node> & A, const list< node> & B, list< edge> & M)|
|The function takes a bipartite graph G
with sides A
computes a maximal stable matching M
which is A
-optimal. The graph is assumed to be
bidirected, i.e, for each
(a, b) E
we also have
(b, a) E
. It is assumed
that adjacency lists record the preferences of the vertices. The running time
is O(n + m)
Precondition The graph G is bidirected and a map.
Sets A and B only contain nodes of graph G . In addition they are disjoint from each other.
|bool||CheckStableMatching(const graph& G, const list< node> & A, const list< node> & B, const list< edge> & M)|
|returns true if M
is a stable matching in G
The running time is O(n + m)
Precondition A and B only contain nodes from G .
The graph G is bipartite with respect to lists A and B .
|void||CreateInputGraph(graph& G, list< node> & A, list< node> & B, node_map< int> & nodes_a, node_map< int> & nodes_b, const list< int> & InputA, const list< int> & InputB, const map< int, list< int> > & preferencesA, const map< int, list< int> > & preferencesB)|
|The function takes a list of objects InputA
and a list of objects InputB
The objects are represented bei integer numbers, multiple occurences
of the same number in the same list are ignored. The maps
give for each object i
the list of partner candidates
with respect to a matching. The lists are decreasingly ordered according to the preferences.
The function computes the input data G
. The maps
provide the objects in A
corresponding to the nodes in the graph.
Precondition The entries in the lists in the preference maps only contain elements from InputB resp. InputA .
There are no multiple occurences of an element in the same such list.