dwave.graphs.algorithms.matching.maximal_matching#

maximal_matching(graph: int | tuple[Collection[Hashable], Collection[tuple[Hashable, Hashable]]] | Collection[tuple[Hashable, Hashable]] | Graph, sampler: Sampler, **sampler_args) → set[Hashable][source]#

Finds an approximate maximal matching.

Defines a BQM with ground states corresponding to a maximal matching and uses the sampler to sample from it.

A matching is a subset of edges in which no node occurs more than once. A maximal matching is one in which no edges from graph can be added without violating the matching rule.

Finding maximal matchings can be done is polynomial time, so this method is only useful pedagogically.

Based on the formulation presented in [Luc2014].

Parameters:

  • graph – The graph on which to find a maximal matching. Either an integer n, interpreted as a complete graph of size n, a nodes/edges pair, a list of edges or a NetworkX graph.

  • sampler – A dimod sampler.

  • **sampler_args – Additional keyword parameters are passed to the sampler.

Returns:

A maximal matching of the graph.