Added max-clique

tonowak · Mar 9, 2024 · 5fe1c1c · 5fe1c1c
1 parent 87b4ab8
commit 5fe1c1c
Show file tree

Hide file tree

Showing 3 changed files with 89 additions and 0 deletions.
diff --git a/code/graph/chapter.tex b/code/graph/chapter.tex
@@ -12,6 12,7 @@ \chapter{Grafy}
 \myimport{eulerian-path}
 \myimport{hld}
 \myimport{jump-ptr}
 \myimport{max-clique}
 \myimport{negative-cycle}
 \myimport{planar-graph-faces}
 \myimport{planarity-check}

diff --git a/code/graph/max-clique/main.cpp b/code/graph/max-clique/main.cpp
@@ -0,0 1,46 @@
 /*
  * Opis: O(idk), działa 1s dla n=155 na najgorszych przypadkach
  * (losowe grafy p=.90). Działa szybciej dla grafów rzadkich.
  * Zwraca listę wierzchołków w jakiejś max klice. Pętelki niedozwolone.
  */
 constexpr int max_n = 500;
 vector<int> get_max_clique(vector<bitset<max_n>> e) {
  double limit = 0.025, pk = 0;
  vector<pair<int, int>> V;
  vector<vector<int>> C(ssize(e) 1);
  vector<int> qmax, q, S(ssize(C)), old(S);
  REP(i, ssize(e)) V.emplace_back(0, i);
  auto init = [&](vector<pair<int, int>>& r) {
  for (auto& v : r) for (auto j : r) v.first = e[v.second][j.second];
  sort(r.rbegin(), r.rend());
  int mxD = r[0].first;
  REP(i, ssize(r)) r[i].first = min(i, mxD) 1;
  };
  function<void (vector<pair<int, int>>&, int)> expand = [&](vector<pair<int, int>>& R, int lev) {
  S[lev] = S[lev - 1] - old[lev];
  old[lev] = S[lev - 1];
  while (ssize(R)) {
  if (ssize(q) R.back().first <= ssize(qmax)) return;
  q.emplace_back(R.back().second);
  vector<pair<int, int>> T;
  for(auto [_, v] : R) if (e[R.back().second][v]) T.emplace_back(0, v);
  if (ssize(T)) {
  if (S[lev] / pk < limit) init(T);
  int j = 0, mxk = 1, mnk = max(ssize(qmax) - ssize(q) 1, 1);
  C[1] = C[2] = {};
  for (auto [_, v] : T) {
  int k = 1;
  while (any_of(C[k].begin(), C[k].end(), [&](int i) { return e[v][i]; })) k ;
  if (k > mxk) C[(mxk = k) 1] = {};
  if (k < mnk) T[j ].second = v;
  C[k].emplace_back(v);
  }
  if (j > 0) T[j - 1].first = 0;
  FOR(k, mnk, mxk) for (int i : C[k]) T[j ] = {k, i};
  expand(T, lev 1);
  } else if (ssize(q) > ssize(qmax)) qmax = q;
  q.pop_back(), R.pop_back();
  }
  };
  init(V), expand(V, 1); return qmax;
 }
diff --git a/code/graph/max-clique/test.cpp b/code/graph/max-clique/test.cpp
@@ -0,0 1,42 @@
 #include "../../utils/testing/test-wrapper.cpp"
 #include "main.cpp"
 
 void test() {
  int n = rd(1, 12);
  vector<bitset<max_n>> graph(n);
  int m = rd(0, n * n);
  while(m --> 0) {
  int v = rd(0, n - 1);
  int u = rd(0, n - 1);
  if(v == u)
  continue;
  graph[v][u] = graph[u][v] = true;
  }
  debug(n);
  REP(v, n)
  REP(u, n)
  debug(v, u, graph[v][u]);
 
  auto max_clique = get_max_clique(graph);
 
  auto is_ok = [&](vector<int> v) {
  REP(i, ssize(v))
  REP(j, i)
  if(not graph[v[i]][v[j]])
  return false;
  return true;
  };
 
  int best_brute = 0;
  REP(mask, 1 << n) {
  vector<int> v;
  REP(i, n)
  if((mask >> i) & 1)
  v.emplace_back(i);
  if(is_ok(v))
  best_brute = max(best_brute, __builtin_popcount(mask));
  }
 
  assert(ssize(max_clique) == best_brute);
  assert(is_ok(max_clique));
 }