Loading...
Searching...
No Matches
MaxMatching< GR > Class Template Reference
Algorithms » Matching Algorithms

## Detailed Description

template<typename GR>
class lemon::MaxMatching< GR >

This class implements Edmonds' alternating forest matching algorithm for finding a maximum cardinality matching in a general undirected graph. It can be started from an arbitrary initial matching (the default is the empty one).

The dual solution of the problem is a map of the nodes to Status, having values `EVEN` (or `D`), `ODD` (or `A`) and `MATCHED` (or `C`) defining the Gallai-Edmonds decomposition of the graph. The nodes in `EVEN/D` induce a subgraph with factor-critical components, the nodes in `ODD/A` form the canonical barrier, and the nodes in `MATCHED/C` induce a graph having a perfect matching. The number of the factor-critical components minus the number of barrier nodes is a lower bound on the unmatched nodes, and the matching is optimal if and only if this bound is tight. This decomposition can be obtained using status() or statusMap() after running the algorithm.

Template Parameters

  GR | The undirected graph type the algorithm runs on.

`#include <lemon/matching.h>`

## Public Types

enum | Status { EVEN = 1 , D = 1 , MATCHED = 0 , C = 0 , ODD = -1 , A = -1 , UNMATCHED = -2 }
| Status constants for Gallai-Edmonds decomposition. More...
typedef GR | Graph
| The graph type of the algorithm.
typedef Graph::template NodeMap< typename Graph::Arc > | MatchingMap
| The type of the matching map.
typedef Graph::template NodeMap< Status > | StatusMap
| The type of the status map.

## Public Member Functions

| MaxMatching (const Graph &graph)
| Constructor.
Execution Control
The simplest way to execute the algorithm is to use the `run()` member function. If you need better control on the execution, you have to call one of the functions init(), greedyInit() or matchingInit() first, then you can start the algorithm with startSparse() or startDense().
void | init ()
| Set the initial matching to the empty matching.
void | greedyInit ()
| Find an initial matching in a greedy way.
template<typename MatchingMap>
bool | matchingInit (const MatchingMap &matching)
| Initialize the matching from a map.
void | startSparse ()
| Start Edmonds' algorithm.
void | startDense ()
| Start Edmonds' algorithm with a heuristic improvement for dense graphs.
void | run ()
| Run Edmonds' algorithm.
Primal Solution
Functions to get the primal solution, i.e. the maximum matching.
int | matchingSize () const
| Return the size (cardinality) of the matching.
bool | matching (const Edge &edge) const
| Return `true` if the given edge is in the matching.
Arc | matching (const Node &n) const
| Return the matching arc (or edge) incident to the given node.
const MatchingMap & | matchingMap () const
| Return a const reference to the matching map.
Node | mate (const Node &n) const
| Return the mate of the given node.
Dual Solution
Functions to get the dual solution, i.e. the Gallai-Edmonds decomposition.
Status | status (const Node &n) const
| Return the status of the given node in the Edmonds-Gallai decomposition.
const StatusMap & | statusMap () const
| Return a const reference to the status map, which stores the Edmonds-Gallai decomposition.
bool | barrier (const Node &n) const
| Return `true` if the given node is in the barrier.

## Member Enumeration Documentation

## Status

template<typename GR>

enum Status

These constants are used for indicating the Gallai-Edmonds decomposition of a graph. The nodes with status `EVEN` (or `D`) induce a subgraph with factor-critical components, the nodes with status `ODD` (or `A`) form the canonical barrier, and the nodes with status `MATCHED` (or `C`) induce a subgraph having a perfect matching.

Enumerator
EVEN | = 1. (`D` is an alias for `EVEN`.)
MATCHED | = 0. (`C` is an alias for `MATCHED`.)
ODD | = -1. (`A` is an alias for `ODD`.)
UNMATCHED | = -2.

## Constructor & Destructor Documentation

## MaxMatching()

template<typename GR>

MaxMatching | ( | const Graph & | graph | ) |

inline

Constructor.

## Member Function Documentation

## init()

template<typename GR>

void init | ( |  | ) |

inline

This function sets the initial matching to the empty matching.

## greedyInit()

template<typename GR>

void greedyInit | ( |  | ) |

inline

This function finds an initial matching in a greedy way.

## matchingInit()

template<typename GR>
template<typename MatchingMap>

bool matchingInit | ( | const MatchingMap & | matching | ) |

inline

This function initializes the matching from a `bool` valued edge map. This map should have the property that there are no two incident edges with `true` value, i.e. it really contains a matching.

Returns
  `true` if the map contains a matching.

## startSparse()

template<typename GR>

void startSparse | ( |  | ) |

inline

This function runs the original Edmonds' algorithm.

Precondition
  init(), greedyInit() or matchingInit() must be called before using this function.

## startDense()

template<typename GR>

void startDense | ( |  | ) |

inline

This function runs Edmonds' algorithm with a heuristic of postponing shrinks, therefore resulting in a faster algorithm for dense graphs.

Precondition
  init(), greedyInit() or matchingInit() must be called before using this function.

## run()

template<typename GR>

void run | ( |  | ) |

inline

This function runs Edmonds' algorithm. An additional heuristic of postponing shrinks is used for relatively dense graphs (for which m>=2*n holds).

## matchingSize()

template<typename GR>

int matchingSize | ( |  | ) | const

inline

This function returns the size (cardinality) of the current matching. After run() it returns the size of the maximum matching in the graph.

## matching() [1/2]

template<typename GR>

bool matching | ( | const Edge & | edge | ) | const

inline

This function returns `true` if the given edge is in the current matching.

## matching() [2/2]

template<typename GR>

Arc matching | ( | const Node & | n | ) | const

inline

This function returns the matching arc (or edge) incident to the given node in the current matching or `INVALID` if the node is not covered by the matching.

## matchingMap()

template<typename GR>

const MatchingMap & matchingMap | ( |  | ) | const

inline

This function returns a const reference to a node map that stores the matching arc (or edge) incident to each node.

## mate()

template<typename GR>

Node mate | ( | const Node & | n | ) | const

inline

This function returns the mate of the given node in the current matching or `INVALID` if the node is not covered by the matching.

## status()

template<typename GR>

Status status | ( | const Node & | n | ) | const

inline

This function returns the status of the given node in the Edmonds-Gallai decomposition.

## statusMap()

template<typename GR>

const StatusMap & statusMap | ( |  | ) | const

inline

This function returns a const reference to a node map that stores the status of each node in the Edmonds-Gallai decomposition.

## barrier()

template<typename GR>

bool barrier | ( | const Node & | n | ) | const

inline

This function returns `true` if the given node is in the barrier.