[ library(graph_algorithms) | Reference Manual | Alphabetic Index ]

maximum_matching_hopcroft_karp(+G, ++A, ++B, -MaximalM)

Compute the maximum matching in a bipartite graph using Hopcroft and Karp's algorithm
A directed bipartite graph, with all edges starting and ending in 'A' or 'B'
List of nodes in one half of the graph
List of nodes in the other half of the graph
List of edges constituting the maximum matching


Computes the maximum matching in the given bipartite graph. A matching in a bipartite graph, is a set of edges from the graph such that no two edges are incident to the same node. A maximum matching is a matching with the most edges possible. The may be more than one maximum matching, this predicate returns only one.

The implementation uses Hopcroft and Karp's algorithm which has a complexity of O(Nedges*SQRT(Nnodes in A)).

Modes and Determinism

Fail Conditions

Graph is not bipartite


See Also