[ 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
G
A directed bipartite graph, with all edges starting and ending in 'A' or 'B'
A
List of nodes in one half of the graph
B
List of nodes in the other half of the graph
MaximalM
List of edges constituting the maximum matching

Description

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

Examples


See Also