The maxBipartiteMatching package


Find a maximum cardinality matching on a bipartite graph, using an augmenting path algorithm. More efficient than using MaxFlow from FGL with constant weight and additional source and sink nodes.

[Skip to ReadMe]


Dependenciesbase (==4.9.*), containers (==0.5.*), directory, fgl (==5.5.*), parallel-io (==0.3.*), QuickCheck (==2.9.*) [details]
AuthorStefan Klinger <>
MaintainerStefan Klinger <>
CategoryAlgorithms, Graph
Home page
Source repositoryhead: git clone
ExecutablesmkGraphs, fgl, matcher
UploadedSun Jul 31 17:10:24 UTC 2016 by StefanKlinger




buildperftestBuild performance testing and comparisonDisabledAutomatic

Use -f <flag> to enable a flag, or -f -<flag> to disable that flag. More info


Maintainers' corner

For package maintainers and hackage trustees

Readme for maxBipartiteMatching-

Maximum Cardinality Bipartite Matching


A somewhat efficient, purely functional (Haskell) algorithm to find maximum cardinality matchings in bipartite graphs (MCBM).

This project contains a library, command line tool, tests and benchmark.


Module Data.Graph.MaxBipartiteMatching exports the function

matching :: (Ord a, Ord b) => S.Set (a,b) -> M.Map b a

which calculates a maximum cardinality matching on the given bipartite graph.

The small command line tool matcher demonstrates the use of the matching library. See build instructions for more.

Performance & Testing

The implementation is quite compact with the core functions accounting for only 21 lines. The source file contains extensive information about the workings of the algorithm. There is no correctness proof, but a test suite is available.

$ grep -Ec '^>' src/Data/Graph/MaxBipartiteMatching.lhs

Despite its brevity it seems rather efficient. There are very few other purely functional MCBM implementations around. AFAIK there is none in FGL (June 2016), but they have a MaxFlow algorithm which is a much more general approach of course. However, if you only need MCBM, then this implementation scales better than using FGL:

cpu/size memory/size sample distribution

Scripts to run the comparison are contained in this repository.


See the BUGS/open subdirectory.


The implementation was originally announced on Mon, 22 Oct 2012 on the haskell-cafe! mailing list. Since then I use this toy project to play with other tools in, e.g., GitHub.