Public Types | Public Member Functions

MaxMatching< GR > Class Template Reference


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:
GRThe undirected graph type the algorithm runs on.

#include <lemon/matching.h>

List of all members.

Public Types

enum  Status { EVEN = 1 , MATCHED = 0 , ODD = -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)
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 MatchingMapmatchingMap () 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 StatusMapstatusMap () 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

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 ( const Graph graph) [inline]

Constructor.


Member Function Documentation

void init ( ) [inline]

This function sets the initial matching to the empty matching.

void greedyInit ( ) [inline]

This function finds an initial matching in a greedy way.

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.
void startSparse ( ) [inline]

This function runs the original Edmonds' algorithm.

Precondition:
init(), greedyInit() or matchingInit() must be called before using this function.
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.
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).

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.

bool matching ( const Edge &  edge) const [inline]

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

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.

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.

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 status ( const Node &  n) const [inline]

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

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.

bool barrier ( const Node &  n) const [inline]

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

 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines