MaxWeightedBipartiteMatching< _BpUGraph, _WeightMap, _Traits > Class Template Reference
[Matching algorithms]

Detailed Description

template<typename _BpUGraph, typename _WeightMap, typename _Traits>
class lemon::MaxWeightedBipartiteMatching< _BpUGraph, _WeightMap, _Traits >

This class implements the bipartite Max Weighted Matching algorithm. It uses the successive shortest path algorithm to calculate the maximum weighted matching in the bipartite graph. The algorithm can be used also to calculate the maximum cardinality maximum weighted matching. The time complexity of the algorithm is $O(ne\log(n))$ with the default binary heap implementation but this can be improved to $O(n^2\log(n)+ne)$ if we use fibonacci heaps.

The algorithm also provides a potential function on the nodes which a dual solution of the matching algorithm and it can be used to proof the optimality of the given pimal solution. #include <lemon/bipartite_matching.h>

List of all members.

Classes

struct DefHeap

struct DefStandardHeap

Named parameter for setting heap and cross reference type with automatic allocation More...

class UninitializedParameter

Exception for uninitialized parameters. More...

Public Member Functions

MaxWeightedBipartiteMatching (const BpUGraph &_graph, const WeightMap &_weight)

Constructor.

~MaxWeightedBipartiteMatching ()

Destructor.

MaxWeightedBipartiteMatching & heap (Heap &hp, HeapCrossRef &cr)

Sets the heap and the cross reference used by algorithm.

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.

bool augment (bool decrease=false)

An augmenting phase of the weighted matching algorithm.

void start (bool maxCardinality=false)

Starts the algorithm.

void run (bool maxCardinality=false)

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 PotentialMap >

void potential (PotentialMap &pt) const

Gives back the potential in the NodeMap.

template<typename MatchingMap >

int quickMatching (MatchingMap &mm) const

Set true all matching uedge in the map.

template<typename 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 &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.

Value matchingValue () const

int matchingSize () const

Constructor & Destructor Documentation

MaxWeightedBipartiteMatching	(	const BpUGraph &	_graph,
		const WeightMap &	_weight
	)			`[inline]`

Constructor of the algorithm.

~MaxWeightedBipartiteMatching ( ) [inline]

Destructor of the algorithm.

Member Function Documentation

MaxWeightedBipartiteMatching& heap	(	Heap &	hp,
		HeapCrossRef &	cr
	)			`[inline]`

Sets the heap and the cross reference used by algorithm. If you don't use this function before calling run(), it will allocate one. The destuctor deallocates this automatically allocated map, of course.

Returns:: (*this)

void init ( ) [inline]

It initalizes the data structures and creates an empty matching.

bool augment ( bool decrease = false ) [inline]

It runs an augmenting phase of the weighted matching algorithm. This phase finds the best augmenting path and augments only on this paths.

The algorithm consists at most of $ O(n) $ phase and one phase is $O(n\log(n)+e)$ long with Fibonacci heap or $O((n+e)\log(n))$ long with binary heap.

Parameters:

decrease

If the given parameter true the matching value can be decreased in the augmenting phase. If we would like to calculate the maximum cardinality maximum weighted matching then we should let the algorithm to decrease the matching value in order to increase the number of the matching edges.

void start ( bool maxCardinality = false ) [inline]

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

Parameters:

maxCardinality

If the given value is true it will calculate the maximum cardinality maximum matching instead of the maximum matching.

void run ( bool maxCardinality = false ) [inline]

It just initalize the algorithm and then start it.

Parameters:

maxCardinality

If the given value is true it will calculate the maximum cardinality maximum matching instead of the maximum matching.

void potential ( PotentialMap & pt ) const [inline]

Gives back the potential in the NodeMap. The matching is optimal with the current number of edges if $\pi(a) + \pi(b) - w(ab) = 0$ for each matching edges and $\pi(a) + \pi(b) - w(ab) \ge 0$ for each edges.

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

Value matchingValue ( ) const [inline]

Gives back the sum of weights of the matching edges.

int matchingSize ( ) const [inline]

Gives back the number of the matching edges.


Classes
struct	DefHeap
struct	DefStandardHeap
	Named parameter for setting heap and cross reference type with automatic allocation More...
class	UninitializedParameter
	Exception for uninitialized parameters. More...
Public Member Functions
	MaxWeightedBipartiteMatching (const BpUGraph &_graph, const WeightMap &_weight)
	Constructor.
	~MaxWeightedBipartiteMatching ()
	Destructor.
MaxWeightedBipartiteMatching &	heap (Heap &hp, HeapCrossRef &cr)
	Sets the heap and the cross reference used by algorithm.
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.
bool	augment (bool decrease=false)
	An augmenting phase of the weighted matching algorithm.
void	start (bool maxCardinality=false)
	Starts the algorithm.
void	run (bool maxCardinality=false)
	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 PotentialMap >
void	potential (PotentialMap &pt) const
	Gives back the potential in the NodeMap.
template<typename MatchingMap >
int	quickMatching (MatchingMap &mm) const
	Set true all matching uedge in the map.
template<typename 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 &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.
Value	matchingValue () const
int	matchingSize () const

MaxWeightedBipartiteMatching< _BpUGraph, _WeightMap, _Traits > Class Template Reference [Matching algorithms]

Detailed Description

template<typename _BpUGraph, typename _WeightMap, typename _Traits> class lemon::MaxWeightedBipartiteMatching< _BpUGraph, _WeightMap, _Traits >

Classes

Public Member Functions

Constructor & Destructor Documentation

Member Function Documentation

MaxWeightedBipartiteMatching< _BpUGraph, _WeightMap, _Traits > Class Template Reference
[Matching algorithms]

template<typename _BpUGraph, typename _WeightMap, typename _Traits>
class lemon::MaxWeightedBipartiteMatching< _BpUGraph, _WeightMap, _Traits >