#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. |
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 |
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.
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
,map[v])==u holds, and now some edge joining g.oppositeNode
(vu
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.