Weighted Matchings in General Graphs ( mw_matching )

We give functions

• to compute maximum-weight matchings in general graphs,
• to compute maximum-weight or minimum-weight perfect matchings in general graphs, and
• to check the optimality of weighted matchings.

The functions in this section are template functions. It is intended that the template parameter NT can be instantiated with any number type. However,

Note: So far the template functions are only guaranteed to perform correctly for the number type int.

In order to use the template functions the appropriate .t-file must be included.

#include <LEDA/templates/mw_matching.t>

All functions for computing maximum or minimum weighted matchings provide a proof of optimality in the form of a dual solution represented by pot, BT and b. We briefly sketch the semantics; for a more extensive discussion refer to the section ``Weighted Matching in General Graphs'' of the LEDA book extensions ( http://www.mpi-sb.mpg.de/~mehlhorn/LEDAbook.html). The potential of each vertex is stored in the node_array pot. BT represents the nested family of odd cardinality sets. Each two_tuple (z_{$\cal {B}$}, p_{$\cal {B}$}) in BT represents a non-trivial blossom $\cal {B}$ having potential z_{$\cal {B}$} and parent index p_{$\cal {B}$}. The parent index p_{$\cal {B}$} is set to -1 if $\cal {B}$ is a surface blossom. Otherwise, p_{$\cal {B}$} stores the index of the entry corresponding to the immediate superblossom of $\cal {B}$. The index range of BT is [0,..., k - 1], where k denotes the number of non-trivial blossoms. When $\cal {B}$_i is a subblossom of $\cal {B}$, the index of the entry corresponding to $\cal {B}$_i is smaller than the one of $\cal {B}$. The parent index for a vertex u is stored in the node_array b.

Each function can be asked to start with either an empty matching ( heur = 0), a greedy matching ( heur = 1) or a fractional matching ( heur = 2); by default, the fractional matching heuristic is used.
In order to avoid rounding errors, all functions expect the edge weights to be multiplicatives of 4. Moreover, in the maximum-weight (non-perfect) matching case all edge weights are assumed to be non-negative. The function CHECK_WEIGHTS may be used to test whether the edge weights are feasible or not.

By defining the _SST_APPROACH token (type #define _SST_APPROACH before the .t-file is included) the algorithm runs a so-called single search tree approach which (for large instances) is not as efficiently as the multiple search tree approach (which is used by default). If additional information about the processing steps of the functions are desired the user may define the _INFO token.

All functions for computing maximum or minimum weighted matchings guarantee a running time of O(nmlog n), where n and m denote the number of vertices and edges, respectively.

template <class NT>
list<edge>	MAX_WEIGHT_MATCHING_T(graph G, edge_array<NT> w, bool check = true, int heur = 2)
		computes a maximum-weight matching M of the undirected graph G with weight function w. If check is set to true, the optimality of M is checked internally. The heuristic heur which is used by the function can be set to 0, 1 or 2. Precondition All edge weights must to be non-negative.
template <class NT>
list<edge>	MAX_WEIGHT_MATCHING_T(graph G, edge_array<NT> w, node_array<NT>& pot, array<two_tuple<NT, int> >& BT, node_array<int>& b, bool check = true, int heur = 2)
		computes a maximum-weight matching M of the undirected graph G with weight function w. The function provides a proof of optimality in the form of a dual solution given by pot, BT and b. As above, if check is set to true, the optimality of M is checked internally. The heuristic heur which is used by the function can be set to 0, 1 or 2. Precondition All edge weights must be non-negative.
template <class NT>
bool	CHECK_MAX_WEIGHT_MATCHING_T(graph G, edge_array<NT> w, list<edge> M, node_array<NT> pot, array<two_tuple<NT, int> > BT, node_array<int> b)
		checks if M together with the dual solution represented by pot, BT and b are optimal. If so, M is a maximum-weight matching of G with weight function w.
template <class NT>
list<edge>	MAX_WEIGHT_PERFECT_MATCHING_T(graph G, edge_array<NT> w, bool check = true, int heur = 2)
		computes a maximum-weight perfect matching M of the undirected graph G and weight function w. If G contains no perfect matching the empty set of edges is returned. If check is set to true, the optimality of M is checked internally. The heuristic heur which is used by the function can be set to 0, 1 or 2.
template <class NT>
list<edge>	MAX_WEIGHT_PERFECT_MATCHING_T(graph G, edge_array<NT> w, node_array<NT>& pot, array<two_tuple<NT, int> >& BT, node_array<int>& b, bool check = true, int heur = 2)
		computes a maximum-weight perfect matching M of the undirected graph G with weight function w. If G contains no perfect matching the empty set of edges is returned. The function provides a proof of optimality in the form of a dual solution given by pot, BT and b. As above, if check is set to true, the optimality of M is checked internally. The heuristic heur which is used by the function can be set to 0, 1 or 2.
template <class NT>
bool	CHECK_MAX_WEIGHT_PERFECT_MATCHING_T(graph G, edge_array<NT> w, list<edge> M, node_array<NT> pot, array<two_tuple<NT, int> > BT, node_array<int> b)
		checks if M together with the dual solution represented by pot, BT and b are optimal. If so, M is a maximum-weight perfect matching of G with weight function w.
template <class NT>
list<edge>	MIN_WEIGHT_PERFECT_MATCHING_T(graph G, edge_array<NT> w, bool check = true, int heur = 2)
		computes a minimum-weight perfect matching M of the undirected graph G with weight function w. If G contains no perfect matching the empty set of edges is returned. If check is set to true, the optimality of M is checked internally. The heuristic heur which is used by the function can be set to 0, 1 or 2.
template <class NT>
list<edge>	MIN_WEIGHT_PERFECT_MATCHING_T(graph G, edge_array<NT> w, node_array<NT>& pot, array<two_tuple<NT, int> >& BT, node_array<int>& b, bool check = true, int heur = 2)
		computes a minimum-weight perfect matching M of the undirected graph G with weight function w. If G contains no perfect matching the empty set of edges is returned. The function provides a proof of optimality in the form of a dual solution given by pot, BT and b. As above, if check is set to true, the optimality of M is checked internally. The heuristic heur which is used by the function can be set to 0, 1 or 2.
template <class NT>
bool	CHECK_MIN_WEIGHT_PERFECT_MATCHING_T(graph G, edge_array<NT> w, list<edge> M, node_array<NT> pot, array<two_tuple<NT, int> > BT, node_array<int> b)
		checks if M together with the dual solution represented by pot, BT and b are optimal. If so, M is a minimum-weight matching of G with weight function w.
template <class NT>
bool	CHECK_WEIGHTS_T(graph G, edge_array<NT> w, bool perfect)
		returns true, if w is a feasible weight function for G; false otherwise. perfect must be set to true in the perfect matching case; otherwise it must be set to false.