BitGraph.Algorithm.Matching.Kuhn (bitgraph v0.4.1)

Maximum Matching for bipartite graph (Kuhn algorithm). Implementation mostly follows https://cp-algorithms.com/graph/kuhn_maximum_bipartite_matching.html

Summary

Functions

dfs_iterate(graph, neighbors, state, vertex)
get_matching_count(state)
iterate_fun(graph, state, vertex)
preprocess(graph, opts)

Replaces vertex labels with vertex indices. The modified options will be used by the implementation (run/2)

run(graph, opts \\ [])

Kuhn algorithm (operating on vertex indices) graph - bipartite graph.

run(graph, left_partition, opts)

Functions

dfs_iterate(graph, neighbors, state, vertex)

get_matching_count(state)

iterate_fun(graph, state, vertex)

preprocess(graph, opts)

@spec preprocess(BitGraph.t(), Keyword.t()) :: Keyword.t()

Replaces vertex labels with vertex indices. The modified options will be used by the implementation (run/2)

run(graph, opts \\ [])

@spec run(BitGraph.t(), Keyword.t()) :: %{matching: Map.t(), free: MapSet.t()} | nil

Kuhn algorithm (operating on vertex indices) graph - bipartite graph.

Options:

  • :left_partition (mandatory) - list or set of vertices that represent one of the two paartition of graph.
  • :fixed_matching (optional) - The edges that have to be in matching. This is a left_vertex => right vertex , where left_vertex is a vertex from left_partition
  • :required_size (optional) - The required size of maximum matching. If not reached, algorithm returns nil

Output: map with keys

  • :matching - map of left_vertex => right_vertex
  • :free - unmatched vertices from right partition

run(graph, left_partition, opts)

@spec run(BitGraph.t(), MapSet | list(), Keyword.t()) ::
  %{matching: Map.t(), free: MapSet.t()} | nil