public class BipartiteMatching extends Object
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 alternatingpath algorithm. It is equivalent to reducing to the maximumflow problem and running the augmentingpath 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 HopcroftKarp
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.
Constructor and Description 

BipartiteMatching(Graph G)
Determines a maximum matching (and a minimum vertex cover)
in a bipartite graph.

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.

public BipartiteMatching(Graph G)
G
 the bipartite graphIllegalArgumentException
 if G
is not bipartitepublic int mate(int v)
v
 the vertexv
is matched in the
maximum matching; 1
if the vertex is not matchedIllegalArgumentException
 unless 0 <= v < V
public boolean isMatched(int v)
v
 the vertextrue
if vertex v
is matched in maximum matching;
false
otherwiseIllegalArgumentException
 unless 0 <= v < V
public int size()
public boolean isPerfect()
true
if the graph contains a perfect matching;
false
otherwisepublic boolean inMinVertexCover(int v)
v
 the vertextrue
if vertex v
is in the minimum vertex cover;
false
otherwiseIllegalArgumentException
 unless 0 <= v < V
public static void main(String[] args)
HopcroftKarp
data type.
Takes three commandline 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.args
 the commandline arguments