CPSolver.Algorithms.Kuhn (Fixpoint v0.10.2)

Kuhn's algorithm to find maximum matching in bipartite graph. https://cp-algorithms.com/graph/kuhn_maximum_bipartite_matching.html

Summary

Functions

initial_matching(graph, left_partition)

run(graph, left_partition, partial_matching \\ %{})

Given the bipartite graph, a list of vertices int the left partition, and (optional) partial matching %{right_side_vertex => left_side_vertex}, find maximum matching

Functions

initial_matching(graph, left_partition)

run(graph, left_partition, partial_matching \\ %{})

@spec run(Graph.t(), [any()], map()) :: map()

Given the bipartite graph, a list of vertices int the left partition, and (optional) partial matching %{right_side_vertex => left_side_vertex}, find maximum matching