edu.princeton.cs.algs4

Class BipartiteMatching

• Object
• edu.princeton.cs.algs4.BipartiteMatching

• ```public class BipartiteMatching
extends Object```
The `BipartiteMatching` class represents a data type for computing a maximum (cardinality) matching and a minimum (cardinality) vertex cover in a bipartite graph. A bipartite graph in a graph whose vertices can be partitioned into two disjoint sets such that every edge has one endpoint in either set. A matching in a graph is a subset of its edges with no common vertices. A maximum matching is a matching with the maximum number of edges. A perfect matching is a matching which matches all vertices in the graph. A vertex cover in a graph is a subset of its vertices such that every edge is incident to at least one vertex. A minimum vertex cover is a vertex cover with the minimum number of vertices. By Konig's theorem, in any biparite graph, the maximum number of edges in matching equals the minimum number of vertices in a vertex cover. The maximum matching problem in nonbipartite graphs is also important, but all known algorithms for this more general problem are substantially more complicated.

This implementation uses the alternating-path algorithm. It is equivalent to reducing to the maximum-flow problem and running the augmenting-path algorithm on the resulting flow network, but it does so with less overhead. The constructor takes O((E + V) V) time, where E is the number of edges and V is the number of vertices in the graph. It uses Θ(V) extra space (not including the graph).

See also `HopcroftKarp`, which solves the problem in O(E sqrt(V)) using the Hopcroft-Karp algorithm and BipartiteMatchingToMaxflow, which solves the problem in O((E + V) V) time via a reduction to maxflow.

For additional documentation, see Section 6.5 Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

Author:
Robert Sedgewick, Kevin Wayne
• Constructor Summary

Constructors
Constructor and Description
`BipartiteMatching(Graph G)`
Determines a maximum matching (and a minimum vertex cover) in a bipartite graph.
• Method Summary

All Methods
Modifier and Type Method and Description
`boolean` `inMinVertexCover(int v)`
Returns true if the specified vertex is in the minimum vertex cover computed by the algorithm.
`boolean` `isMatched(int v)`
Returns true if the specified vertex is matched in the maximum matching computed by the algorithm.
`boolean` `isPerfect()`
Returns true if the graph contains a perfect matching.
`static void` `main(String[] args)`
Unit tests the `HopcroftKarp` data type.
`int` `mate(int v)`
Returns the vertex to which the specified vertex is matched in the maximum matching computed by the algorithm.
`int` `size()`
Returns the number of edges in a maximum matching.
• Methods inherited from class Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• Constructor Detail

• BipartiteMatching

`public BipartiteMatching(Graph G)`
Determines a maximum matching (and a minimum vertex cover) in a bipartite graph.
Parameters:
`G` - the bipartite graph
Throws:
`IllegalArgumentException` - if `G` is not bipartite
• Method Detail

• mate

`public int mate(int v)`
Returns the vertex to which the specified vertex is matched in the maximum matching computed by the algorithm.
Parameters:
`v` - the vertex
Returns:
the vertex to which vertex `v` is matched in the maximum matching; `-1` if the vertex is not matched
Throws:
`IllegalArgumentException` - unless `0 <= v < V`
• isMatched

`public boolean isMatched(int v)`
Returns true if the specified vertex is matched in the maximum matching computed by the algorithm.
Parameters:
`v` - the vertex
Returns:
`true` if vertex `v` is matched in maximum matching; `false` otherwise
Throws:
`IllegalArgumentException` - unless `0 <= v < V`
• size

`public int size()`
Returns the number of edges in a maximum matching.
Returns:
the number of edges in a maximum matching
• isPerfect

`public boolean isPerfect()`
Returns true if the graph contains a perfect matching. That is, the number of edges in a maximum matching is equal to one half of the number of vertices in the graph (so that every vertex is matched).
Returns:
`true` if the graph contains a perfect matching; `false` otherwise
• inMinVertexCover

`public boolean inMinVertexCover(int v)`
Returns true if the specified vertex is in the minimum vertex cover computed by the algorithm.
Parameters:
`v` - the vertex
Returns:
`true` if vertex `v` is in the minimum vertex cover; `false` otherwise
Throws:
`IllegalArgumentException` - unless `0 <= v < V`
• main

`public static void main(String[] args)`
Unit tests the `HopcroftKarp` data type. Takes three command-line arguments `V1`, `V2`, and `E`; creates a random bipartite graph with `V1` + `V2` vertices and `E` edges; computes a maximum matching and minimum vertex cover; and prints the results.
Parameters:
`args` - the command-line arguments