Safe Haskell	Safe-Inferred
Language	Haskell2010

Test.Predicates.Internal.FlowMatcher

Description

An implementation of bipartite matching using the Ford-Fulkerson algorithm.

Synopsis

bipartiteMatching :: forall a b. (a -> b -> Bool) -> [a] -> [b] -> ([(a, b)], [a], [b])

Documentation

>>> :set -Wno-type-defaults

bipartiteMatching :: forall a b. (a -> b -> Bool) -> [a] -> [b] -> ([(a, b)], [a], [b]) Source #

Computes the best bipartite matching of the elements in the two lists, given the compatibility function.

Returns matched pairs, then unmatched lhs elements, then unmatched rhs elements.

>>> bipartiteMatching (==) [1 .. 5] [6, 5 .. 2]
([(2,2),(3,3),(4,4),(5,5)],[1],[6])