template<typename GR, typename TR>
class lemon::MaxFractionalMatching< GR, TR >
This class provides an implementation of fractional matching algorithm based on push-relabel principle.
The maximum cardinality fractional matching is a relaxation of the maximum cardinality 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 can be represented as 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 barrier. The number of adjacents of any node set minus the size of node set is a lower bound on the uncovered nodes in the graph. For maximum matching a barrier is computed which maximizes this difference.
The algorithm can be executed with the run() function. After it the matching (the primal solution) and the barrier (the dual solution) can be obtained using the query functions.
The simplest way to execute the algorithm is to use one of the member functions called run().
If you need more control on the execution, first you must call init() and then one variant of the start() member.
Sets the matching map. If you don't use this function before calling run() or init(), an instance will be allocated automatically. The destructor deallocates this automatically allocated map, of course.
Sets the elevator used by algorithm. If you don't use this function before calling run() or init(), an instance will be allocated automatically. The destructor deallocates this automatically allocated elevator, of course.
The algorithm computes a maximum fractional matching.
Parameters
postprocess
The algorithm computes first a matching which is a union of a matching with one value edges, cycles with half value edges and even length paths with half value edges. If the parameter is true, then after the push-relabel algorithm it postprocesses the matching to contain only matching edges and half value odd cycles.
The algorithm computes a perfect fractional matching. If it does not exists, then the algorithm returns false and the matching is undefined and the barrier.
Parameters
postprocess
The algorithm computes first a matching which is a union of a matching with one value edges, cycles with half value edges and even length paths with half value edges. If the parameter is true, then after the push-relabel algorithm it postprocesses the matching to contain only matching edges and half value odd cycles.
This function returns one of the fractional matching arc (or edge) incident to the given node in the found matching or INVALID if 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.
Precondition
Either run() or start() must be called before using this function.
The barrier is a subset of the nodes. If the nodes in the barrier have less adjacent nodes than the size of the barrier, then at least as much nodes cannot be covered as the difference of the two subsets.