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 true if the given edge is in the matching.

inline 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.

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 INVALID if 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 true if the given node is in the minimum vertex cover, whose size equals that of the maximum matching.

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 Functions

inline explicit HopcroftKarp( const BpGraph & graph )

Constructor.