Matching algorithms in graphs and bipartite graphs
[Algorithms]


Detailed Description

This group provides some algorithm objects and function to calculate matchings in graphs and bipartite graphs.

bipartite_matching.png


Files

file  bipartite_matching.h
 Maximum matching algorithms in bipartite graphs.
file  max_matching.h
 Maximum matching algorithm in undirected graph.

Classes

class  MaxBipartiteMatching
 Bipartite Max Cardinality Matching algorithm. More...
class  MaxWeightedBipartiteMatching
 Bipartite Max Weighted Matching algorithm. More...
class  MinCostMaxBipartiteMatching
 Bipartite Min Cost Matching algorithm. More...
class  MaxMatching
 Edmonds' alternating forest maximum matching algorithm. More...

Functions

template<typename BpUGraph, typename MatchingMap>
int maxBipartiteMatching (const BpUGraph &graph, MatchingMap &matching)
 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.


Function Documentation

int lemon::maxBipartiteMatching ( const BpUGraph &  graph,
MatchingMap &  matching 
)

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 undirected edge map which will be set to the matching.
Returns:
The size of the matching.

WeightMap::Value lemon::maxWeightedBipartiteMatching ( const BpUGraph &  graph,
const WeightMap &  weight,
MatchingMap &  matching 
)

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 
)

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 
)

This function calculates the minimum cost matching of the maximum cardinality matchings 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.


Generated on Tue Oct 31 09:49:38 2006 for LEMON by  doxygen 1.5.1