Copyright	© 2012 Stefan Klinger <http://stefan-klinger.de/>
License	GNU AGPL 3 <http://www.gnu.org/licenses/agpl-3.0.html>
Maintainer	http://stefan-klinger.de
Stability	experimental
Safe Haskell	Safe
Language	Haskell98

Data.Graph.MaxBipartiteMatching

Description

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. But not as good as Hopcroft–Karp would be.

Synopsis

Documentation

matching :: (Ord a, Ord b) => Set (a, b) -> Map b a Source #

Return a maximum cardinality matching. The input graph is a Set (α,β) of edges, which implies being bipartite and simple. The matching is returned as an injective Map β α, i.e., backwards.

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