My Project
Loading...
Searching...
No Matches
MaxWeightedMatching< GR, WM > Class Template Reference

Detailed Description

template<typename GR, typename WM>
class lemon::MaxWeightedMatching< GR, WM >

This class provides an efficient implementation of Edmond's maximum weighted matching algorithm. The implementation is based on extensive use of priority queues and provides $O(nm\log n)$ time complexity.

The maximum weighted matching problem is to find a subset of the edges in an undirected graph with maximum overall weight for which each node has at most one incident edge. It can be formulated with the following linear program.

\[ \sum_{e \in \delta(u)}x_e \le 1 \quad \forall u\in V\]

\[ \sum_{e \in \gamma(B)}x_e \le \frac{\vert B \vert - 1}{2}
\quad \forall B\in\mathcal{O}\]

\[x_e \ge 0\quad \forall e\in E\]

\[\max \sum_{e\in E}x_ew_e\]

where $\delta(X)$ is the set of edges incident to a node in $X$, $\gamma(X)$ is the set of edges with both ends in $X$ and $\mathcal{O}$ is the set of odd cardinality subsets of the nodes.

The algorithm calculates an optimal matching and a proof of the optimality. The solution of the dual problem can be used to check the result of the algorithm. The dual linear problem is the following.

\[ y_u + y_v + \sum_{B \in \mathcal{O}, uv \in \gamma(B)}
z_B \ge w_{uv} \quad \forall uv\in E\]

\[y_u \ge 0 \quad \forall u \in V\]

\[z_B \ge 0 \quad \forall B \in \mathcal{O}\]

\[\min \sum_{u \in V}y_u + \sum_{B \in \mathcal{O}}
\frac{\vert B \vert - 1}{2}z_B\]

The algorithm can be executed with the run() function. After it the matching (the primal solution) and the dual solution can be obtained using the query functions and the BlossomIt nested class, which is able to iterate on the nodes of a blossom. If the value type is integer, then the dual solution is multiplied by 4.

Template Parameters
GRThe undirected graph type the algorithm runs on.
WMThe type edge weight map. The default type is GR::EdgeMap<int>.

#include <lemon/matching.h>

Classes

class  BlossomIt
 Iterator for obtaining the nodes of a blossom. More...
 

Public Types

typedef GR Graph
 The graph type of the algorithm.
 
typedef WM WeightMap
 The type of the edge weight map.
 
typedef WeightMap::Value Value
 The value type of the edge weights.
 
typedef Graph::template NodeMap< typename Graph::Arc > MatchingMap
 The type of the matching map.
 

Public Member Functions

 MaxWeightedMatching (const Graph &graph, const WeightMap &weight)
 Constructor.
 
Execution Control

The simplest way to execute the algorithm is to use the run() member function.

void init ()
 Initialize the algorithm.
 
void fractionalInit ()
 Initialize the algorithm with fractional matching.
 
void start ()
 Start the algorithm.
 
void run ()
 Run the algorithm.
 
Primal Solution

Functions to get the primal solution, i.e. the maximum weighted matching.
Either run() or start() function should be called before using them.

Value matchingWeight () const
 Return the weight of the 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 &node) 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 &node) const
 Return the mate of the given node.
 
Dual Solution

Functions to get the dual solution.
Either run() or start() function should be called before using them.

Value dualValue () const
 Return the value of the dual solution.
 
Value nodeValue (const Node &n) const
 Return the dual value (potential) of the given node.
 
int blossomNum () const
 Return the number of the blossoms in the basis.
 
int blossomSize (int k) const
 Return the number of the nodes in the given blossom.
 
Value blossomValue (int k) const
 Return the dual value (ptential) of the given blossom.
 

Static Public Attributes

static const int dualScale
 Scaling factor for dual solution.
 

Constructor & Destructor Documentation

◆ MaxWeightedMatching()

template<typename GR , typename WM >
MaxWeightedMatching ( const Graph & graph,
const WeightMap & weight )
inline

Constructor.

Member Function Documentation

◆ init()

template<typename GR , typename WM >
void init ( )
inline

This function initializes the algorithm.

◆ fractionalInit()

template<typename GR , typename WM >
void fractionalInit ( )
inline

This function initializes the algorithm with a fractional matching. This initialization is also called jumpstart heuristic.

◆ start()

template<typename GR , typename WM >
void start ( )
inline

This function starts the algorithm.

Precondition
init() or fractionalInit() must be called before using this function.

◆ run()

template<typename GR , typename WM >
void run ( )
inline

This method runs the MaxWeightedMatching algorithm.

Note
mwm.run() is just a shortcut of the following code.
mwm.fractionalInit();
mwm.start();

◆ matchingWeight()

template<typename GR , typename WM >
Value matchingWeight ( ) const
inline

This function returns the weight of the found matching.

Precondition
Either run() or start() must be called before using this function.

◆ matchingSize()

template<typename GR , typename WM >
int matchingSize ( ) const
inline

This function returns the size (cardinality) of the found matching.

Precondition
Either run() or start() must be called before using this function.

◆ matching() [1/2]

template<typename GR , typename WM >
bool matching ( const Edge & edge) const
inline

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

Precondition
Either run() or start() must be called before using this function.

◆ matching() [2/2]

template<typename GR , typename WM >
Arc matching ( const Node & node) const
inline

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

Precondition
Either run() or start() must be called before using this function.

◆ matchingMap()

template<typename GR , typename WM >
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 , typename WM >
Node mate ( const Node & node) const
inline

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

Precondition
Either run() or start() must be called before using this function.

◆ dualValue()

template<typename GR , typename WM >
Value dualValue ( ) const
inline

This function returns the value of the dual solution. It should be equal to the primal value scaled by dual scale.

Precondition
Either run() or start() must be called before using this function.

◆ nodeValue()

template<typename GR , typename WM >
Value nodeValue ( const Node & n) const
inline

This function returns the dual value (potential) of the given node.

Precondition
Either run() or start() must be called before using this function.

◆ blossomNum()

template<typename GR , typename WM >
int blossomNum ( ) const
inline

This function returns the number of the blossoms in the basis.

Precondition
Either run() or start() must be called before using this function.
See also
BlossomIt

◆ blossomSize()

template<typename GR , typename WM >
int blossomSize ( int k) const
inline

This function returns the number of the nodes in the given blossom.

Precondition
Either run() or start() must be called before using this function.
See also
BlossomIt

◆ blossomValue()

template<typename GR , typename WM >
Value blossomValue ( int k) const
inline

This function returns the dual value (ptential) of the given blossom.

Precondition
Either run() or start() must be called before using this function.

Member Data Documentation

◆ dualScale

template<typename GR , typename WM >
const int dualScale
static
Initial value:
=
std::numeric_limits<Value>::is_integer ? 4 : 1

Scaling factor for dual solution. It is equal to 4 or 1 according to the value type.