maxBipartiteMatching: Maximum cardinality bipartite matching

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] [Publish]

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

Versions 0.1.0.0
Change log None available
Dependencies base (>=4.9 && <4.10), containers (>=0.5 && <0.6), directory, fgl (>=5.5 && <5.6), parallel-io (>=0.3 && <0.4), QuickCheck (>=2.9 && <2.10) [details]
License LicenseRef-OtherLicense
Author Stefan Klinger <http://stefan-klinger.de/>
Maintainer Stefan Klinger <http://stefan-klinger.de/>
Category Algorithms, Graph
Home page http://stefan-klinger.de/
Source repo head: git clone https://github.com/s5k6/maxBipartiteMatching.git
Uploaded by StefanKlinger at 2016-07-31T17:10:24Z

Modules

[Index]

Flags

Automatic Flags
NameDescriptionDefault
buildperftest

Build performance testing and comparison

Disabled

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

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees


Readme for maxBipartiteMatching-0.1.0.0

[back to package description]

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.