Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

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

Definition at line 56 of file max_matching.h.

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)
 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 map of Nodes.
template<typename NMapN>
void writeNMapNode (NMapN &map) const
 Writes the stored matching to a Node map of Nodes.
template<typename NMapE>
void readNMapEdge (NMapE &map)
 Reads a matching from a Node map of Edges.
template<typename NMapE>
void writeNMapEdge (NMapE &map) const
 Writes the matching stored to a Node map of Edges.
template<typename EMapB>
void readEMapBool (EMapB &map)
 Reads a matching from an Edge map of bools.
template<typename EMapB>
void writeEMapBool (EMapB &map) const
 Writes the matching stored to an Edge map of bools.
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.

Definition at line 74 of file max_matching.h.


Member Function Documentation

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.

Definition at line 127 of file max_matching.h.

void readNMapNode NMapN &  map  )  [inline]
 

Reads a matching from a Node map of Nodes. 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.

Definition at line 137 of file max_matching.h.

void writeNMapNode NMapN &  map  )  const [inline]
 

Writes the stored matching to a Node map of Nodes. 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.

Definition at line 149 of file max_matching.h.

void readNMapEdge NMapE &  map  )  [inline]
 

Reads a matching from a Node map of incident Edges. This map must have the property that if G.target(map[u])==v then G.target(map[v])==u must hold, and now this edge is an edge of the matching.

Definition at line 162 of file max_matching.h.

void writeNMapEdge NMapE &  map  )  const [inline]
 

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

Definition at line 177 of file max_matching.h.

void readEMapBool EMapB &  map  )  [inline]
 

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

Definition at line 203 of file max_matching.h.

void writeEMapBool EMapB &  map  )  const [inline]
 

Writes the matching stored to an Edge map of bools. This map will have the property that there are no two adjacent edges e, f with map[e]==map[f]==true. The edges e with map[e]==true form the matching.

Definition at line 222 of file max_matching.h.

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.

Definition at line 249 of file max_matching.h.


The documentation for this class was generated from the following file:
Generated on Mon Feb 21 15:02:35 2005 for LEMON by  doxygen 1.4.1