01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 package algs64; // section 6.4 import stdlib.*; /* *********************************************************************** * Compilation: javac BipartiteMatching.java * Execution: java BipartiteMatching N E * Dependencies: FordFulkerson.java FlowNetwork.java FlowEdge.java * * Find a maximum matching in a bipartite graph. Solve by reducing * to maximum flow. * * The order of growth of the running time in the worst case is E V * because each augmentation increases the cardinality of the matching * by one. * * The Hopcroft-Karp algorithm improves this to E V^1/2 by finding * a maximal set of shortest augmenting paths in each phase. * *********************************************************************/ public class BipartiteMatching { public static void main(String[] args) { // read in bipartite network with 2N vertices and E edges // we assume the vertices on one side of the bipartition // are named 0 to N-1 and on the other side are N to 2N-1. int N = Integer.parseInt(args[0]); int E = Integer.parseInt(args[1]); int s = 2*N, t = 2*N + 1; FlowNetwork G = new FlowNetwork(2*N + 2); for (int i = 0; i < E; i++) { int v = StdRandom.uniform(N); int w = StdRandom.uniform(N) + N; G.addEdge(new FlowEdge(v, w, Double.POSITIVE_INFINITY)); StdOut.println(v + "-" + w); } for (int i = 0; i < N; i++) { G.addEdge(new FlowEdge(s, i, 1.0)); G.addEdge(new FlowEdge(i + N, t, 1.0)); } // compute maximum flow and minimum cut FordFulkerson maxflow = new FordFulkerson(G, s, t); StdOut.println(); StdOut.println("Size of maximum matching = " + (int) maxflow.value()); for (int v = 0; v < N; v++) { for (FlowEdge e : G.adj(v)) { if (e.from() == v && e.flow() > 0) StdOut.println(e.from() + "-" + e.to()); } } } }