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. |
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.
graph | The bipartite graph. |
matching | The undirected edge map which will be set to 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.
graph | The bipartite graph. | |
weight | The undirected edge map which contains the weights. |
matching | The undirected edge map which will be set to 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.
graph | The bipartite graph. | |
weight | The undirected edge map which contains the weights. |
matching | The undirected edge map which will be set to 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.
graph | The bipartite graph. | |
cost | The undirected edge map which contains the costs. |
matching | The undirected edge map which will be set to the matching. |