Maximum Cardinality Bipartite Matching ====================================== Synopsis -------- A somewhat efficient, purely functional (Haskell) algorithm to find maximum cardinality matchings in bipartite graphs ([MCBM](https://en.wikipedia.org/wiki/Maximum_flow_problem#Maximum_cardinality_bipartite_matching)). 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`](./src/Matcher.lhs) demonstrates the use of the matching library. See [build instructions](./INSTALL) 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](./INSTALL) 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](http://hackage.haskell.org/package/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](./tests/cpu_nodes+edges.png) ![memory/size](./tests/mem_nodes+edges.png) ![sample distribution](./tests/nodes_edges.png) Scripts to [run the comparison](./INSTALL) are contained in this repository. Bugs ---- See the `BUGS/open` subdirectory. History ------- The implementation was [originally announced](./HISTORY) 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.