The maxBipartiteMatching package

This is a package candidate release! Here you can preview how this package release will appear once published to the main package index (which can be accomplished via the 'maintain' link below). Please note that once a package has been published to the main package index it cannot be undone! Please consult the package uploading documentation for more information.

[maintain]

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]

Properties

Version0.1.0.0
Change logNone available
Dependenciesbase (==4.9.*), containers (==0.5.*), directory, fgl (==5.5.*), parallel-io (==0.3.*), QuickCheck (==2.9.*) [details]
LicenseOtherLicense
AuthorStefan Klinger <http://stefan-klinger.de/>
MaintainerStefan Klinger <http://stefan-klinger.de/>
CategoryAlgorithms, Graph
Home pagehttp://stefan-klinger.de/
Source repositoryhead: git clone https://github.com/s5k6/maxBipartiteMatching.git
ExecutablesmkGraphs, fgl, matcher
UploadedSun Jul 31 17:10:24 UTC 2016 by StefanKlinger

Modules

[Index]

Flags

NameDescriptionDefaultType
buildperftestBuild performance testing and comparisonDisabledAutomatic

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

Downloads

Maintainers' corner

For package maintainers and hackage trustees

Readme for maxBipartiteMatching-0.1.0.0

Maximum Cardinality Bipartite Matching

Synopsis

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.

Use

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
25

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.

Bugs

See the BUGS/open subdirectory.

History

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