MaxMatching
Declared in lemon/matching.h, in the group Matching Algorithms; the same class on the Doxygen site.
-
template< typename GR >
class MaxMatching Maximum cardinality matching in general graphs.
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(orD),ODD(orA) andMATCHED(orC) defining the Gallai-Edmonds decomposition of the graph. The nodes inEVEN/Dinduce a subgraph with factor-critical components, the nodes inODD/Aform the canonical barrier, and the nodes inMATCHED/Cinduce 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.
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().-
inline void init()
Set the initial matching to the empty matching.
This function sets the initial matching to the empty matching.
-
inline void greedyInit()
Find an initial matching in a greedy way.
This function finds an initial matching in a greedy way.
-
template< typename MatchingMap >
inline bool matchingInit( const MatchingMap & matching ) Initialize the matching from a map.
This function initializes the matching from a
boolvalued edge map. This map should have the property that there are no two incident edges withtruevalue, i.e. it really contains a matching.- Returns:
trueif the map contains a matching.
-
inline void startSparse( bool decomposition = true )
Start Edmonds’ algorithm.
This function runs the original Edmonds’ algorithm. If the
decompositionparameter is set to false, then the Gallai-Edmonds decomposition is not computed.- Pre:
init(), greedyInit() or matchingInit() must be called before using this function.
-
inline void startDense( bool decomposition = true )
Start Edmonds’ algorithm with a heuristic improvement for dense graphs.
This function runs Edmonds’ algorithm with a heuristic of postponing shrinks, therefore resulting in a faster algorithm for dense graphs. If the
decompositionparameter is set to false, then the Gallai-Edmonds decomposition is not computed.- Pre:
init(), greedyInit() or matchingInit() must be called before using this function.
-
inline void run( bool decomposition = true )
Run Edmonds’ algorithm.
This function runs Edmonds’ algorithm. An additional heuristic of postponing shrinks is used for relatively dense graphs (for which
m>=2*nholds). If thedecompositionparameter is set to false, then the Gallai-Edmonds decomposition is not computed. In some cases, this can speed up the algorithm significantly, especially when a maximum matching is computed in a dense graph with odd number of nodes.
Primal Solution
Functions to get the primal solution, i.e. the maximum matching.
-
inline int matchingSize() const
Return the size (cardinality) of the matching.
This function returns the size (cardinality) of the current matching. After run() it returns the size of the maximum matching in the graph.
-
inline bool matching( const Edge & edge ) const
Return
trueif the given edge is in the matching.This function returns
trueif the given edge is in the current matching.
-
inline Arc matching( const Node & n ) const
Return the matching arc (or edge) incident to the given node.
This function returns the matching arc (or edge) incident to the given node in the current matching or
INVALIDif the node is not covered by the matching.
-
inline const MatchingMap & matchingMap() const
Return a const reference to the matching map.
This function returns a const reference to a node map that stores the matching arc (or edge) incident to each node.
-
inline Node mate( const Node & n ) const
Return the mate of the given node.
This function returns the mate of the given node in the current matching or
INVALIDif the node is not covered by the matching.
Dual Solution
Functions to get the dual solution, i.e. the Gallai-Edmonds decomposition.
-
inline Status status( const Node & n ) const
Return the status of the given node in the Edmonds-Gallai decomposition.
This function returns the status of the given node in the Edmonds-Gallai decomposition.
-
inline const StatusMap & statusMap() const
Return a const reference to the status map, which stores the Edmonds-Gallai decomposition.
This function returns a const reference to a node map that stores the status of each node in the Edmonds-Gallai decomposition.
-
inline bool barrier( const Node & n ) const
Return
trueif the given node is in the barrier.This function returns
trueif the given node is in the barrier.
Public Types
-
enum Status
Status constants for Gallai-Edmonds decomposition.
These constants are used for indicating the Gallai-Edmonds decomposition of a graph. The nodes with status
EVEN(orD) induce a subgraph with factor-critical components, the nodes with statusODD(orA) form the canonical barrier, and the nodes with statusMATCHED(orC) induce a subgraph having a perfect matching.Values:
-
enumerator EVEN
= 1. (
Dis an alias forEVEN.)
-
enumerator D
-
enumerator MATCHED
= 0. (
Cis an alias forMATCHED.)
-
enumerator C
-
enumerator ODD
= -1. (
Ais an alias forODD.)
-
enumerator A
-
enumerator UNMATCHED
= -2.
-
enumerator EVEN