MaxMatching Class Template Reference
[Graph Algorithms]

#include <lemon/max_matching.h>

List of all members.


Detailed Description

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

This class provides Edmonds' alternating forest matching algorithm. The starting matching (if any) can be passed to the algorithm using read-in functions readNMapNode, readNMapEdge or readEMapBool depending on the container. The resulting maximum matching can be attained by write-out functions writeNMapNode, writeNMapEdge or writeEMapBool depending on the preferred container.

The dual side of a matching is a map of the nodes to MaxMatching::pos_enum, having values D, A and C showing the Gallai-Edmonds decomposition of the graph. The nodes in D induce a graph with factor-critical components, the nodes in A form the barrier, and the nodes in C induce a graph having a perfect matching. This decomposition can be attained by calling writePos after running the algorithm.

Parameters:
Graph The undirected graph type the algorithm runs on.
Author:
Jacint Szabo


Public Types

enum  pos_enum
 Indicates the Gallai-Edmonds decomposition of the graph. More...

Public Member Functions

void run ()
 Runs Edmonds' algorithm.
void runEdmonds (int heur=1)
 Runs Edmonds' algorithm.
void greedyMatching ()
 Finds a greedy matching starting from the actual matching.
int size () const
 Returns the size of the actual matching stored.
void resetMatching ()
 Resets the actual matching to the empty matching.
Node mate (Node &node) const
 Returns the mate of a node in the actual matching.
template<typename NMapN>
void readNMapNode (NMapN &map)
 Reads a matching from a Node valued Node map.
template<typename NMapN>
void writeNMapNode (NMapN &map) const
 Writes the stored matching to a Node valued Node map.
template<typename NMapE>
void readNMapEdge (NMapE &map)
 Reads a matching from an UEdge valued Node map.
template<typename NMapE>
void writeNMapEdge (NMapE &map) const
 Writes the matching stored to an UEdge valued Node map.
template<typename EMapB>
void readEMapBool (EMapB &map)
 Reads a matching from a bool valued Edge map.
template<typename EMapB>
void writeEMapBool (EMapB &map) const
 Writes the matching stored to a bool valued Edge map.
template<typename NMapEnum>
void writePos (NMapEnum &map) const


Member Enumeration Documentation

enum pos_enum
 

Indicates the Gallai-Edmonds decomposition of the graph, which shows an upper bound on the size of a maximum matching. The nodes with pos_enum D induce a graph with factor-critical components, the nodes in A form the canonical barrier, and the nodes in C induce a graph having a perfect matching.


Member Function Documentation

void run  )  [inline]
 

Runs Edmonds' algorithm for sparse graphs (number of edges < 2*number of nodes), and a heuristical Edmonds' algorithm with a heuristic of postponing shrinks for dense graphs.

void runEdmonds int  heur = 1  )  [inline]
 

If heur=0 it runs Edmonds' algorithm. If heur=1 it runs Edmonds' algorithm with a heuristic of postponing shrinks, giving a faster algorithm for dense graphs.

void greedyMatching  )  [inline]
 

Starting form the actual matching stored, it finds a maximal greedy matching.

int size  )  const [inline]
 

Returns the size of the actual matching stored. After run() it returns the size of a maximum matching in the graph.

void resetMatching  )  [inline]
 

Resets the actual matching to the empty matching.

Node mate Node &  node  )  const [inline]
 

Returns the mate of a node in the actual matching. Returns INVALID if the node is not covered by the actual matching.

void readNMapNode NMapN &  map  )  [inline]
 

Reads a matching from a Node valued Node map. This map must be symmetric, i.e. if map[u]==v then map[v]==u must hold, and uv will be an edge of the matching.

void writeNMapNode NMapN &  map  )  const [inline]
 

Writes the stored matching to a Node valued Node map. The resulting map will be symmetric, i.e. if map[u]==v then map[v]==u will hold, and now uv is an edge of the matching.

void readNMapEdge NMapE &  map  )  [inline]
 

Reads a matching from an UEdge valued Node map. map[v] must be an UEdge incident to v. This map must have the property that if g.oppositeNode(u,map[u])==v then g.oppositeNode(v,map[v])==u holds, and now some edge joining u to v will be an edge of the matching.

void writeNMapEdge NMapE &  map  )  const [inline]
 

Writes the stored matching to an UEdge valued Node map. map[v] will be an UEdge incident to v. This map will have the property that if g.oppositeNode(u,map[u]) == v then map[u]==map[v] holds, and now this edge is an edge of the matching.

void readEMapBool EMapB &  map  )  [inline]
 

Reads a matching from a bool valued Edge map. This map must have the property that there are no two incident edges e, f with map[e]==map[f]==true. The edges e with map[e]==true form the matching.

void writeEMapBool EMapB &  map  )  const [inline]
 

Writes the matching stored to a bool valued Edge map. This map will have the property that there are no two incident edges e, f with map[e]==map[f]==true. The edges e with map[e]==true form the matching.

void writePos NMapEnum &  map  )  const [inline]
 

After calling any run methods of the class, it writes the Gallai-Edmonds canonical decomposition of the graph. map must be a node map of pos_enum 's.


The documentation for this class was generated from the following file:
Generated on Fri Feb 3 18:42:26 2006 for LEMON by  doxygen 1.4.6