[ 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

- maximum_matching_hopcroft_karp(+, ++, ++, -) is semidet

### Fail Conditions

Graph is not bipartite
## Examples

## See Also