MaxWeightedPerfectMatching
Declared in lemon/matching.h, in the group Matching Algorithms; the same class on the Doxygen site.
-
template< typename GR , typename WM >
class MaxWeightedPerfectMatching Weighted perfect matching in general graphs.
This class provides an efficient implementation of Edmond’s maximum weighted perfect matching algorithm. The implementation is based on extensive use of priority queues and provides \(O( nm\log n )\) time complexity.
The maximum weighted perfect matching problem is to find a subset of the edges in an undirected graph with maximum overall weight for which each node has exactly one incident edge. It can be formulated with the following linear program.
\[ \sum_{e \in \delta(u)}x_e = 1 \quad \forall u\in V\]\[ \sum_{e \in \gamma(B)}x_e \le \frac{\vert B \vert - 1}{2} \quad \forall B\in\mathcal{O}\]\[x_e \ge 0\quad \forall e\in E\]\[\max \sum_{e\in E}x_ew_e\]where \(\delta(X)\) is the set of edges incident to a node in \(X\), \(\gamma(X)\) is the set of edges with both ends in \(X\) and \(\mathcal{O}\) 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.
\[ y_u + y_v + \sum_{B \in \mathcal{O}, uv \in \gamma(B)}z_B \ge w_{uv} \quad \forall uv\in E\]\[z_B \ge 0 \quad \forall B \in \mathcal{O}\]\[\min \sum_{u \in V}y_u + \sum_{B \in \mathcal{O}} \frac{\vert B \vert - 1}{2}z_B\]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.- Template Parameters:
GR – The undirected graph type the algorithm runs on.
WM – The type edge weight map. The default type is GR::EdgeMap< int >.
Execution Control
The simplest way to execute the algorithm is to use the run() member function.
-
inline void init()
Initialize the algorithm.
This function initializes the algorithm.
-
inline void fractionalInit()
Initialize the algorithm with fractional matching.
This function initializes the algorithm with a fractional matching. This initialization is also called jumpstart heuristic.
-
inline bool start()
Start the algorithm.
This function starts the algorithm.
- Pre:
init() or fractionalInit() must be called before using this function.
-
inline bool run()
Run the algorithm.
This method runs the
MaxWeightedPerfectMatchingalgorithm.Note
mwpm.run() is just a shortcut of the following code.
mwpm.fractionalInit(); mwpm.start();
Primal Solution
Functions to get the primal solution, i.e. the maximum weighted perfect matching.
Either
run() or start() function should be called before using them.-
inline Value matchingWeight() const
Return the weight of the matching.
This function returns the weight of the found matching.
-
inline bool matching( const Edge & edge ) const
Return
trueif the given edge is in the matching.This function returns
trueif the given edge is in the found matching.
-
inline Arc matching( const Node & node ) const
Return the matching arc (or edge) incident to the given node.
This function returns the matching arc (or edge) incident to the given node in the found matching or
INVALIDif the node is not covered by the matching.
-
inline const MatchingMap & matchingMap() const
Return a const reference to the matching map.
This function returns a const reference to a node map that stores the matching arc (or edge) incident to each node.
Dual Solution
Functions to get the dual solution.
Either
run() or start() function should be called before using them.-
inline Value dualValue() const
Return the value of the dual solution.
This function returns the value of the dual solution. It should be equal to the primal value scaled by dual scale.
-
inline Value nodeValue( const Node & n ) const
Return the dual value (potential) of the given node.
This function returns the dual value (potential) of the given node.
-
inline int blossomNum() const
Return the number of the blossoms in the basis.
This function returns the number of the blossoms in the basis.
See also
-
inline int blossomSize( int k ) const
Return the number of the nodes in the given blossom.
This function returns the number of the nodes in the given blossom.
See also
Public Types
Public Functions
-
inline ~MaxWeightedPerfectMatching()
Public Static Attributes
-
class BlossomIt
Iterator for obtaining the nodes of a blossom.
This class provides an iterator for obtaining the nodes of the given blossom. It lists a subset of the nodes. Before using this iterator, you must allocate a MaxWeightedPerfectMatching class and execute it.
Public Functions
-
inline BlossomIt( const MaxWeightedPerfectMatching & algorithm , int variable )
Constructor.
Constructor to get the nodes of the given variable.
- Pre:
Either algorithm.run() or algorithm.start() must be called before initializing this iterator.
-
inline operator Node() const
Conversion to
Node.
-
inline BlossomIt( const MaxWeightedPerfectMatching & algorithm , int variable )