MaxBipartiteMatching Class Template Reference
[Matching algorithms in graphs and bipartite graphs]

#include <lemon/bipartite_matching.h>

List of all members.


Detailed Description

template<typename BpUGraph>
class lemon::MaxBipartiteMatching< BpUGraph >

Bipartite Max Cardinality Matching algorithm. This class implements the Hopcroft-Karp algorithm which has $ O(e\sqrt{n}) $ time complexity.


Public Member Functions

 MaxBipartiteMatching (const BpUGraph &_graph)
 Constructor.
Execution control
The simplest way to execute the algorithm is to use one of the member functions called run().
If you need more control on the execution, first you must call init() or one alternative for it. Finally start() will perform the matching computation or with step-by-step execution you can augment the solution.

void init ()
 Initalize the data structures.
void greedyInit ()
 Initalize the data structures.
template<typename MatchingMap>
void matchingInit (const MatchingMap &matching)
 Initalize the data structures with an initial matching.
template<typename MatchingMap>
void checkedMatchingInit (const MatchingMap &matching)
 Initalize the data structures with an initial matching.
bool augment ()
 An augmenting phase of the Hopcroft-Karp algorithm.
bool simpleAugment ()
 An augmenting phase of the Ford-Fulkerson algorithm.
void start ()
 Starts the algorithm.
void run ()
 Runs the algorithm.
Query Functions
The result of the Matching algorithm can be obtained using these functions.
Before the use of these functions, either run() or start() must be called.

template<typename CoverMap>
int coverSet (CoverMap &covering) const
 Returns an minimum covering of the nodes.
template<typename MatchingMap>
int quickMatching (MatchingMap &matching) const
 Set true all matching uedge in the map.
template<typename MatchingMap>
int matching (MatchingMap &matching) const
 Set true all matching uedge in the map and the others to false.
bool matchingEdge (const UEdge &edge) const
 Return true if the given uedge is in the matching.
UEdge matchingEdge (const Node &node) const
 Returns the matching edge from the node.
int matchingSize () const
 Gives back the number of the matching edges.


Constructor & Destructor Documentation

MaxBipartiteMatching ( const BpUGraph &  _graph  )  [inline]

Constructor of the algorithm.


Member Function Documentation

void init (  )  [inline]

It initalizes the data structures and creates an empty matching.

void greedyInit (  )  [inline]

It initalizes the data structures and creates a greedy matching. From this matching sometimes it is faster to get the matching than from the initial empty matching.

void matchingInit ( const MatchingMap &  matching  )  [inline]

It initalizes the data structures with an initial matching.

void checkedMatchingInit ( const MatchingMap &  matching  )  [inline]

It initalizes the data structures with an initial matching.

Returns:
True when the given map contains really a matching.

bool augment (  )  [inline]

It runs an augmenting phase of the Hopcroft-Karp algorithm. The phase finds maximum count of edge disjoint augmenting paths and augments on these paths. The algorithm consists at most of $ O(\sqrt{n}) $ phase and one phase is $ O(e) $ long.

bool simpleAugment (  )  [inline]

It runs an augmenting phase of the Ford-Fulkerson algorithm. The phase finds only one augmenting path and augments only on this paths. The algorithm consists at most of $ O(n) $ simple phase and one phase is at most $ O(e) $ long.

void start (  )  [inline]

Starts the algorithm. It runs augmenting phases until the optimal solution reached.

void run (  )  [inline]

It just initalize the algorithm and then start it.

int coverSet ( CoverMap &  covering  )  const [inline]

The minimum covering set problem is the dual solution of the maximum bipartite matching. It provides an solution for this problem what is proof of the optimality of the matching.

Returns:
The size of the cover set.

int quickMatching ( MatchingMap &  matching  )  const [inline]

Set true all matching uedge in the map. It does not change the value mapped to the other uedges.

Returns:
The number of the matching edges.

int matching ( MatchingMap &  matching  )  const [inline]

Set true all matching uedge in the map and the others to false.

Returns:
The number of the matching edges.

bool matchingEdge ( const UEdge &  edge  )  const [inline]

It returns true if the given uedge is in the matching.

UEdge matchingEdge ( const Node &  node  )  const [inline]

Returns the matching edge from the node. If there is not such edge it gives back INVALID.

int matchingSize (  )  const [inline]

Gives back the number of the matching edges.


The documentation for this class was generated from the following file:
Generated on Tue Oct 31 09:49:50 2006 for LEMON by  doxygen 1.5.1