Enumerate Cliques (クリークの列挙)
(lib/graph/enumerate_cliques.hpp)

• View this file on GitHub
• Last update: 2024-11-01 00:39:10+09:00
• Include: #include "lib/graph/enumerate_cliques.hpp"
• Link: https://www.slideshare.net/wata_orz/ss-12131479

Enumerate Cliques (クリークの列挙)

概要

グラフ $G$ について、クリークを列挙します。 クリークとは、部分グラフであって完全グラフであるようなものです。

計算量

頂点数を $V$、辺の数を $E$ とすると、$\mathrm{O}(2^{\sqrt{2E}} V)$

Verified with

• test/library_checker/graph/enumerate_cliques.test.cpp

Code

#pragma once

/**
 * @brief Enumerate Cliques (クリークの列挙)
 * @docs docs/graph/enumerate_cliques.md
 * @see https://www.slideshare.net/wata_orz/ss-12131479
 */

vector<vector<int>> enumerateCliques(vector<vector<int>> &G){
    int n = G.size();
    vector<pair<int, int>> deg(n);
    for(int i = 0; i < n; i++){
        deg[i] = {(int) G[i].size(), i};
    }

    vector<vector<bool>> adj(n, vector<bool>(n));
    for(int i = 0; i < n; i++){
        for(auto &j : G[i]){
            adj[i][j] = adj[j][i] = true;
        }
    }

    // 次数が √2m 未満かどうかで場合分け -> 次数が低い頂点から処理をしても十分高速 (O(2^(√2m) * n^2))
    sort(deg.begin(), deg.end());
    vector<vector<int>> res;
    for(int i = 0; i < n; i++){
        int cur = deg[i].second;
        vector<int> nxt;
        for(int j = 0; j < n; j++){
            if(adj[cur][j]){
                nxt.push_back(j);
            }
        }
        int d = nxt.size();
        for(int bit = 0; bit < (1 << d); bit++){
            vector<int> s = {cur};
            for(int j = 0; j < d; j++){
                if(bit & (1 << j)){
                    s.push_back(nxt[j]);
                }
            }
            bool is_ok = true;
            for(auto x : s){
                for(auto y : s){
                    if(x == y) continue;
                    if(adj[x][y] == 0){
                        is_ok = false;
                    }
                }
            }
            if(is_ok){
                res.push_back(s);
            }
        }
        for(int j = 0; j < d; j++){
            adj[cur][nxt[j]] = adj[nxt[j]][cur] = false;
        }
    }
    return res;
}

#line 2 "lib/graph/enumerate_cliques.hpp"

/**
 * @brief Enumerate Cliques (クリークの列挙)
 * @docs docs/graph/enumerate_cliques.md
 * @see https://www.slideshare.net/wata_orz/ss-12131479
 */

vector<vector<int>> enumerateCliques(vector<vector<int>> &G){
    int n = G.size();
    vector<pair<int, int>> deg(n);
    for(int i = 0; i < n; i++){
        deg[i] = {(int) G[i].size(), i};
    }

    vector<vector<bool>> adj(n, vector<bool>(n));
    for(int i = 0; i < n; i++){
        for(auto &j : G[i]){
            adj[i][j] = adj[j][i] = true;
        }
    }

    // 次数が √2m 未満かどうかで場合分け -> 次数が低い頂点から処理をしても十分高速 (O(2^(√2m) * n^2))
    sort(deg.begin(), deg.end());
    vector<vector<int>> res;
    for(int i = 0; i < n; i++){
        int cur = deg[i].second;
        vector<int> nxt;
        for(int j = 0; j < n; j++){
            if(adj[cur][j]){
                nxt.push_back(j);
            }
        }
        int d = nxt.size();
        for(int bit = 0; bit < (1 << d); bit++){
            vector<int> s = {cur};
            for(int j = 0; j < d; j++){
                if(bit & (1 << j)){
                    s.push_back(nxt[j]);
                }
            }
            bool is_ok = true;
            for(auto x : s){
                for(auto y : s){
                    if(x == y) continue;
                    if(adj[x][y] == 0){
                        is_ok = false;
                    }
                }
            }
            if(is_ok){
                res.push_back(s);
            }
        }
        for(int j = 0; j < d; j++){
            adj[cur][nxt[j]] = adj[nxt[j]][cur] = false;
        }
    }
    return res;
}

Back to top page