template<typename GR, typename WM>
class lemon::MaxWeightedFractionalMatching< GR, WM >
This class provides an efficient implementation of fractional matching algorithm. The implementation uses priority queues and provides
time complexity.
The maximum weighted fractional matching is a relaxation of the maximum weighted matching problem where the odd set constraints are omitted. It can be formulated with the following linear program.
where
is the set of edges incident to a node in
. 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.
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>. |
|
| MaxWeightedFractionalMatching (const Graph &graph, const WeightMap &weight, bool allow_loops=true) |
|
|
The simplest way to execute the algorithm is to use the run() member function.
|
void | init () |
| Initialize the algorithm.
|
|
void | start () |
| Start the algorithm.
|
|
void | run () |
| Run the algorithm.
|
|
|
Functions to get the primal solution, i.e. the maximum weighted matching.
Either run() or start() function should be called before using them.
|
Value | matchingWeight () const |
| Return the weight of the matching.
|
|
int | matchingSize () const |
| Return the number of covered nodes in the matching.
|
|
int | matching (const Edge &edge) const |
| Return true if the given edge is in the matching.
|
|
Arc | matching (const Node &node) const |
| Return the fractional matching arc (or edge) incident to the given node.
|
|
const MatchingMap & | matchingMap () const |
| Return a const reference to the matching map.
|
|
|
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.
|
|