Next: Minimum Spanning Trees ( Up: Graph Algorithms Previous: General Weighted Matchings ( Contents Index

Stable Matching ( stable_matching )

We are given a bipartite graph G = (A $\cup$ 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) $\in$ E $\setminus$ 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) $\in$ E we also have (b, a) $\in$ 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 nodes $\_$ a and nodes $\_$ b 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.

Next: Minimum Spanning Trees ( Up: Graph Algorithms Previous: General Weighted Matchings ( Contents Index

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) $\in$ E we also have (b, a) $\in$ 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 nodes $\_$ a and nodes $\_$ b 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.