001package algs64; // section 6.4 002import stdlib.*; 003/* *********************************************************************** 004 * Compilation: javac BipartiteMatching.java 005 * Execution: java BipartiteMatching N E 006 * Dependencies: FordFulkerson.java FlowNetwork.java FlowEdge.java 007 * 008 * Find a maximum matching in a bipartite graph. Solve by reducing 009 * to maximum flow. 010 * 011 * The order of growth of the running time in the worst case is E V 012 * because each augmentation increases the cardinality of the matching 013 * by one. 014 * 015 * The Hopcroft-Karp algorithm improves this to E V^1/2 by finding 016 * a maximal set of shortest augmenting paths in each phase. 017 * 018 *********************************************************************/ 019 020public class BipartiteMatching { 021 022 public static void main(String[] args) { 023 024 // read in bipartite network with 2N vertices and E edges 025 // we assume the vertices on one side of the bipartition 026 // are named 0 to N-1 and on the other side are N to 2N-1. 027 int N = Integer.parseInt(args[0]); 028 int E = Integer.parseInt(args[1]); 029 int s = 2*N, t = 2*N + 1; 030 FlowNetwork G = new FlowNetwork(2*N + 2); 031 for (int i = 0; i < E; i++) { 032 int v = StdRandom.uniform(N); 033 int w = StdRandom.uniform(N) + N; 034 G.addEdge(new FlowEdge(v, w, Double.POSITIVE_INFINITY)); 035 StdOut.println(v + "-" + w); 036 } 037 for (int i = 0; i < N; i++) { 038 G.addEdge(new FlowEdge(s, i, 1.0)); 039 G.addEdge(new FlowEdge(i + N, t, 1.0)); 040 } 041 042 043 // compute maximum flow and minimum cut 044 FordFulkerson maxflow = new FordFulkerson(G, s, t); 045 StdOut.println(); 046 StdOut.println("Size of maximum matching = " + (int) maxflow.value()); 047 for (int v = 0; v < N; v++) { 048 for (FlowEdge e : G.adj(v)) { 049 if (e.from() == v && e.flow() > 0) 050 StdOut.println(e.from() + "-" + e.to()); 051 } 052 } 053 } 054 055}