PrBipartiteMatching< Graph > Class Template Reference
[Matching algorithms]

---

Detailed Description

template<class Graph>
class lemon::PrBipartiteMatching< Graph >

Bipartite Max Cardinality Matching algorithm. This class uses the push-relabel principle which in several cases has better runtime performance than the augmenting path solutions.

Author:

Alpar Juttner

#include <lemon/pr_bipartite_matching.h>

List of all members.

Public Member Functions
	PrBipartiteMatching (const Graph &g)
	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() and then one variant of the start() member.
void	init ()
	Initialize the data structures.
void	start ()
	Start the main phase of the algorithm.
bool	startPerfect ()
	Start the algorithm to find a perfect matching.
void	run ()
	Runs the algorithm.
bool	runPerfect ()
	Runs the algorithm to find a perfect matching.
bool	checkedRunPerfect ()
	Runs the algorithm to find a perfect matching.
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 MatchingMap >
int	quickMatching (MatchingMap &mm) const
	Set true all matching uedge in the map.
template<class MatchingMap >
int	matching (MatchingMap &mm) const
	Set true all matching uedge in the map and the others to false.
template<class MatchingMap >
int	aMatching (MatchingMap &mm) const
	Gives back the matching in an ANodeMap.
template<class MatchingMap >
int	bMatching (MatchingMap &mm) const
	Gives back the matching in a BNodeMap.
bool	matchingEdge (const UEdge &e) const
	Returns true if the given uedge is in the matching.
UEdge	matchingEdge (const Node &n) const
	Returns the matching edge from the node.
int	matchingSize () const
template<class BarrierMap >
void	aBarrier (BarrierMap &bar) const
	Gives back a barrier on the A-nodes.
template<class BarrierMap >
void	bBarrier (BarrierMap &bar) const
	Gives back a barrier on the B-nodes.
template<class CoverMap >
int	coverSet (CoverMap &covering) const
	Returns a minimum covering of the nodes.

---

Constructor & Destructor Documentation

PrBipartiteMatching

(

const Graph &

g

)

[inline]

Constructor

---

Member Function Documentation

void init

(

)

[inline]

This function constructs a prematching first, which is a regular matching on the A-side of the graph, but on the B-side each node could cover more matching edges. After that, the B-nodes which multiple matched, will be pushed into the lowest level of the Elevator. The remaning B-nodes will be pushed to the consequent levels respect to a Bfs on following graph: the nodes are the B-nodes of the original bipartite graph and two nodes are adjacent if a node can pass over a matching edge to an other node. The source of the Bfs are the lowest level nodes. Last, the reached B-nodes without covered matching edge becomes active.

void start

(

)

[inline]

This algorithm calculates the maximum matching with the push-relabel principle. This function should be called just after the init() function which already set the initial prematching, the level function on the B-nodes and the active, ie. unmatched B-nodes.

The algorithm always takes highest active B-node, and it try to find a B-node which is eligible to pass over one of it's matching edge. This condition holds when the B-node is one level lower, and the opposite node of it's matching edge is adjacent to the highest active node. In this case the current node steals the matching edge and becomes inactive. If there is not eligible node then the highest active node should be lift to the next proper level.

The nodes should not lift higher than the number of the B-nodes, if a node reach this level it remains unmatched. If during the execution one level becomes empty the nodes above it can be deactivated and lift to the highest level.

bool startPerfect

(

)

[inline]

This function is close to identical to the simple start() member function but it calculates just perfect matching. However, the perfect property is only checked on the B-side of the graph

The main difference between the two function is the handling of the empty levels. The simple start() function let the nodes above the empty levels unmatched while this variant if it find an empty level immediately terminates and gives back false return value.

void run

(

)

[inline]

Just a shortcut for the next code:

        init();
        start();

bool runPerfect

(

)

[inline]

Just a shortcut for the next code:

        init();
        startPerfect();

Note:

If the two nodesets of the graph have different size then this algorithm checks the perfect property on the B-side.

bool checkedRunPerfect

(

)

[inline]

Just a shortcut for the next code:

        init();
        startPerfect();

Note:

It checks that the size of the two nodesets are equal.

int quickMatching

(

MatchingMap &

mm

)

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 &

mm

)

const [inline]

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

Returns:

The number of the matching edges.

int aMatching

(

MatchingMap &

mm

)

const [inline]

Gives back the matching in an ANodeMap. The parameter should be a write ANodeMap of UEdge values.

Returns:

The number of the matching edges.

int bMatching

(

MatchingMap &

mm

)

const [inline]

Gives back the matching in a BNodeMap. The parameter should be a write BNodeMap of UEdge values.

Returns:

The number of the matching edges.

bool matchingEdge

(

const UEdge &

e

)

const [inline]

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

UEdge matchingEdge

(

const Node &

n

)

const [inline]

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

Note:

If the parameter node is a B-node then the running time is propotional to the degree of the node.

int matchingSize

(

)

const [inline]

Gives back the number of the matching edges.

void aBarrier

(

BarrierMap &

bar

)

const [inline]

The barrier is s subset of the nodes on the same side of the graph. If we tried to find a perfect matching and it failed then the barrier size will be greater than its neighbours. If the maximum matching searched then the barrier size minus its neighbours will be exactly the unmatched nodes on the A-side.

Return values:

bar

A WriteMap on the ANodes with bool value.

void bBarrier

(

BarrierMap &

bar

)

const [inline]

The barrier is s subset of the nodes on the same side of the graph. If we tried to find a perfect matching and it failed then the barrier size will be greater than its neighbours. If the maximum matching searched then the barrier size minus its neighbours will be exactly the unmatched nodes on the B-side.

Return values:

bar

A WriteMap on the BNodes with bool value.

int coverSet

(

CoverMap &

covering

)

const [inline]

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

Parameters:

covering

NodeMap of bool values, the nodes of the cover set will set true while the others false.

Returns:

The size of the cover set.

Note:

This function can be called just after the algorithm have already found a matching.