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 primal solution is multiplied by 2.
- Template Parameters
-
GR | The undirected graph type the algorithm runs on. |
|
| MaxFractionalMatching (const Graph &graph, bool allow_loops=true) |
|
MaxFractionalMatching & | matchingMap (MatchingMap &map) |
| Sets the matching map.
|
|
MaxFractionalMatching & | elevator (Elevator &elevator) |
| Sets the elevator used by algorithm.
|
|
const Elevator & | elevator () const |
| Returns a const reference to the elevator.
|
|
|
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.
|
void | init () |
| Initializes the internal data structures.
|
|
void | start (bool postprocess=true) |
| Starts the algorithm and computes a fractional matching.
|
|
bool | startPerfect (bool postprocess=true) |
| Starts the algorithm and computes a perfect fractional matching.
|
|
void | run (bool postprocess=true) |
| Runs the algorithm.
|
|
bool | runPerfect (bool postprocess=true) |
| Runs the algorithm to find a perfect fractional matching.
|
|
|
The result of the Matching algorithm can be obtained using these functions.
Before the use of these functions, either run() or start() must be called.
|
int | matchingSize () const |
| Return the number of covered nodes in the matching.
|
|
const MatchingMap & | matchingMap () const |
| Returns a const reference to the matching map.
|
|
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.
|
|
bool | barrier (const Node &node) const |
| Returns true if the node is in the barrier.
|
|