[Haskell-cafe] Maximum bipartite matching: 24 lines

[Eugene Kirpichov]

Hi,

    fwd = foldr (\(x,y) -> M.insertWith (++) x [y]) M.empty $ S.toList g

Use foldl' here, foldr is absolutely useless here and it only consumes
the stack space as your operation is strict.

As for the actual code: I'd prefer the code itself to be more
readable, rather than have a lot of literate comments around it;
currently, IMO all the uncurry's, flips, eithers, maybes and
point-free style hurt readability heavily. I think it would be better
to devise your own very simple datatypes for this.

Maybe I'm too capricious or heretically unhaskellish, I'll probably
try to write my own version as an exercise :)

On Mon, Oct 22, 2012 at 1:28 PM, Stefan Klinger
<all-lists at stefan-klinger.de> wrote:
> 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
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>



-- 
Eugene Kirpichov
http://www.linkedin.com/in/eugenekirpichov
We're hiring! http://tinyurl.com/mirantis-openstack-engineer