![]() |
abLEMON 1.9.0-101-gccb8629
A maintained fork of LEMON
|
Maximum cardinality matching in bipartite graphs. More...
#include <lemon/bipartite_matching.h>
Public Types | |
| typedef BPGR | BpGraph |
| The bipartite graph type of the algorithm. | |
| typedef BpGraph::template NodeMap< typename BpGraph::Edge > | MatchingMap |
| The type of the matching map. | |
Public Member Functions | |
| HopcroftKarp (const BpGraph &graph) | |
| Constructor. | |
Execution Control | |
The simplest way to execute the algorithm is to use the | |
| void | init () |
| Set the initial matching to the empty matching. | |
| void | greedyInit () |
| Find an initial matching in a greedy way. | |
| void | start () |
| Augment the initial matching to a maximum one. | |
| void | run () |
| Run the algorithm. | |
Primal Solution | |
Functions to get the primal solution, i.e., the maximum matching. | |
| int | matchingSize () const |
| Return the size (cardinality) of the matching. | |
| bool | matching (const Edge &edge) const |
Return true if the given edge is in the matching. | |
| Edge | matching (const Node &n) const |
Return the matching edge incident to the given node, or INVALID if the node is not covered by the matching. | |
| const MatchingMap & | matchingMap () const |
| Return a const reference to the matching map. | |
| Node | mate (const Node &n) const |
Return the mate of the given node, or INVALID if it is not covered by the matching. | |
Dual Solution | |
Functions to get the dual solution, i.e., a minimum vertex cover. | |
| bool | cover (const Node &n) const |
Return true if the given node is in the minimum vertex cover, whose size equals that of the maximum matching. | |
This class implements the algorithm of Hopcroft and Karp, which finds a maximum cardinality matching of a bipartite graph in \(O((n+m)\sqrt{n})\) time, i.e., \(O(m\sqrt{n})\) on a graph without isolated nodes: in each phase, a breadth-first search from the unmatched red nodes finds the length of the shortest augmenting paths, and a depth-first search augments along a maximal set of disjoint ones of that length. It can be started from the empty matching or from a greedy one.
The dual solution is a minimum vertex cover, whose size equals that of the matching (König's theorem): with the nodes that an alternating path from an unmatched red node reaches, it is made of the red nodes not reached and the blue nodes reached [see cover()].
| BPGR | The bipartite graph type the algorithm runs on. |
|
inlineexplicit |
Constructor.
|
inline |
This function matches each red node to the first unmatched blue node among its neighbours, if any.
|
inline |
This function augments the initial matching, set by init() or greedyInit(), until it is maximum, and finds the vertex cover that proves it.
|
inline |
This function runs the algorithm from a greedy initial matching.
|
inline |
This function returns a const reference to a node map that stores the matching edge incident to each node.