Package edu.princeton.cs.algs4
Class BipartiteMatching
 Object

 edu.princeton.cs.algs4.BipartiteMatching

public class BipartiteMatching extends Object
TheBipartiteMatching
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 bipartite 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.
 Author:
 Robert Sedgewick, Kevin Wayne


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

Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method 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 theHopcroftKarp
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.



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
 ifG
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
 unless0 <= 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 vertexv
is matched in maximum matching;false
otherwise Throws:
IllegalArgumentException
 unless0 <= 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 vertexv
is in the minimum vertex cover;false
otherwise Throws:
IllegalArgumentException
 unless0 <= v < V

main
public static void main(String[] args)
Unit tests theHopcroftKarp
data type. Takes three commandline argumentsV1
,V2
, andE
; creates a random bipartite graph withV1
+V2
vertices andE
edges; computes a maximum matching and minimum vertex cover; and prints the results. Parameters:
args
 the commandline arguments

