We give functions
You may skip the following subsections and restrict on reading the function signatures and the corresponding comments in order to use these functions. If you are interested in technical details, or if you would like to ensure that the input data is well chosen, or if you would like to know the exact meaning of all output parameters, you should continue reading.
The functions in this section are template functions. It is intended that in the near future the template parameter NT can be instantiated with any number type. Please note that for the time being the template functions are only guaranteed to perform correctly for the number type int. In order to use the template version of the function the appropriate .hfile must be included.
#include <LEDA/graph/templates/mw_matching.h>
There are preinstantiations for the number types int. In order to use them either
#include <LEDA/graph/mw_matching.h>
or
#include <LEDA/graph/graph_alg.h>
has to be included (the latter file includes the former).
The connection
between template functions and preinstantiated functions is discussed in
detail in the section ``Templates for Network Algorithms'' of the LEDA book.
The function names of the preinstantiated versions and the template versions
only differ by an additional suffix _T
in the names of the latter ones.
In the nonperfect matching case we have for a potential pot[u] of a node u and for a potential z_{B} of a blossom B :
The function CHECK_WEIGHTS may be used to test whether the edge weights are feasible or not. It is automatically called at the beginning of each of the algorithms provided in this chapter.
template < class NT>  
list< edge>  MAX_WEIGHT_MATCHING_T(const graph& G, const edge_array< NT> & w, bool check = true, int heur = 2)  
computes a maximumweight matching M of the underlying undirected graph of graph G with weight
function w. If check is set to true, the optimality of M is checked internally.
The heuristic used for the construction of an initial matching is determined by heur. Precondition All edge weights must be nonnegative.


template < class NT>  
list< edge>  MAX_WEIGHT_MATCHING_T(const graph& G, const 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 maximumweight matching M of the underlying undirected graph of 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.
If check is set to true, the optimality of M is checked internally.
The heuristic used for the construction of an initial matching is determined by heur. Precondition All edge weights must be nonnegative.


template < class NT>  
bool  CHECK_MAX_WEIGHT_MATCHING_T(const graph& G, const edge_array< NT> & w, const list< edge> & M, const node_array< NT> & pot, const array< two_tuple< NT, int> > & BT, const node_array< int> & b)  
checks if M together with the dual solution represented by pot, BT and b are
optimal. The function returns true if M is a maximumweight matching of G with weight
function w.


template < class NT>  
list< edge>  MAX_WEIGHT_PERFECT_MATCHING_T(const graph& G, const edge_array< NT> & w, bool check = true, int heur = 2)  
computes a maximumweight perfect matching M of the underlying undirected graph of 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 used for the construction of an initial matching is determined by heur.


template < class NT>  
list< edge>  MAX_WEIGHT_PERFECT_MATCHING_T(const graph& G, const 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 maximumweight perfect matching M of the underlying undirected graph of 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.
If check is set to true, the optimality of M is checked internally.
The heuristic used for the construction of an initial matching is determined by heur.


template < class NT>  
bool  CHECK_MAX_WEIGHT_PERFECT_MATCHING_T(const graph& G, const edge_array< NT> & w, const list< edge> & M, const node_array< NT> & pot, const array< two_tuple< NT, int> > & BT, const node_array< int> & b)  
checks if M together with the dual solution represented by pot, BT and b are
optimal. The function returns true iff M is a maximumweight perfect matching of G
with weight function w.


template < class NT>  
list< edge>  MIN_WEIGHT_PERFECT_MATCHING_T(const graph& G, const edge_array< NT> & w, bool check = true, int heur = 2)  
computes a minimumweight perfect matching M of the underlying undirected graph of 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 used for the construction of an initial matching is determined by heur.


template < class NT>  
list< edge>  MIN_WEIGHT_PERFECT_MATCHING_T(const graph& G, const 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 minimumweight perfect matching M of the underlying undirected graph of 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.
If check is set to true, the optimality of M is checked internally.
The heuristic used for the construction of an initial matching is determined by heur.


template < class NT>  
bool  CHECK_MIN_WEIGHT_PERFECT_MATCHING_T(const graph& G, const edge_array< NT> & w, const list< edge> & M, const node_array< NT> & pot, const array< two_tuple< NT, int> > & BT, const node_array< int> & b)  
checks if M together with the dual solution represented by pot, BT and b are
optimal. The function returns true iff M is a minimumweight matching of G with
weight function w.


template < class NT>  
bool  CHECK_WEIGHTS_T(const 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.
If the edge weights are not multiplicatives of 4
all edge weights will be
scaled by a factor of 4
. The modified weight function is returned in w
then.
This function is automatically called by each of the maximum weighted machting
algorithms provided in this chapter, the user does not have to take care of it.
