Class GraphMatchingExtensions

Namespace

Graph1x.Algorithms

Assembly

Graph1x.dll

Convenience entry points for matching queries.

public static class GraphMatchingExtensions

Inheritance

object

GraphMatchingExtensions

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

object.ToString()

Methods

MaximumBipartiteMatching<TVertex, TEdge>(IReadOnlyGraph<TVertex, TEdge>)

Computes a maximum-cardinality matching of an undirected bipartite graph using Hopcroft-Karp.

public static IReadOnlyList<TEdge> MaximumBipartiteMatching<TVertex, TEdge>(this IReadOnlyGraph<TVertex, TEdge> graph) where TVertex : notnull where TEdge : IEdge<TVertex>

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.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

Exceptions

ArgumentException

graph is directed or not bipartite.