Count Independent Sets
(src/graph/count_independent_set.hpp)

• View this file on GitHub
• Last update: 2023-11-03 03:12:33+09:00
• Include: #include "src/graph/count_independent_set.hpp"

概要

$n$ 頂点の自己ループを含まないグラフ $G$ の独立集合の個数を数える． 計算量は $\mathrm{O}(n 1.381^n)$．

unsigned long long を使って計算している都合上，$n < 64$ という制約を課している（オーバーフローさせたり mod を取ったりでそれ以上の値でも計算自体は可能）．

Links

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

Required by

• Count Cliques (src/graph/count_clique.hpp)

Code

#pragma once
#include <cassert>
#include <vector>

namespace internal {

unsigned long long f(unsigned long long,
                     const std::vector<unsigned long long>&,
                     const std::vector<unsigned long long>&,
                     const std::vector<unsigned long long>&);
unsigned long long g(unsigned long long,
                     const std::vector<unsigned long long>&,
                     const std::vector<unsigned long long>&,
                     const std::vector<unsigned long long>&);

unsigned long long f(unsigned long long S,
                     const std::vector<unsigned long long>& G,
                     const std::vector<unsigned long long>& path,
                     const std::vector<unsigned long long>& cycle) {
    unsigned long long res = 1;
    for (; S;) {
        int v = __builtin_ctzll(S);
        unsigned long long comp = 1ULL << v, seen = 0;
        for (; comp & ~seen;) {
            int u = __builtin_ctzll(comp & ~seen);
            comp |= G[u] & S;
            seen |= 1ULL << u;
        }
        res *= g(comp, G, path, cycle);
        S &= ~comp;
    }
    return res;
}

unsigned long long g(unsigned long long S,
                     const std::vector<unsigned long long>& G,
                     const std::vector<unsigned long long>& path,
                     const std::vector<unsigned long long>& cycle) {
    if (!S) return 1;
    if (!(S & (S - 1))) return 2;
    int maxi = -1, argmax = -1, one = 0, tot = __builtin_popcountll(S);
    for (unsigned long long T = S; T;) {
        int v = __builtin_ctzll(T);
        T &= ~(1ULL << v);
        int deg = __builtin_popcountll(G[v] & S);
        if (maxi < deg) {
            maxi = deg;
            argmax = v;
        }
        one += (deg == 1);
    }
    if (maxi <= 2) return one ? path[tot] : cycle[tot];
    S &= ~(1ULL << argmax);
    return f(S, G, path, cycle) + f(S & ~G[argmax], G, path, cycle);
}

}  // namespace internal

unsigned long long count_independent_set(const std::vector<unsigned long long>& G) {
    int n = G.size();
    assert(n < 64);
    if (n == 0) return 1;
    std::vector<unsigned long long> path(n + 1), cycle(n + 1);
    path[0] = 1, path[1] = 2;
    for (int i = 2; i <= n; i++) path[i] = path[i - 1] + path[i - 2];
    cycle[0] = 2, cycle[1] = 1;
    for (int i = 2; i <= n; i++) cycle[i] = cycle[i - 1] + cycle[i - 2];
    return internal::f((1ULL << n) - 1, G, path, cycle);
}

#line 2 "src/graph/count_independent_set.hpp"
#include <cassert>
#include <vector>

namespace internal {

unsigned long long f(unsigned long long,
                     const std::vector<unsigned long long>&,
                     const std::vector<unsigned long long>&,
                     const std::vector<unsigned long long>&);
unsigned long long g(unsigned long long,
                     const std::vector<unsigned long long>&,
                     const std::vector<unsigned long long>&,
                     const std::vector<unsigned long long>&);

unsigned long long f(unsigned long long S,
                     const std::vector<unsigned long long>& G,
                     const std::vector<unsigned long long>& path,
                     const std::vector<unsigned long long>& cycle) {
    unsigned long long res = 1;
    for (; S;) {
        int v = __builtin_ctzll(S);
        unsigned long long comp = 1ULL << v, seen = 0;
        for (; comp & ~seen;) {
            int u = __builtin_ctzll(comp & ~seen);
            comp |= G[u] & S;
            seen |= 1ULL << u;
        }
        res *= g(comp, G, path, cycle);
        S &= ~comp;
    }
    return res;
}

unsigned long long g(unsigned long long S,
                     const std::vector<unsigned long long>& G,
                     const std::vector<unsigned long long>& path,
                     const std::vector<unsigned long long>& cycle) {
    if (!S) return 1;
    if (!(S & (S - 1))) return 2;
    int maxi = -1, argmax = -1, one = 0, tot = __builtin_popcountll(S);
    for (unsigned long long T = S; T;) {
        int v = __builtin_ctzll(T);
        T &= ~(1ULL << v);
        int deg = __builtin_popcountll(G[v] & S);
        if (maxi < deg) {
            maxi = deg;
            argmax = v;
        }
        one += (deg == 1);
    }
    if (maxi <= 2) return one ? path[tot] : cycle[tot];
    S &= ~(1ULL << argmax);
    return f(S, G, path, cycle) + f(S & ~G[argmax], G, path, cycle);
}

}  // namespace internal

unsigned long long count_independent_set(const std::vector<unsigned long long>& G) {
    int n = G.size();
    assert(n < 64);
    if (n == 0) return 1;
    std::vector<unsigned long long> path(n + 1), cycle(n + 1);
    path[0] = 1, path[1] = 2;
    for (int i = 2; i <= n; i++) path[i] = path[i - 1] + path[i - 2];
    cycle[0] = 2, cycle[1] = 1;
    for (int i = 2; i <= n; i++) cycle[i] = cycle[i - 1] + cycle[i - 2];
    return internal::f((1ULL << n) - 1, G, path, cycle);
}

Back to top page