/****************************************************************************** * Compilation: javac BipartiteMatching.java * Execution: java BipartiteMatching V1 V2 E * Dependencies: BipartiteX.java * * Find a maximum cardinality matching (and minimum cardinality vertex cover) * in a bipartite graph using the alternating path algorithm. * ******************************************************************************/ /** * The {@code 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 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 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 {@link 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
* @author Kevin Wayne
*/
public class BipartiteMatching {
private static final int UNMATCHED = -1;
private final int V; // number of vertices in the graph
private BipartiteX bipartition; // the bipartition
private int cardinality; // cardinality of current matching
private int[] mate; // mate[v] = w if v-w is an edge in current matching
// = -1 if v is not in current matching
private boolean[] inMinVertexCover; // inMinVertexCover[v] = true iff v is in min vertex cover
private boolean[] marked; // marked[v] = true iff v is reachable via alternating path
private int[] edgeTo; // edgeTo[v] = last edge on alternating path to v
/**
* Determines a maximum matching (and a minimum vertex cover)
* in a bipartite graph.
*
* @param G the bipartite graph
* @throws IllegalArgumentException if {@code G} is not bipartite
*/
public BipartiteMatching(Graph G) {
bipartition = new BipartiteX(G);
if (!bipartition.isBipartite()) {
throw new IllegalArgumentException("graph is not bipartite");
}
this.V = G.V();
// initialize empty matching
mate = new int[V];
for (int v = 0; v < V; v++)
mate[v] = UNMATCHED;
// alternating path algorithm
while (hasAugmentingPath(G)) {
// find one endpoint t in alternating path
int t = -1;
for (int v = 0; v < G.V(); v++) {
if (!isMatched(v) && edgeTo[v] != -1) {
t = v;
break;
}
}
// update the matching according to alternating path in edgeTo[] array
for (int v = t; v != -1; v = edgeTo[edgeTo[v]]) {
int w = edgeTo[v];
mate[v] = w;
mate[w] = v;
}
cardinality++;
}
// find min vertex cover from marked[] array
inMinVertexCover = new boolean[V];
for (int v = 0; v < V; v++) {
if (bipartition.color(v) && !marked[v]) inMinVertexCover[v] = true;
if (!bipartition.color(v) && marked[v]) inMinVertexCover[v] = true;
}
assert certifySolution(G);
}
/*
* is there an augmenting path?
* - if so, upon termination adj[] contains the level graph;
* - if not, upon termination marked[] specifies those vertices reachable via an alternating
* path from one side of the bipartition
*
* an alternating path is a path whose edges belong alternately to the matching and not
* to the matching
*
* an augmenting path is an alternating path that starts and ends at unmatched vertices
*
* this implementation finds a shortest augmenting path (fewest number of edges), though there
* is no particular advantage to do so here
*/
private boolean hasAugmentingPath(Graph G) {
marked = new boolean[V];
edgeTo = new int[V];
for (int v = 0; v < V; v++)
edgeTo[v] = -1;
// breadth-first search (starting from all unmatched vertices on one side of bipartition)
Queue