independent_set_clique.cpp

// independent_set_clique.cpp
// -----------------------------------------------------------------
// Independent Set 與 Clique：一體兩面的 NP-Complete 問題
//   1. 最大獨立集：位元枚舉（n<=20 教學版）+ 分支剪枝
//   2. 最大團：Bron–Kerbosch（含 pivot）
//   3. 三位一體驗證：IS(G) = Clique(補圖 G') = n - VC(G)
//
// Compile: g++ -std=c++17 -O2 -Wall -Wextra -o independent_set_clique independent_set_clique.cpp
// -----------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 鄰接以 bitmask 儲存：adj[v] 的第 u 位 = 1 表示 u,v 相鄰（n <= 30）
struct Graph {
    int n;
    vector<unsigned> adj;
    Graph(int n_) : n(n_), adj(n_, 0) {}
    void addEdge(int u, int v) {
        adj[u] |= 1u << v;
        adj[v] |= 1u << u;
    }
    Graph complement() const {
        Graph g(n);
        unsigned full = (n == 32) ? ~0u : ((1u << n) - 1);
        for (int v = 0; v < n; ++v)
            g.adj[v] = full & ~adj[v] & ~(1u << v);   // 去掉自環
        return g;
    }
};

// ---------- 1a. 最大獨立集：枚舉所有子集（O(2^n)，n 小用） ----------
pair<int, unsigned> maxISBrute(const Graph& g) {
    int best = 0;
    unsigned bestSet = 0;
    for (unsigned s = 0; s < (1u << g.n); ++s) {
        bool ok = true;
        for (int v = 0; v < g.n && ok; ++v)
            if ((s >> v) & 1)
                if (g.adj[v] & s) ok = false;          // v 的鄰居也在集合裡
        if (ok && __builtin_popcount(s) > best) {
            best = __builtin_popcount(s);
            bestSet = s;
        }
    }
    return {best, bestSet};
}

// ---------- 1b. 最大獨立集：分支剪枝 ----------
// 分支規則：挑一個度數最大的點 v -> 不選 v（在剩餘圖刪 v）或選 v（刪 v 和鄰居）
class MaxISBranch {
    const Graph& g;
public:
    long long nodes = 0;
    MaxISBranch(const Graph& g_) : g(g_) {}

    pair<int, unsigned> solve() {
        nodes = 0;
        unsigned full = (g.n == 32) ? ~0u : ((1u << g.n) - 1);
        return dfs(full);
    }
private:
    pair<int, unsigned> dfs(unsigned remain) {
        ++nodes;
        if (!remain) return {0, 0};
        // 找 remain 中度數最大的點
        int best = -1, bestDeg = -1;
        for (int v = 0; v < g.n; ++v)
            if ((remain >> v) & 1) {
                int d = __builtin_popcount(g.adj[v] & remain);
                if (d > bestDeg) { bestDeg = d; best = v; }
            }
        if (bestDeg == 0) {                            // 剩下的全是孤立點
            return {__builtin_popcount(remain), remain};
        }
        // 分支 1：不選 best
        auto [c1, s1] = dfs(remain & ~(1u << best));
        // 分支 2：選 best（刪掉 best 和其鄰居）
        auto [c2, s2] = dfs(remain & ~(1u << best) & ~g.adj[best]);
        ++c2;
        s2 |= 1u << best;
        return c1 >= c2 ? make_pair(c1, s1) : make_pair(c2, s2);
    }
};

// ---------- 2. 最大團：Bron–Kerbosch with pivot ----------
class BronKerbosch {
    const Graph& g;
public:
    int best = 0;
    unsigned bestClique = 0;
    long long calls = 0;
    BronKerbosch(const Graph& g_) : g(g_) {}

    void run() {
        best = 0; bestClique = 0; calls = 0;
        unsigned full = (g.n == 32) ? ~0u : ((1u << g.n) - 1);
        expand(0, full, 0);
    }
private:
    // R = 目前的團, P = 還能加入的候選, X = 已處理過（避免重複）
    void expand(unsigned R, unsigned P, unsigned X) {
        ++calls;
        if (!P && !X) {                                 // R 是極大團
            if (__builtin_popcount(R) > best) {
                best = __builtin_popcount(R);
                bestClique = R;
            }
            return;
        }
        // pivot：從 P|X 挑鄰居最多的 u，只展開 P \ N(u)
        unsigned PX = P | X;
        int pivot = -1, bestCover = -1;
        for (int v = 0; v < g.n; ++v)
            if ((PX >> v) & 1) {
                int c = __builtin_popcount(g.adj[v] & P);
                if (c > bestCover) { bestCover = c; pivot = v; }
            }
        unsigned cand = P & ~g.adj[pivot];
        for (int v = 0; v < g.n; ++v)
            if ((cand >> v) & 1) {
                expand(R | (1u << v), P & g.adj[v], X & g.adj[v]);
                P &= ~(1u << v);
                X |= 1u << v;
            }
    }
};

