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
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
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@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
On 2012-Oct-22 14:23 (-0700), Eugene Kirpichov wrote with possible deletions:
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.
Thank you very much for that. I'll review the code under strictness aspects.
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;
I like comments documenting why something's done, complementing the code which tells what's done.
currently, IMO all the uncurry's, flips, eithers, maybes and point-free style hurt readability heavily.
I agree. Between babbling bloated and incomprehensible terse, my code is certainly towards the terse extreme. For me, that's a balancing act that I find hard to do right.
I'll probably try to write my own version as an exercise :)
Cool! I'd like to see that... Cheers! Stefan -- Stefan Klinger o/klettern /\/ bis zum send plaintext only - max size 32kB - no spam \ Abfallen http://stefan-klinger.de
I didn't analyze it but anytime I see "M.insertWith" I am just in doubt -
do you know about a strict version M.insertWith' ?
2012/10/24 Stefan Klinger
On 2012-Oct-22 14:23 (-0700), Eugene Kirpichov wrote with possible deletions:
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.
Thank you very much for that. I'll review the code under strictness aspects.
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;
I like comments documenting why something's done, complementing the code which tells what's done.
currently, IMO all the uncurry's, flips, eithers, maybes and point-free style hurt readability heavily.
I agree. Between babbling bloated and incomprehensible terse, my code is certainly towards the terse extreme. For me, that's a balancing act that I find hard to do right.
I'll probably try to write my own version as an exercise :)
Cool! I'd like to see that...
Cheers! 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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
participants (3)
-
Dmitry Olshansky -
Eugene Kirpichov -
Stefan Klinger