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

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-04-24 02:34:04+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