HopcroftKarp
Declared in lemon/bipartite_matching.h, in the group Matching Algorithms; the same class on the Doxygen site.
-
template< typename BPGR >
class HopcroftKarp Maximum cardinality matching in bipartite graphs.
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()].
- Template Parameters:
BPGR – The bipartite graph type the algorithm runs on.
Execution Control
The simplest way to execute the algorithm is to use the
run()member function.
If you need better control on the execution, you have to call one of the functions
init() or greedyInit() first, then start().-
inline void init()
Set the initial matching to the empty matching.
-
inline void greedyInit()
Find an initial matching in a greedy way.
This function matches each red node to the first unmatched blue node among its neighbours, if any.
-
inline void start()
Augment the initial matching to a maximum one.
This function augments the initial matching, set by init() or greedyInit(), until it is maximum, and finds the vertex cover that proves it.
-
inline void run()
Run the algorithm.
This function runs the algorithm from a greedy initial matching.
Note
mm.run() is just a shortcut of the following code.
mm.greedyInit(); mm.start();
Primal Solution
Functions to get the primal solution, i.e., the maximum matching.
-
inline int matchingSize() const
Return the size (cardinality) of the matching.
-
inline bool matching( const Edge & edge ) const
Return
trueif the given edge is in the matching.
-
inline Edge matching( const Node & n ) const
Return the matching edge incident to the given node, or
INVALIDif the node is not covered by the matching.
-
inline const MatchingMap & matchingMap() const
Return a const reference to the matching map.
This function returns a const reference to a node map that stores the matching edge incident to each node.
-
inline Node mate( const Node & n ) const
Return the mate of the given node, or
INVALIDif it is not covered by the matching.
Dual Solution
Functions to get the dual solution, i.e., a minimum vertex cover.
-
inline bool cover( const Node & n ) const
Return
trueif the given node is in the minimum vertex cover, whose size equals that of the maximum matching.
Public Types