Matching algorithms
[Algorithms]

Detailed Description

This group contains algorithm objects and functions to calculate matchings in graphs and bipartite graphs. The general matching problem is finding a subset of the edges which does not shares common endpoints.

There are several different algorithms for calculate matchings in graphs. The matching problems in bipartite graphs are generally easier than in general graphs. The goal of the matching optimization can be the finding maximum cardinality, maximum weight or minimum cost matching. The search can be constrained to find perfect or maximum cardinality matching.

Lemon contains the next algorithms:

MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm for calculate maximum cardinality matching in bipartite graphs
PrBipartiteMatching Push-Relabel algorithm for calculate maximum cardinality matching in bipartite graphs
MaxWeightedBipartiteMatching Successive shortest path algorithm for calculate maximum weighted matching and maximum weighted bipartite matching in bipartite graph
MinCostMaxBipartiteMatching Successive shortest path algorithm for calculate minimum cost maximum matching in bipartite graph
MaxMatching Edmond's blossom shrinking algorithm for calculate maximum cardinality matching in general graph
MaxWeightedMatching Edmond's blossom shrinking algorithm for calculate maximum weighted matching in general graph
MaxWeightedPerfectMatching Edmond's blossom shrinking algorithm for calculate maximum weighted perfect matching in general graph


Classes
class	MaxBipartiteMatching< BpUGraph >
	Bipartite Max Cardinality Matching algorithm. More...
class	MaxWeightedBipartiteMatching< _BpUGraph, _WeightMap, _Traits >
	Bipartite Max Weighted Matching algorithm. More...
class	MinCostMaxBipartiteMatching< _BpUGraph, _CostMap, _Traits >
	Bipartite Min Cost Matching algorithm. More...
class	MaxMatching< Graph >
	Edmonds' alternating forest maximum matching algorithm. More...
class	MaxWeightedMatching< _UGraph, _WeightMap >
	Weighted matching in general undirected graphs. More...
class	MaxWeightedPerfectMatching< _UGraph, _WeightMap >
	Weighted perfect matching in general undirected graphs. More...
class	PrBipartiteMatching< Graph >
	Max cardinality matching algorithm based on push-relabel principle. More...
Files
file	bipartite_matching.h
	Maximum matching algorithms in bipartite graphs.
file	max_matching.h
	Maximum matching algorithms in undirected graph.
file	pr_bipartite_matching.h
	Push-prelabel maximum matching algorithms in bipartite graphs.
Functions
template<typename BpUGraph >
int	maxBipartiteMatching (const BpUGraph &graph)
	Maximum cardinality bipartite matching.
template<typename BpUGraph , typename MatchingMap >
int	maxBipartiteMatching (const BpUGraph &graph, MatchingMap &matching)
	Maximum cardinality bipartite matching.
template<typename BpUGraph , typename MatchingMap , typename BarrierMap >
int	maxBipartiteMatching (const BpUGraph &graph, MatchingMap &matching, BarrierMap &barrier)
	Maximum cardinality bipartite matching.
template<typename BpUGraph , typename WeightMap , typename MatchingMap >
WeightMap::Value	maxWeightedBipartiteMatching (const BpUGraph &graph, const WeightMap &weight, MatchingMap &matching)
	Maximum weighted bipartite matching.
template<typename BpUGraph , typename WeightMap , typename MatchingMap >
WeightMap::Value	maxWeightedMaxBipartiteMatching (const BpUGraph &graph, const WeightMap &weight, MatchingMap &matching)
	Maximum weighted maximum cardinality bipartite matching.
template<typename BpUGraph , typename CostMap , typename MatchingMap >
CostMap::Value	minCostMaxBipartiteMatching (const BpUGraph &graph, const CostMap &cost, MatchingMap &matching)
	Minimum cost maximum cardinality bipartite matching.
template<class Graph >
int	prBipartiteMatching (const Graph &g)
	Maximum cardinality of the matchings in a bipartite graph.
template<class Graph , class MT >
int	prBipartiteMatching (const Graph &g, MT &matching)
	Maximum cardinality matching in a bipartite graph.
template<class Graph , class MT , class GT >
int	prBipartiteMatching (const Graph &g, MT &matching, GT &barrier)
	Maximum cardinality matching in a bipartite graph.
template<class Graph >
bool	prPerfectBipartiteMatching (const Graph &g)
	Perfect matching in a bipartite graph.
template<class Graph , class MT >
bool	prPerfectBipartiteMatching (const Graph &g, MT &matching)
	Perfect matching in a bipartite graph.
template<class Graph , class MT , class GT >
bool	prPerfectBipartiteMatching (const Graph &g, MT &matching, GT &barrier)
	Perfect matching in a bipartite graph.

Function Documentation

int lemon::maxBipartiteMatching ( const BpUGraph & graph ) [inline]

This function calculates the maximum cardinality matching in a bipartite graph. It gives back the matching in an undirected edge map.

Parameters:

graph

The bipartite graph.

Returns:: The size of the matching.

int lemon::maxBipartiteMatching	(	const BpUGraph &	graph,
		MatchingMap &	matching
	)			`[inline]`

This function calculates the maximum cardinality matching in a bipartite graph. It gives back the matching in an undirected edge map.

Parameters:

graph

The bipartite graph.

Return values:

matching

The ANodeMap of UEdges which will be set to covered matching undirected edge.

Returns:: The size of the matching.

