Enumerate Cliques(クリーク全列挙) (graph/others/enumerate-cliques.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-05-01 23:44:47+09:00
• Include: #include "graph/others/enumerate-cliques.hpp"
• Link: https://www.slideshare.net/wata_orz/ss-12131479

概要

無向グラフが与えられたとき, クリークを全列挙する.

次数が $\sqrt {2E}$ 未満の頂点 $v$ を $1$ 個選んで, 頂点 $v$ に隣接する頂点の部分集合を全て試し, $v$ を除去して再帰的に求める.

クリークの個数は高々 $2 ^ {\sqrt {2E}}$ 個.

使い方

• enumerate_clique(g): 隣接行列 g の部分グラフに含まれる全てのクリークを返す. 頂点数 $1$ もクリークとしてみなしている.

計算量

$O(2 ^ {\sqrt {2E}} V)$

Verified with

• test/verify/aoj-2306.test.cpp

Code

/**
 * @brief Enumerate Cliques(クリーク全列挙)
 * @see https://www.slideshare.net/wata_orz/ss-12131479
 *
 */
template <typename Matrix>
vector<vector<int> > enumerate_cliques(Matrix &g) {
  int N = (int)g.size(), M = 0;
  vector<int> deg(N);
  vector<vector<int> > edge(N, vector<int>(N));
  for (int i = 0; i < N; i++) {
    for (auto p : g[i]) deg[i] += p;
    M += deg[i];
  }
  int lim = (int)sqrt(M);

  vector<vector<int> > cliques;

  auto add_clique = [&](const vector<int> &rem, bool last) {
    vector<int> neighbor((int)rem.size() - last);
    for (int i = 0; i < (int)neighbor.size(); i++) {
      for (int j = 0; j < (int)neighbor.size(); j++) {
        if (i != j && !g[rem[i]][rem[j]]) neighbor[i] |= 1 << j;
      }
    }
    for (int i = 1 - last; i < (1 << neighbor.size()); i++) {
      bool ok = true;
      for (int j = 0; j < (int)neighbor.size(); j++) {
        if ((i >> j) & 1) {
          if (i & neighbor[j]) {
            ok = false;
            break;
          }
        }
      }
      if (ok) {
        vector<int> clique;
        if (last) clique.emplace_back(rem.back());
        for (int j = 0; j < (int)neighbor.size(); j++) {
          if ((i >> j) & 1) clique.emplace_back(rem[j]);
        }
        cliques.emplace_back(clique);
      }
    }
  };

  vector<int> used(N);
  queue<int> que;
  for (int i = 0; i < N; i++) {
    if (deg[i] < lim) {
      used[i] = true;
      que.emplace(i);
    }
  }
  while (!que.empty()) {
    int idx = que.front();
    que.pop();
    vector<int> rem;
    for (int k = 0; k < N; k++) {
      if (g[idx][k]) rem.emplace_back(k);
    }
    rem.emplace_back(idx);
    add_clique(rem, true);
    used[idx] = true;
    for (int k = 0; k < N; k++) {
      if (g[idx][k]) {
        g[idx][k] = false;
        g[k][idx] = false;
        --deg[k];
        if (!used[k] && deg[k] < lim) {
          used[k] = true;
          que.emplace(k);
        }
      }
    }
  }
  vector<int> rem;
  for (int i = 0; i < N; i++) {
    if (!used[i]) rem.emplace_back(i);
  }
  add_clique(rem, false);
  return cliques;
}

#line 1 "graph/others/enumerate-cliques.hpp"
/**
 * @brief Enumerate Cliques(クリーク全列挙)
 * @see https://www.slideshare.net/wata_orz/ss-12131479
 *
 */
template <typename Matrix>
vector<vector<int> > enumerate_cliques(Matrix &g) {
  int N = (int)g.size(), M = 0;
  vector<int> deg(N);
  vector<vector<int> > edge(N, vector<int>(N));
  for (int i = 0; i < N; i++) {
    for (auto p : g[i]) deg[i] += p;
    M += deg[i];
  }
  int lim = (int)sqrt(M);

  vector<vector<int> > cliques;

  auto add_clique = [&](const vector<int> &rem, bool last) {
    vector<int> neighbor((int)rem.size() - last);
    for (int i = 0; i < (int)neighbor.size(); i++) {
      for (int j = 0; j < (int)neighbor.size(); j++) {
        if (i != j && !g[rem[i]][rem[j]]) neighbor[i] |= 1 << j;
      }
    }
    for (int i = 1 - last; i < (1 << neighbor.size()); i++) {
      bool ok = true;
      for (int j = 0; j < (int)neighbor.size(); j++) {
        if ((i >> j) & 1) {
          if (i & neighbor[j]) {
            ok = false;
            break;
          }
        }
      }
      if (ok) {
        vector<int> clique;
        if (last) clique.emplace_back(rem.back());
        for (int j = 0; j < (int)neighbor.size(); j++) {
          if ((i >> j) & 1) clique.emplace_back(rem[j]);
        }
        cliques.emplace_back(clique);
      }
    }
  };

  vector<int> used(N);
  queue<int> que;
  for (int i = 0; i < N; i++) {
    if (deg[i] < lim) {
      used[i] = true;
      que.emplace(i);
    }
  }
  while (!que.empty()) {
    int idx = que.front();
    que.pop();
    vector<int> rem;
    for (int k = 0; k < N; k++) {
      if (g[idx][k]) rem.emplace_back(k);
    }
    rem.emplace_back(idx);
    add_clique(rem, true);
    used[idx] = true;
    for (int k = 0; k < N; k++) {
      if (g[idx][k]) {
        g[idx][k] = false;
        g[k][idx] = false;
        --deg[k];
        if (!used[k] && deg[k] < lim) {
          used[k] = true;
          que.emplace(k);
        }
      }
    }
  }
  vector<int> rem;
  for (int i = 0; i < N; i++) {
    if (!used[i]) rem.emplace_back(i);
  }
  add_clique(rem, false);
  return cliques;
}

Back to top page