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}