Function test_rand

code/graph/hopcroft_karp.test.cpp:3–34

#include "../code/graph/bipartite_matching.cpp"

void test_rand(int N, int M, int sparseness = 2) {
  adj = new vi[N];

  done = new bool[N];
  memset(done, 0, sizeof(bool) * N);

  owner = new int[M];
  memset(owner, -1, sizeof(int) * M);

  bipartite_graph g(N, M);

  for(int i = 0; i < N; i++) {
    for(int j = 0; j < M; j++) {
      if(rng() % sparseness == 0) {
        g.add_edge(i, j);
        adj[i].push_back(j);
      }
    }
  }

  int sum = 0;
  for(int i = 0; i < N; ++i) {
    memset(done, 0, sizeof(bool) * N);
    sum += alternating_path(i);
  }

  assert_equal(sum, g.maximum_matching());

  delete[] adj;
  delete[] done;
  delete[] owner;
}

void test() {
  int TESTS = 1000, MAX_N = 400, MAX_M = 300;