Module
Data.Graph.Matching
- Package
- purescript-hylograph-graph
- Repository
- afcondon/purescript-hylograph-graph
Bipartite matching.
maximumBipartiteMatching finds a maximum matching by Kuhn's
augmenting-path algorithm, O(V·E) — the right tool for small dense
graphs (constraint-propagation houses, assignment problems); swap in
Hopcroft–Karp only if profiling ever demands it. The input is the
left-side adjacency (each a with the set of bs it may pair with);
the result maps each matched b to its a.
Contributed for Régin-style alldifferent filtering (matching + the strongly connected components of the alternating digraph decide which candidate edges survive in some maximum matching), but nothing here is specific to that use.
#matchingSize Source
matchingSize :: forall a b. Map b a -> Int