template<typename GR, typename WM>
class lemon::MaxWeightedPerfectMatching< GR, WM >
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>. |
|
| | MaxWeightedPerfectMatching (const Graph &graph, const WeightMap &weight) |
| |
|
The simplest way to execute the algorithm is to use the run() member function.
|
| void | init () |
| | Initialize the algorithm.
|
| |
| void | fractionalInit () |
| | Initialize the algorithm with fractional matching.
|
| |
| bool | start () |
| | Start the algorithm.
|
| |
| bool | run () |
| | Run the algorithm.
|
| |
|
Functions to get the primal solution, i.e. the maximum weighted perfect matching.
Either run() or start() function should be called before using them.
|
| Value | matchingWeight () const |
| | Return the weight of the matching.
|
| |
| bool | matching (const Edge &edge) const |
| | Return true if the given edge is in the matching.
|
| |
| Arc | matching (const Node &node) const |
| | Return the matching arc (or edge) incident to the given node.
|
| |
| const MatchingMap & | matchingMap () const |
| | Return a const reference to the matching map.
|
| |
| Node | mate (const Node &node) const |
| | Return the mate of the given node.
|
| |
|
Functions to get the dual solution.
Either run() or start() function should be called before using them.
|
| Value | dualValue () const |
| | Return the value of the dual solution.
|
| |
| Value | nodeValue (const Node &n) const |
| | Return the dual value (potential) of the given node.
|
| |
| int | blossomNum () const |
| | Return the number of the blossoms in the basis.
|
| |
| int | blossomSize (int k) const |
| | Return the number of the nodes in the given blossom.
|
| |
| Value | blossomValue (int k) const |
| | Return the dual value (ptential) of the given blossom.
|
| |
1.8.2