static void printSet(unsigned s, int n) {
    cout << "{";
    bool first = true;
    for (int v = 0; v < n; ++v)
        if ((s >> v) & 1) {
            cout << (first ? "" : ",") << v;
            first = false;
        }
    cout << "}";
}

int main() {
    // ---- 範例 1：C5 環（IS=2, Clique=2） ----
    cout << "=== Example 1: cycle C5 ===\n";
    Graph c5(5);
    for (int i = 0; i < 5; ++i) c5.addEdge(i, (i + 1) % 5);
    auto [is1, s1] = maxISBrute(c5);
    cout << "max independent set = " << is1 << "  ";
    printSet(s1, 5);
    BronKerbosch bk1(c5);
    bk1.run();
    cout << "\nmax clique = " << bk1.best << "  ";
    printSet(bk1.bestClique, 5);
    cout << "\n\n";

    // ---- 範例 2：三位一體 IS(G) = Clique(G') = n - VC(G) ----
    cout << "=== Example 2: trinity on Petersen graph ===\n";
    Graph pet(10);
    int petE[][2] = {{0,1},{1,2},{2,3},{3,4},{4,0},
                     {5,7},{7,9},{9,6},{6,8},{8,5},
                     {0,5},{1,6},{2,7},{3,8},{4,9}};
    for (auto& e : petE) pet.addEdge(e[0], e[1]);
    auto [isP, setP] = maxISBrute(pet);
    Graph petComp = pet.complement();        // 注意：要用具名變數，避免懸空參考
    BronKerbosch bkC(petComp);
    bkC.run();
    cout << "max IS in G           = " << isP << "  ";
    printSet(setP, 10);
    cout << "\nmax clique in G'      = " << bkC.best << "  ";
    printSet(bkC.bestClique, 10);
    cout << "\nn - maxIS = 10 - " << isP << " = " << 10 - isP
         << "  (= minimum vertex cover size)\n\n";

    // ---- 範例 3：分支剪枝 vs 暴力枚舉 ----
    cout << "=== Example 3: branch-and-prune vs brute force (n=20) ===\n";
    Graph g20(20);
    // 決定性的偽隨機圖
    unsigned seed = 123456789;
    auto nextRand = [&seed]() {
        seed = seed * 1103515245 + 12345;
        return (seed >> 16) & 0x7fff;
    };
    int edges = 0;
    for (int u = 0; u < 20; ++u)
        for (int v = u + 1; v < 20; ++v)
            if (nextRand() % 100 < 25) {               // 邊密度 25%
                g20.addEdge(u, v);
                ++edges;
            }
    auto [isB, setB] = maxISBrute(g20);
    MaxISBranch mb(g20);
    auto [isBr, setBr] = mb.solve();
    cout << "n=20, |E|=" << edges << "\n";
    cout << "brute force  : maxIS=" << isB << " (2^20 = 1,048,576 subsets)\n";
    cout << "branch+prune : maxIS=" << isBr << " (nodes=" << mb.nodes << ")\n";
    cout << "agree = " << (isB == isBr ? "yes" : "NO!") << "\n\n";
    (void)setB; (void)setBr;

    // ---- 範例 4：社群偵測情境——找互相認識的最大群體 ----
    cout << "=== Example 4: find the largest group of mutual friends ===\n";
    // 8 人，邊 = 互相認識
    Graph soc(8);
    int socE[][2] = {{0,1},{0,2},{1,2},{2,3},{0,3},{1,3},   // 0,1,2,3 全連 = K4
                     {3,4},{4,5},{5,6},{6,7},{4,6}};
    for (auto& e : socE) soc.addEdge(e[0], e[1]);
    BronKerbosch bkS(soc);
    bkS.run();
    cout << "max clique size = " << bkS.best << "  members ";
    printSet(bkS.bestClique, 8);
    cout << "  (BK calls=" << bkS.calls << ")\n";
    return 0;
}