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.

#maximumBipartiteMatching Source

maximumBipartiteMatching :: forall a b. Ord a => Ord b => Map a (Set b) -> Map b a

Maximum bipartite matching, right-to-left: each matched b with the a it is assigned to.

#matchingSize Source

matchingSize :: forall a b. Map b a -> Int

#isPerfect Source

isPerfect :: forall a b. Ord a => Ord b => Map a (Set b) -> Map b a -> Boolean

Every left vertex matched.