graph-matchings-0.1.0.0: An implementation of algorithms for matchings in graphs

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

Synopsis

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.