#include <lemon/max_matching.h>
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.
Graph | The undirected graph type the algorithm runs on. |
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 |
|
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 Definition at line 74 of file max_matching.h. |
|
Returns the mate of a Definition at line 127 of file max_matching.h. |
|
Reads a matching from a Definition at line 137 of file max_matching.h. |
|
Writes the stored matching to a Definition at line 149 of file max_matching.h. |
|
Reads a matching from a Definition at line 162 of file max_matching.h. |
|
Writes the stored matching to a Definition at line 177 of file max_matching.h. |
|
Reads a matching from an Definition at line 203 of file max_matching.h. |
|
Writes the matching stored to an Definition at line 222 of file max_matching.h. |
|
After calling any run methods of the class, it writes the Gallai-Edmonds canonical decomposition of the graph. Definition at line 249 of file max_matching.h. |