Enumerate Cliques
(src/graph/enumerate_cliques.hpp)

• View this file on GitHub
• Last update: 2023-01-12 22:28:24+09:00
• Include: #include "src/graph/enumerate_cliques.hpp"

概要

グラフのクリークを全列挙する． 時間計算量は頂点数 $n$，辺数 $m$ として $O(2^{\sqrt{2m}} n)$ となる． あまり見ない計算量だが，$n, m \sim 200$ でも高速に動作する．

Links

• 指数時間アルゴリズム入門

Verified with

• test/yosupo/enumerate_cliques.test.cpp

Code

#pragma once
#include <queue>
#include <vector>

std::vector<std::vector<int>> enumerate_cliques(std::vector<std::vector<bool>> G) {
    int n = G.size(), m = 0;
    std::vector<int> deg(n, 0);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) deg[i] += G[i][j];
        m += deg[i];
    }
    std::vector<std::vector<int>> cliques;

    auto add_clique = [&](const std::vector<int>& cand, bool last) {
        int size = cand.size() - last;
        std::vector<int> not_adj(size);
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (i != j && !G[cand[i]][cand[j]]) {
                    not_adj[i] |= 1 << j;
                }
            }
        }
        for (int mask = 1 - last; mask < (1 << (size)); mask++) {
            bool ok = true;
            for (int i = 0; i < size; i++) {
                if ((mask >> i & 1) && (mask & not_adj[i])) {
                    ok = false;
                    break;
                }
            }
            if (!ok) continue;
            std::vector<int> clique;
            if (last) clique.emplace_back(cand.back());
            for (int i = 0; i < size; i++) {
                if (mask >> i & 1) {
                    clique.emplace_back(cand[i]);
                }
            }
            cliques.emplace_back(clique);
        }
    };

    std::vector<bool> used(n, false);
    std::queue<int> que;
    for (int i = 0; i < n; i++) {
        if (deg[i] * (deg[i] + 1) <= m) {
            used[i] = true;
            que.emplace(i);
        }
    }
    while (!que.empty()) {
        int v = que.front();
        que.pop();
        std::vector<int> cand;
        for (int u = 0; u < n; u++) {
            if (G[v][u]) {
                cand.emplace_back(u);
            }
        }
        cand.emplace_back(v);
        add_clique(cand, true);
        for (int u = 0; u < n; u++) {
            if (!G[v][u]) continue;
            G[v][u] = G[u][v] = false;
            deg[u]--;
            if (!used[u] && deg[u] * (deg[u] + 1) <= m) {
                used[u] = true;
                que.emplace(u);
            }
        }
    }
    std::vector<int> rest;
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            rest.emplace_back(i);
        }
    }
    add_clique(rest, false);
    return cliques;
}

#line 2 "src/graph/enumerate_cliques.hpp"
#include <queue>
#include <vector>

std::vector<std::vector<int>> enumerate_cliques(std::vector<std::vector<bool>> G) {
    int n = G.size(), m = 0;
    std::vector<int> deg(n, 0);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) deg[i] += G[i][j];
        m += deg[i];
    }
    std::vector<std::vector<int>> cliques;

    auto add_clique = [&](const std::vector<int>& cand, bool last) {
        int size = cand.size() - last;
        std::vector<int> not_adj(size);
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (i != j && !G[cand[i]][cand[j]]) {
                    not_adj[i] |= 1 << j;
                }
            }
        }
        for (int mask = 1 - last; mask < (1 << (size)); mask++) {
            bool ok = true;
            for (int i = 0; i < size; i++) {
                if ((mask >> i & 1) && (mask & not_adj[i])) {
                    ok = false;
                    break;
                }
            }
            if (!ok) continue;
            std::vector<int> clique;
            if (last) clique.emplace_back(cand.back());
            for (int i = 0; i < size; i++) {
                if (mask >> i & 1) {
                    clique.emplace_back(cand[i]);
                }
            }
            cliques.emplace_back(clique);
        }
    };

    std::vector<bool> used(n, false);
    std::queue<int> que;
    for (int i = 0; i < n; i++) {
        if (deg[i] * (deg[i] + 1) <= m) {
            used[i] = true;
            que.emplace(i);
        }
    }
    while (!que.empty()) {
        int v = que.front();
        que.pop();
        std::vector<int> cand;
        for (int u = 0; u < n; u++) {
            if (G[v][u]) {
                cand.emplace_back(u);
            }
        }
        cand.emplace_back(v);
        add_clique(cand, true);
        for (int u = 0; u < n; u++) {
            if (!G[v][u]) continue;
            G[v][u] = G[u][v] = false;
            deg[u]--;
            if (!used[u] && deg[u] * (deg[u] + 1) <= m) {
                used[u] = true;
                que.emplace(u);
            }
        }
    }
    std::vector<int> rest;
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            rest.emplace_back(i);
        }
    }
    add_clique(rest, false);
    return cliques;
}

Back to top page