316 @defgroup matching Matching algorithms |
316 @defgroup matching Matching algorithms |
317 @ingroup algs |
317 @ingroup algs |
318 \brief This group describes the algorithms |
318 \brief This group describes the algorithms |
319 for find matchings in graphs and bipartite graphs. |
319 for find matchings in graphs and bipartite graphs. |
320 |
320 |
321 This group provides some algorithm objects and function |
321 This group provides some algorithm objects and function to calculate |
322 to calculate matchings in graphs and bipartite graphs. |
322 matchings in graphs and bipartite graphs. The general matching problem is |
|
323 finding a subset of the edges which does not shares common endpoints. |
|
324 |
|
325 There are several different algorithms for calculate matchings in |
|
326 graphs. The matching problems in bipartite graphs are generally |
|
327 easier than in general graphs. The goal of the matching optimization |
|
328 can be the finding maximum cardinality, maximum weight or minimum cost |
|
329 matching. The search can be constrained to find perfect or |
|
330 maximum cardinality matching. |
|
331 |
|
332 Lemon contains the next algorithms: |
|
333 - \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp |
|
334 augmenting path algorithm for calculate maximum cardinality matching in |
|
335 bipartite graphs |
|
336 - \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel |
|
337 algorithm for calculate maximum cardinality matching in bipartite graphs |
|
338 - \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching" |
|
339 Successive shortest path algorithm for calculate maximum weighted matching |
|
340 and maximum weighted bipartite matching in bipartite graph |
|
341 - \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching" |
|
342 Successive shortest path algorithm for calculate minimum cost maximum |
|
343 matching in bipartite graph |
|
344 - \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm |
|
345 for calculate maximum cardinality matching in general graph |
|
346 - \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom |
|
347 shrinking algorithm for calculate maximum weighted matching in general |
|
348 graph |
|
349 - \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching" |
|
350 Edmond's blossom shrinking algorithm for calculate maximum weighted |
|
351 perfect matching in general graph |
323 |
352 |
324 \image html bipartite_matching.png |
353 \image html bipartite_matching.png |
325 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth |
354 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth |
326 |
355 |
327 */ |
356 */ |