abLEMON 1.9.0-101-gccb8629
A maintained fork of LEMON
Loading...
Searching...
No Matches
HopcroftKarp< BPGR > Class Template Reference

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 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().

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.

Detailed Description

template< typename BPGR >
class lemon::HopcroftKarp< BPGR >

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
BPGRThe bipartite graph type the algorithm runs on.

Constructor & Destructor Documentation

◆ HopcroftKarp()

template< typename BPGR >
HopcroftKarp ( const BpGraph & graph)
inlineexplicit

Constructor.

Member Function Documentation

◆ greedyInit()

template< typename BPGR >
void greedyInit ( )
inline

This function matches each red node to the first unmatched blue node among its neighbours, if any.

◆ start()

template< typename BPGR >
void start ( )
inline

This function augments the initial matching, set by init() or greedyInit(), until it is maximum, and finds the vertex cover that proves it.

◆ run()

template< typename BPGR >
void run ( )
inline

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();

◆ matchingMap()

template< typename BPGR >
const MatchingMap & matchingMap ( ) const
inline

This function returns a const reference to a node map that stores the matching edge incident to each node.