The dual side of a matching is a map of the nodes to MaxMatching::DecompType, 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 decomposition() after running the algorithm.
| Graph | The undirected graph type the algorithm runs on. |
#include <lemon/max_matching.h>
Public Types | |
| enum | DecompType |
| Indicates the Gallai-Edmonds decomposition of the graph. More... | |
Public Member Functions | |
| void | init () |
| void | greedyInit () |
| Finds a greedy matching for initial matching. | |
| template<typename MateMap > | |
| void | mateMapInit (MateMap &map) |
| Initialize the matching from each nodes' mate. | |
| template<typename MatchingMap > | |
| void | matchingMapInit (MatchingMap &map) |
| Initialize the matching from a node map with the incident matching edges. | |
| template<typename MatchingMap > | |
| void | matchingInit (MatchingMap &map) |
| Initialize the matching from the map containing the undirected matching edges. | |
| void | run () |
| Runs Edmonds' algorithm. | |
| void | startSparse () |
| Starts Edmonds' algorithm. | |
| void | startDense () |
| Starts Edmonds' algorithm. | |
| int | size () const |
| Returns the size of the actual matching stored. | |
| Node | mate (const Node &node) const |
| Returns the mate of a node in the actual matching. | |
| UEdge | matchingEdge (const Node &node) const |
| Returns the matching edge incident to the given node. | |
| DecompType | decomposition (const Node &n) |
| bool | barrier (const Node &n) |
| template<typename MateMap > | |
| void | mateMap (MateMap &map) const |
Gives back the matching in a Node of mates. | |
| template<typename MatchingMap > | |
| void | matchingMap (MatchingMap &map) const |
Gives back the matching in an UEdge valued Node map. | |
| template<typename MatchingMap > | |
| void | matching (MatchingMap &map) const |
Gives back the matching in a bool valued UEdge map. | |
| template<typename DecompositionMap > | |
| void | decomposition (DecompositionMap &map) const |
| Returns the canonical decomposition of the graph after running the algorithm. | |
| template<typename BarrierMap > | |
| void | barrier (BarrierMap &barrier) |
| Returns a barrier on the nodes. | |
| enum DecompType |
Indicates the Gallai-Edmonds decomposition of the graph, which shows an upper bound on the size of a maximum matching. The nodes with DecompType 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 init | ( | ) | [inline] |
Sets the actual matching to the empty matching.
| void greedyInit | ( | ) | [inline] |
For initial matchig it finds a maximal greedy matching.
| void mateMapInit | ( | MateMap & | map | ) | [inline] |
Initialize the 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 initial matching.
| void matchingMapInit | ( | MatchingMap & | map | ) | [inline] |
Initialize the 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(vu to v will be an edge of the matching.
| void matchingInit | ( | MatchingMap & | map | ) | [inline] |
Initialize the matching from a bool valued UEdge 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 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 startSparse | ( | ) | [inline] |
If runs the original Edmonds' algorithm.
| void startDense | ( | ) | [inline] |
It runs Edmonds' algorithm with a heuristic of postponing shrinks, giving a faster algorithm for dense graphs.
| 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.
| Node mate | ( | const 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.
| UEdge matchingEdge | ( | const Node & | node | ) | const [inline] |
Returns the matching edge of a node in the actual matching. Returns INVALID if the node is not covered by the actual matching.
| DecompType decomposition | ( | const Node & | n | ) | [inline] |
Returns the class of the node in the Edmonds-Gallai decomposition.
| bool barrier | ( | const Node & | n | ) | [inline] |
Returns true when the node is in the barrier.
| void mateMap | ( | MateMap & | 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 matchingMap | ( | MatchingMap & | 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 matching | ( | MatchingMap & | 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 decomposition | ( | DecompositionMap & | 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 DecompType 's.
| void barrier | ( | BarrierMap & | barrier | ) | [inline] |
After calling any run methods of the class, it writes a canonical barrier on the nodes. The odd component number of the remaining graph minus the barrier size is a lower bound for the uncovered nodes in the graph. The map must be a node map of bools.
1.5.9