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 in G 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 is
unmatched or prefers a over its partner in M. In such a situation
a has the intention to switch to b and 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 and B and
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
preferencesA and
preferencesB 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, A and B for calling
the function
StableMatching(constgraph&,...). The maps
nodesa and
nodesb provide the objects in A and B 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. |