License | LGPL-2.1 |
---|---|

Maintainer | Manuel Eberl <last name + m _at_ in.tum.de> |

Stability | experimental |

Safe Haskell | Safe-Inferred |

Language | Haskell2010 |

This module provides some algorithms related to matchings in graphs, most notably an implementation of Edmond's blossom algorithm, which computes maximum matchings for graphs.

Definitions:

- A
*matching*is a subset of the edges of a graph such that no two edges in it are incident to the same node. - A
*maximal matching*is a matching that cannot be made any larger, i.e. no additional edge can be added to it without violating the property of node-disjoint edges. - A
*maximum matching*is a matching such that no other matching contains more edges.

In this list, the given notions are strictly increasing in strength. In particular, note that every maximum matching is also maximal, but not every maximal matching is a maximum one.

Our implementation of Edmond's blossom algorithm is an adaptation of the Java implementation in JGraphT: https://github.com/jgrapht/jgrapht/blob/master/jgrapht-core/src/main/java/org/jgrapht/alg/EdmondsBlossomShrinking.java

- isMatching :: Graph gr => gr a b -> [Edge] -> Bool
- isMaximalMatching :: Graph gr => gr a b -> [Edge] -> Bool
- isMaximumMatching :: Graph gr => gr a b -> [Edge] -> Bool
- maximalMatchings :: Graph gr => gr a b -> [[Edge]]
- maximumMatching :: Graph gr => gr a b -> [Edge]

# Documentation

isMatching :: Graph gr => gr a b -> [Edge] -> Bool Source

Determines whether a given set of edges is a matching.

isMaximalMatching :: Graph gr => gr a b -> [Edge] -> Bool Source

Determines whether a given set of edges is a maximal matching, i.e. a matching that cannot be extended by adding another edge.

isMaximumMatching :: Graph gr => gr a b -> [Edge] -> Bool Source

Determines whether the given set of edges is a maximum matching.

maximalMatchings :: Graph gr => gr a b -> [[Edge]] Source

Computes all maximal matchings in a graph.

maximumMatching :: Graph gr => gr a b -> [Edge] Source

Computes a maximum matching of the given graph using Edmond's blossom algorithm.