Data.Graph.MaxBipartiteMatching

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.

Documentation

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

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)]