template<typename GR, typename WM>
class lemon::MaxWeightedMatching< GR, WM >
This class provides an efficient implementation of Edmond's maximum weighted matching algorithm. The implementation is based on extensive use of priority queues and provides time complexity.
The maximum weighted matching problem is to find a subset of the edges in an undirected graph with maximum overall weight for which each node has at most one incident edge. It can be formulated with the following linear program.
where is the set of edges incident to a node in , is the set of edges with both ends in and is the set of odd cardinality subsets of the nodes.
The algorithm calculates an optimal matching and a proof of the optimality. The solution of the dual problem can be used to check the result of the algorithm. The dual linear problem is the following.
The algorithm can be executed with the run() function. After it the matching (the primal solution) and the dual solution can be obtained using the query functions and the BlossomIt nested class, which is able to iterate on the nodes of a blossom. If the value type is integer, then the dual solution is multiplied by 4.
This function returns the matching arc (or edge) incident to the given node in the found matching or INVALID if the node is not covered by the matching.
Precondition
Either run() or start() must be called before using this function.