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.
GR | The undirected graph type the algorithm runs on. |
#include <lemon/fractional_matching.h>
Classes | |
struct | SetElevator |
Named parameter for setting Elevator type More... | |
struct | SetMatchingMap |
Named parameter for setting MatchingMap type More... | |
struct | SetStandardElevator |
Named parameter for setting Elevator type with automatic allocation More... | |
Public Types | |
typedef TR | Traits |
The traits class of the algorithm. | |
typedef TR::Graph | Graph |
The type of the graph the algorithm runs on. | |
typedef TR::MatchingMap | MatchingMap |
The type of the matching map. | |
typedef TR::Elevator | Elevator |
The type of the elevator. | |
Public Member Functions | |
MaxFractionalMatching (const Graph &graph, bool allow_loops=true) | |
Constructor. More... | |
MaxFractionalMatching & | matchingMap (MatchingMap &map) |
Sets the matching map. More... | |
MaxFractionalMatching & | elevator (Elevator &elevator) |
Sets the elevator used by algorithm. More... | |
const Elevator & | elevator () const |
Returns a const reference to the elevator. More... | |
Execution control | |
void | init () |
Initializes the internal data structures. More... | |
void | start (bool postprocess=true) |
Starts the algorithm and computes a fractional matching. More... | |
bool | startPerfect (bool postprocess=true) |
Starts the algorithm and computes a perfect fractional matching. More... | |
void | run (bool postprocess=true) |
Runs the algorithm. More... | |
bool | runPerfect (bool postprocess=true) |
Runs the algorithm to find a perfect fractional matching. More... | |
Query Functions | |
int | matchingSize () const |
Return the number of covered nodes in the matching. More... | |
const MatchingMap & | matchingMap () const |
Returns a const reference to the matching map. More... | |
int | matching (const Edge &edge) const |
Return true if the given edge is in the matching. More... | |
Arc | matching (const Node &node) const |
Return the fractional matching arc (or edge) incident to the given node. More... | |
bool | barrier (const Node &node) const |
Returns true if the node is in the barrier. More... | |
Static Public Attributes | |
static const int | primalScale = 2 |
Scaling factor for primal solution. More... | |
|
inline |
Constructor.
|
inline |
|
inline |
|
inline |
|
inline |
Initializes the internal data structures and sets the initial matching.
|
inline |
The algorithm computes a maximum fractional matching.
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. |
|
inline |
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.
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. |
|
inline |
|
inline |
Just a shortcut for the next code:
|
inline |
|
inline |
|
inline |
This function returns true
if the given edge is in the found matching. The result is scaled by primal scale.
|
inline |
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.
|
inline |
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.
|
static |
Scaling factor for primal solution.