graph_coloring.cpp

// graph_coloring.cpp
// -----------------------------------------------------------------
// Graph Coloring（圖著色）：
//   1. 回溯 + 剪枝：判斷 k 色可行並輸出著色
//   2. 色數（chromatic number）：從 k=1 遞增測試
//   3. 貪婪著色（Welsh-Powell：度數大者優先）——快速上界
//
// Compile: g++ -std=c++17 -O2 -Wall -Wextra -o graph_coloring graph_coloring.cpp
// -----------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

// ---------- 1. 回溯 k-著色 ----------
class ColoringBacktrack {
    const vector<vector<int>>& adj;
    int n, k;
    vector<int> color;
public:
    long long nodes = 0;
    ColoringBacktrack(const vector<vector<int>>& g)
        : adj(g), n((int)g.size()) {}

    // 回傳 {可行?, 著色方案}
    pair<bool, vector<int>> solve(int k_) {
        k = k_;
        color.assign(n, -1);
        nodes = 0;
        bool ok = dfs(0);
        return {ok, color};
    }
private:
    bool feasible(int u, int c) {
        for (int v : adj[u])
            if (color[v] == c) return false;
        return true;
    }
    bool dfs(int u) {
        ++nodes;
        if (u == n) return true;
        for (int c = 0; c < k; ++c) {
            if (!feasible(u, c)) continue;           // 剪枝
            color[u] = c;
            if (dfs(u + 1)) return true;
            color[u] = -1;
        }
        return false;
    }
};

// ---------- 2. 色數：遞增 k ----------
int chromaticNumber(const vector<vector<int>>& g) {
    ColoringBacktrack cb(g);
    for (int k = 1; k <= (int)g.size(); ++k)
        if (cb.solve(k).first) return k;
    return (int)g.size();
}

// ---------- 3. 貪婪著色（Welsh-Powell 順序） ----------
pair<int, vector<int>> greedyColoring(const vector<vector<int>>& g) {
    int n = (int)g.size();
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int a, int b) {
        return g[a].size() > g[b].size();            // 度數遞減
    });
    vector<int> color(n, -1);
    int used = 0;
    for (int u : order) {
        vector<bool> ban(n, false);
        for (int v : g[u])
            if (color[v] != -1) ban[color[v]] = true;
        int c = 0;
        while (ban[c]) ++c;
        color[u] = c;
        used = max(used, c + 1);
    }
    return {used, color};
}

static vector<vector<int>> buildGraph(int n, const vector<pair<int,int>>& edges) {
    vector<vector<int>> g(n);
    for (auto [u, v] : edges) {
        g[u].push_back(v);
        g[v].push_back(u);
    }
    return g;
}

static void report(const string& name, const vector<vector<int>>& g) {
    ColoringBacktrack cb(g);
    int chi = chromaticNumber(g);
    auto [greedyK, gc] = greedyColoring(g);
    auto [ok, col] = cb.solve(chi);
    cout << name << ": chromatic number = " << chi
         << " | greedy used = " << greedyK
         << (greedyK > chi ? "  (greedy overshoots!)" : "") << "\n";
    if (ok) {
        cout << "  optimal coloring:";
        for (int i = 0; i < (int)col.size(); ++i)
            cout << " v" << i << "=c" << col[i];
        cout << "\n";
    }
    (void)gc;
}

int main() {
    // ---- 範例 1：三角形 K3（色數 3） ----
    cout << "=== Example 1: triangle K3 ===\n";
    report("K3", buildGraph(3, {{0,1},{1,2},{2,0}}));
    cout << "\n";

    // ---- 範例 2：偶環 C4 vs 奇環 C5 ----
    cout << "=== Example 2: even cycle C4 (bipartite) vs odd cycle C5 ===\n";
    report("C4", buildGraph(4, {{0,1},{1,2},{2,3},{3,0}}));
    report("C5", buildGraph(5, {{0,1},{1,2},{2,3},{3,4},{4,0}}));
    cout << "\n";

    // ---- 範例 3：Petersen 圖（著名例子，色數 3） ----
    cout << "=== Example 3: Petersen graph ===\n";
    vector<pair<int,int>> pet = {
        {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}           // 輻條
    };
    report("Petersen", buildGraph(10, pet));
    cout << "\n";

    // ---- 範例 4：排課情境（衝突圖著色 = 時段分配） ----
    cout << "=== Example 4: exam scheduling as coloring ===\n";
    // 6 門課，邊 = 有共同學生（不能同時段）
    // 課程: 0=微積分 1=線代 2=物理 3=化學 4=程設 5=英文
    vector<pair<int,int>> conflicts = {
        {0,1},{0,2},{1,2},{1,3},{2,4},{3,4},{3,5},{4,5}
    };
    auto g = buildGraph(6, conflicts);
    int chi = chromaticNumber(g);
    ColoringBacktrack cb(g);
    auto [ok, col] = cb.solve(chi);
    const char* names[] = {"Calculus","LinAlg","Physics","Chem","Prog","English"};
    cout << "6 courses, 8 conflicts -> minimum time slots = " << chi << "\n";
    if (ok)
        for (int i = 0; i < 6; ++i)
            cout << "  slot " << col[i] << ": " << names[i] << "\n";
    return 0;
}