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.
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]
- Data
Flags
Automatic Flags
| Name | Description | Default |
|---|---|---|
| buildperftest | Build performance testing and comparison | Disabled |
Use -f <flag> to enable a flag, or -f -<flag> to disable that flag. More info
Downloads
- maxBipartiteMatching-0.1.0.0.tar.gz [browse] (Cabal source package)
- Package description (as included in the package)
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:
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.