| License | LGPL-2.1 |
|---|---|
| Maintainer | Manuel Eberl <last name + m _at_ in.tum.de> |
| Stability | experimental |
| Safe Haskell | Safe-Inferred |
| Language | Haskell2010 |
Data.Graph.Inductive.Query.Matchings
Description
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.