Class HopcroftKarpMatching<TVertex, TEdge>

Namespace: Graph1x.Algorithms

Assembly: Graph1x.dll

The Hopcroft-Karp maximum-cardinality matching algorithm for undirected bipartite graphs, running in O(E·√V) by augmenting along maximal sets of shortest vertex-disjoint paths per phase. The bipartition is derived automatically; non-bipartite input is rejected. No strategy interface is introduced: with a single matching algorithm there is no swap point to justify one.

public sealed class HopcroftKarpMatching<TVertex, TEdge> where TVertex : notnull where TEdge : IEdge<TVertex>

Type Parameters

TVertex: The vertex type.
TEdge: The edge type.

Inheritance: object

HopcroftKarpMatching<TVertex, TEdge>

Inherited Members: object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.ReferenceEquals(object, object)

object.ToString()

Methods

FindMaximumMatching(IReadOnlyGraph<TVertex, TEdge>)

Computes a maximum-cardinality matching of the bipartite graph.

public IReadOnlyList<TEdge> FindMaximumMatching(IReadOnlyGraph<TVertex, TEdge> graph)

Parameters

graph IReadOnlyGraph<TVertex, TEdge>: The undirected bipartite graph.

Returns

IReadOnlyList<TEdge>: The matched edges; no two share a vertex, and no larger matching exists.

Exceptions

ArgumentException: graph is directed or not bipartite.