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());
      }
    }
  }

}