int lemon::maxBipartiteMatching	(	const BpUGraph &	graph,
		MatchingMap &	matching,
		BarrierMap &	barrier
	)			`[inline]`

This function calculates the maximum cardinality matching in a bipartite graph. It gives back the matching in an undirected edge map.

Parameters:

graph

The bipartite graph.

Return values:

	matching	The ANodeMap of UEdges which will be set to covered matching undirected edge.
	barrier	The BNodeMap of bools which will be set to a barrier of the BNode-set.

Returns:: The size of the matching.

WeightMap::Value lemon::maxWeightedBipartiteMatching	(	const BpUGraph &	graph,
		const WeightMap &	weight,
		MatchingMap &	matching
	)			`[inline]`

This function calculates the maximum weighted matching in a bipartite graph. It gives back the matching in an undirected edge map.

Parameters:

	graph	The bipartite graph.
	weight	The undirected edge map which contains the weights.

Return values:

matching

The undirected edge map which will be set to the matching.

Returns:: The value of the matching.

WeightMap::Value lemon::maxWeightedMaxBipartiteMatching	(	const BpUGraph &	graph,
		const WeightMap &	weight,
		MatchingMap &	matching
	)			`[inline]`

This function calculates the maximum weighted of the maximum cardinality matchings of a bipartite graph. It gives back the matching in an undirected edge map.

Parameters:

	graph	The bipartite graph.
	weight	The undirected edge map which contains the weights.

Return values:

matching

The undirected edge map which will be set to the matching.

Returns:: The value of the matching.

CostMap::Value lemon::minCostMaxBipartiteMatching	(	const BpUGraph &	graph,
		const CostMap &	cost,
		MatchingMap &	matching
	)			`[inline]`

This function calculates the maximum cardinality matching with minimum cost of a bipartite graph. It gives back the matching in an undirected edge map.

Parameters:

	graph	The bipartite graph.
	cost	The undirected edge map which contains the costs.

Return values:

matching

The undirected edge map which will be set to the matching.

Returns:: The cost of the matching.

int lemon::prBipartiteMatching ( const Graph & g ) [inline]

This function finds the maximum cardinality of the matchings in a bipartite graph g.

Parameters:

g

An undirected bipartite graph.

Returns:: The cardinality of the maximum matching.

Note:: The the implementation is based on the push-relabel principle.

int lemon::prBipartiteMatching	(	const Graph &	g,
		MT &	matching
	)			`[inline]`

This function finds a maximum cardinality matching in a bipartite graph g.

Parameters:

g

An undirected bipartite graph.

Return values:

matching A write ANodeMap of value type UEdge. The found edges will be returned in this map, i.e. for an ANode n the edge matching[n] is the one that covers the node n.

Returns:: The cardinality of the maximum matching.

Note:: The the implementation is based on the push-relabel principle.

int lemon::prBipartiteMatching	(	const Graph &	g,
		MT &	matching,
		GT &	barrier
	)			`[inline]`

This function finds a maximum cardinality matching in a bipartite graph g.

Parameters:

g

An undirected bipartite graph.

Return values:

	matching	A write ANodeMap of value type `UEdge`. The found edges will be returned in this map, i.e. for an `ANode` `n` the edge `matching[n]` is the one that covers the node `n`.
	barrier	A `bool` WriteMap on the BNodes. The map will be set exactly once for each BNode. The nodes with `true` value represent a barrier B, i.e. the cardinality of B minus the number of its neighbor is equal to the number of the `BNode`s minus the cardinality of the maximum matching.

Returns:: The cardinality of the maximum matching.

Note:: The the implementation is based on the push-relabel principle.

bool lemon::prPerfectBipartiteMatching ( const Graph & g ) [inline]

This function checks whether the bipartite graph g has a perfect matching.

Parameters:

g

An undirected bipartite graph.

Returns:: true iff g has a perfect matching.

Note:: The the implementation is based on the push-relabel principle.

bool lemon::prPerfectBipartiteMatching	(	const Graph &	g,
		MT &	matching
	)			`[inline]`

This function finds a perfect matching in a bipartite graph g.

Parameters:

g

An undirected bipartite graph.

Return values:

matching A write ANodeMap of value type UEdge. The found edges will be returned in this map, i.e. for an ANode n the edge matching[n] is the one that covers the node n. The values are unchanged if the graph has no perfect matching.

Returns:: true iff g has a perfect matching.

Note:: The the implementation is based on the push-relabel principle.

bool lemon::prPerfectBipartiteMatching	(	const Graph &	g,
		MT &	matching,
		GT &	barrier
	)			`[inline]`

This function finds a perfect matching in a bipartite graph g.

Parameters:

g

An undirected bipartite graph.

Return values:

	matching	A write ANodeMap of value type `UEdge`. The found edges will be returned in this map, i.e. for an `ANode` `n` the edge `matching[n]` is the one that covers the node `n`. The values are unchanged if the graph has no perfect matching.
	barrier	A `bool` WriteMap on the BNodes. The map will only be set if `g` has no perfect matching. In this case it is set exactly once for each BNode. The nodes with `true` value represent a barrier, i.e. a subset B a of BNodes with the property that the cardinality of B is greater than the number of its neighbors.

Returns:: true iff g has a perfect matching.

Note:: The the implementation is based on the push-relabel principle.

Matching algorithms [Algorithms]

Detailed Description

Classes

Files

Functions

Function Documentation

Matching algorithms
[Algorithms]