[Haskell-cafe] Maximum bipartite matching: 24 lines

Stefan Klinger all-lists at stefan-klinger.de
Mon Oct 22 22:28:38 CEST 2012


Hello.

I have written a function that calculates maximum cardinality matchings
on bipartite graphs.  It's only 24 lines of code.

It seems (tested, not proven) to run faster, use less memory, and scale
better than using MaxFlow from FGL with constant weight and additional
source and sink nodes.  But it's not as good as Hopcroft–Karp would be.

Attached is the module MaxMatching which also contains extensive
documentation of the rationale behind its design.  I would hope to get
any feedback on this: What do you think about the approach?  Did I
oversee anything?  Do you know of any other purely functional solution
to this problem?

Just as an exmaple, run `ghci MaxMatching.lhs` and then use

    matching $ S.fromList [(1,'a'),(1,'b'),(2,'a'),(2,'c'),(3,'b')]

to calculate a maximum cardinality matching of the graph shown below.

    1---a       Note the somewhat awkward type of the matching
     \ /        function, returning a Map instead of a Set, with the
      X         edges being backwards!
     / \
    2   b       matching :: (Ord b, Ord a) => S.Set (a, b) -> M.Map b a
     \ /        
      X         On my machine, it takes less than 2s on 10k edges
     / \        or 225 nodes.
    3   c

Comments are welcome!

Thank you!
Stefan


-- 
Stefan Klinger                                      o/klettern
                                                    /\/  bis zum
send plaintext only - max size 32kB - no spam         \   Abfallen
http://stefan-klinger.de
-------------- next part --------------
A non-text attachment was scrubbed...
Name: MaxMatching.lhs
Type: text/x-literate-haskell
Size: 5790 bytes
Desc: not available
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20121022/3ec055fd/attachment.lhs>


More information about the Haskell-Cafe mailing list