[ 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