MaxWeightedPerfectFractionalMatching
Declared in lemon/fractional_matching.h, in the group Matching Algorithms; the same class on the Doxygen site.
-
template< typename GR , typename WM >
class MaxWeightedPerfectFractionalMatching Weighted fractional perfect matching in general graphs.
This class provides an efficient implementation of fractional matching algorithm. The implementation uses priority queues and provides \(O( nm\log n )\) time complexity.
The maximum weighted fractional perfect matching is a relaxation of the maximum weighted perfect matching problem where the odd set constraints are omitted. It can be formulated with the following linear program.
\[ \sum_{e \in \delta(u)}x_e = 1 \quad \forall u\in V\]\[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\). The result must be the union of a matching with one value edges and a set of odd length cycles with half value edges.The algorithm calculates an optimal fractional 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 \ge w_{uv} \quad \forall uv\in E\]\[\min \sum_{u \in V}y_u \]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.
The primal solution is multiplied by 2. If the value type is integer, then the dual solution is scaled 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 bool start()
Start the algorithm.
This function starts the algorithm.
- Pre:
init() must be called before using this function.
-
inline bool run()
Run the algorithm.
This method runs the
MaxWeightedPerfectFractionalMatchingalgorithm.Note
mwfm.run() is just a shortcut of the following code.
mwpfm.init(); mwpfm.start();
Primal Solution
Functions to get the primal solution, i.e. the maximum weighted 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. This value is scaled by primal scale.
-
inline int matchingSize() const
Return the number of covered nodes in the matching.
This function returns the number of covered nodes in the matching.
-
inline int matching( const Edge & edge ) const
Return the value of the given edge in the matching.
This function returns the value of the given edge in the found matching, scaled by primal scale: 2 for an edge of value 1, 1 for an edge of an odd cycle (a loop included) and 0 for an edge not in the matching.
-
inline Arc matching( const Node & node ) const
Return the fractional matching arc (or edge) incident to the given node.
This function returns one of the fractional matching arc (or edge) incident to the given node in the found matching or
INVALIDif the node is not covered by the matching or if the node is on an odd length cycle then it is the successor edge on the cycle.
-
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.
Public Types