solution.cpp

#include "solution.h"
#include "Net.h"
#include "Node.h"

#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdlib>
#include <numeric>
#include <random>
#include <unordered_map>
#include <utility>
#include <vector>

using namespace std;

// ============================================================
// 多层超图划分（multilevel hypergraph partitioning）
//   heavy-edge matching 粗化 + 最粗层初始划分 + 逐层 FM 精化
// 另保留单层 FM baseline（mode = "fm"）用于实验对比
// ============================================================
namespace mlpart {

static inline long long absll(long long x) { return x < 0 ? -x : x; }

// ---------------- 内部超图：CSR 表示 ----------------
struct HG {
    int n = 0, m = 0;                  // 顶点数 / 网数
    vector<int> netPtr, netPins;       // 网 -> 引脚(顶点)
    vector<int> nodePtr, nodeNets;     // 顶点 -> 关联网
    vector<int> nodeW, netW;           // 顶点权重 / 网权重
    long long totW = 0;                // 顶点总权重

    int netSize(int e) const { return netPtr[e + 1] - netPtr[e]; }

    void buildNodeIncidence() {        // 由 netPins 反建 nodeNets
        nodePtr.assign(n + 1, 0);
        for (int p : netPins) nodePtr[p + 1]++;
        for (int i = 0; i < n; ++i) nodePtr[i + 1] += nodePtr[i];
        nodeNets.assign(netPins.size(), 0);
        vector<int> pos(nodePtr.begin(), nodePtr.end() - 1);
        for (int e = 0; e < m; ++e)
            for (int k = netPtr[e]; k < netPtr[e + 1]; ++k)
                nodeNets[pos[netPins[k]]++] = e;
    }
};

// 割代价 = 跨越两侧的网的权重和（用于最终核验）
static long long cutSize(const HG &g, const vector<int> &part) {
    long long cut = 0;
    for (int e = 0; e < g.m; ++e) {
        bool h0 = false, h1 = false;
        for (int k = g.netPtr[e]; k < g.netPtr[e + 1]; ++k) {
            if (part[g.netPins[k]] == 0) h0 = true; else h1 = true;
            if (h0 && h1) { cut += g.netW[e]; break; }
        }
    }
    return cut;
}

// ---------------- FM 精化器（增益桶/平衡约束/回滚） ----------------
class FMRefiner {
public:
    FMRefiner(const HG &g, long long lo, long long hi) : g(g), lo(lo), hi(hi) {}

    long long refine(vector<int> &part, int maxPasses) {
        n = g.n; pp = &part;
        long long maxg = 0;                      // 最大可能 |gain| = 最大加权度
        for (int v = 0; v < n; ++v) {
            long long s = 0;
            for (int k = g.nodePtr[v]; k < g.nodePtr[v + 1]; ++k)
                s += g.netW[g.nodeNets[k]];
            maxg = max(maxg, s);
        }
        off = (int)maxg; nb = 2 * off + 1;
        nxt.assign(n, -1); prv.assign(n, -1);
        gain.assign(n, 0); locked.assign(n, 0);
        cnt0.assign(g.m, 0); cnt1.assign(g.m, 0);
        head[0].assign(nb, -1); head[1].assign(nb, -1);

        partW[0] = partW[1] = 0;
        for (int v = 0; v < n; ++v) partW[part[v]] += g.nodeW[v];

        long long cut = -1;
        for (int p = 0; p < maxPasses; ++p)
            if (doPass(cut) <= 0) break;         // 一轮无改进则停止
        return cut;
    }

private:
    const HG &g;
    long long lo, hi;                            // 平衡约束 [lo, hi]
    int n = 0, off = 0, nb = 0;
    vector<int> *pp = nullptr;
    vector<int> nxt, prv, gain, cnt0, cnt1;
    vector<char> locked;
    vector<int> head[2];
    int maxPtr[2];
    long long partW[2];
    vector<int> moves;

    void insertNode(int v) {
        int s = (*pp)[v], idx = gain[v] + off;
        prv[v] = -1; nxt[v] = head[s][idx];
        if (nxt[v] != -1) prv[nxt[v]] = v;
        head[s][idx] = v;
        if (idx > maxPtr[s]) maxPtr[s] = idx;
    }
    void removeNode(int v) {
        int s = (*pp)[v], idx = gain[v] + off;
        if (prv[v] != -1) nxt[prv[v]] = nxt[v]; else head[s][idx] = nxt[v];
        if (nxt[v] != -1) prv[nxt[v]] = prv[v];
        nxt[v] = prv[v] = -1;
    }
    void addGain(int v, int d) { removeNode(v); gain[v] += d; insertNode(v); }

    // s 侧增益桶中找满足平衡约束的最高增益顶点（限制扫描深度防退化）
    int topFeasible(int s) {
        while (maxPtr[s] >= 0 && head[s][maxPtr[s]] == -1) --maxPtr[s];
        int scanned = 0;
        for (int gi = maxPtr[s]; gi >= 0; --gi)
            for (int v = head[s][gi]; v != -1; v = nxt[v]) {
                if (++scanned > 64) return -1;
                long long w = g.nodeW[v];
                if (partW[s] - w >= lo && partW[1 - s] + w <= hi) return v;
            }
        return -1;
    }

    // 移动 v: F -> T，按 FM 标准四规则增量更新邻居增益
    void applyMove(int v, int F, int T) {
        vector<int> &part = *pp;
        vector<int> &cF = F ? cnt1 : cnt0;
        vector<int> &cT = F ? cnt0 : cnt1;
        for (int k = g.nodePtr[v]; k < g.nodePtr[v + 1]; ++k) {
            int e = g.nodeNets[k], w = g.netW[e];
            if (cT[e] == 0) {                    // 移动前 T 侧无引脚
                for (int p = g.netPtr[e]; p < g.netPtr[e + 1]; ++p) {
                    int u = g.netPins[p];
                    if (!locked[u]) addGain(u, +w);
                }
            } else if (cT[e] == 1) {             // T 侧唯一引脚
                for (int p = g.netPtr[e]; p < g.netPtr[e + 1]; ++p) {
                    int u = g.netPins[p];
                    if (part[u] == T) { if (!locked[u]) addGain(u, -w); break; }
                }
            }
            --cF[e]; ++cT[e];
            if (cF[e] == 0) {                    // 移动后 F 侧无引脚
                for (int p = g.netPtr[e]; p < g.netPtr[e + 1]; ++p) {
                    int u = g.netPins[p];
                    if (!locked[u]) addGain(u, -w);
                }
            } else if (cF[e] == 1) {             // F 侧只剩一个引脚
                for (int p = g.netPtr[e]; p < g.netPtr[e + 1]; ++p) {
                    int u = g.netPins[p];
                    if (part[u] == F && u != v) { if (!locked[u]) addGain(u, +w); break; }
                }
            }
        }
    }

    // 一轮 pass：全部入桶 -> 依次移动并锁定 -> 回滚到割最小前缀
    long long doPass(long long &cutInOut) {
        vector<int> &part = *pp;
        fill(cnt0.begin(), cnt0.end(), 0);
        fill(cnt1.begin(), cnt1.end(), 0);
        long long cur = 0;
        for (int e = 0; e < g.m; ++e) {
            for (int k = g.netPtr[e]; k < g.netPtr[e + 1]; ++k) {
                if (part[g.netPins[k]] == 0) cnt0[e]++; else cnt1[e]++;
            }
            if (cnt0[e] > 0 && cnt1[e] > 0) cur += g.netW[e];
        }
        const long long startCut = cur;

        fill(head[0].begin(), head[0].end(), -1);
        fill(head[1].begin(), head[1].end(), -1);
        maxPtr[0] = maxPtr[1] = -1;
        fill(locked.begin(), locked.end(), 0);
        for (int v = 0; v < n; ++v) {            // 初始增益
            int F = part[v];
            vector<int> &cF = F ? cnt1 : cnt0;
            vector<int> &cT = F ? cnt0 : cnt1;
            long long gn = 0;
            for (int k = g.nodePtr[v]; k < g.nodePtr[v + 1]; ++k) {
                int e = g.nodeNets[k];
                if (cT[e] == 0) gn -= g.netW[e]; // 移过去会割开本来不割的网
                if (cF[e] == 1) gn += g.netW[e]; // 移过去会解开本来割的网
            }
            gain[v] = (int)gn;
            insertNode(v);
        }

        moves.clear();
        long long best = cur, bestBal = absll(partW[0] - partW[1]);
        int bestIdx = -1, sinceBest = 0;
        const int limit = max(300, n / 20);      // 连续无改进步数上限(早停)
        while (true) {
            int c0 = topFeasible(0), c1 = topFeasible(1), v;
            if (c0 != -1 && c1 != -1) {
                if (gain[c0] != gain[c1]) v = gain[c0] > gain[c1] ? c0 : c1;
                else v = (partW[0] >= partW[1]) ? c0 : c1;   // 平局从重侧移出
            } else v = (c0 != -1) ? c0 : c1;
            if (v == -1) break;

            int F = part[v], T = 1 - F;
            removeNode(v); locked[v] = 1;
            applyMove(v, F, T);
            partW[F] -= g.nodeW[v]; partW[T] += g.nodeW[v];
            cur -= gain[v];
            part[v] = T;
            moves.push_back(v);

            long long bal = absll(partW[0] - partW[1]);
            if (cur < best || (cur == best && bal < bestBal)) {
                best = cur; bestBal = bal;
                bestIdx = (int)moves.size() - 1; sinceBest = 0;
            } else if (++sinceBest > limit) break;
        }
        for (int i = (int)moves.size() - 1; i > bestIdx; --i) {  // 回滚
            int v = moves[i];
            partW[part[v]] -= g.nodeW[v];
            part[v] ^= 1;
            partW[part[v]] += g.nodeW[v];
        }
        cutInOut = best;
        return startCut - best;
    }
};

// ---------------- 粗化：heavy-edge matching ----------------
static HG coarsen(const HG &g, vector<int> &cmap, mt19937 &rng, long long maxW) {
    const int NET_LIMIT = 500;                   // 评分时跳过超大网
    int n = g.n;
    vector<int> match(n, -1), order(n), touched;
    iota(order.begin(), order.end(), 0);
    shuffle(order.begin(), order.end(), rng);
    vector<double> score(n, 0.0);

    for (int u : order) {
        if (match[u] != -1) continue;
        touched.clear();
        for (int k = g.nodePtr[u]; k < g.nodePtr[u + 1]; ++k) {
            int e = g.nodeNets[k], sz = g.netSize(e);
            if (sz < 2 || sz > NET_LIMIT) continue;
            double w = (double)g.netW[e] / (sz - 1);
            for (int p = g.netPtr[e]; p < g.netPtr[e + 1]; ++p) {
                int v = g.netPins[p];
                if (v == u || match[v] != -1) continue;
                if ((long long)g.nodeW[u] + g.nodeW[v] > maxW) continue;
                if (score[v] == 0.0) touched.push_back(v);
                score[v] += w;
            }
        }
        int best = -1; double bs = 0;
        for (int v : touched)
            if (score[v] > bs || (score[v] == bs && best != -1 && g.nodeW[v] < g.nodeW[best]))
                { bs = score[v]; best = v; }
        for (int v : touched) score[v] = 0.0;
        match[u] = (best == -1) ? u : best;
        if (best != -1) match[best] = u;
    }

    cmap.assign(n, -1);                          // 分配粗顶点编号
    int cn = 0;
    for (int u = 0; u < n; ++u) {
        if (cmap[u] != -1) continue;
        cmap[u] = cn;
        cmap[match[u]] = cn;
        ++cn;
    }

    HG cg;
    cg.n = cn; cg.totW = g.totW;
    cg.nodeW.assign(cn, 0);
    for (int u = 0; u < n; ++u) cg.nodeW[cmap[u]] += g.nodeW[u];

    // 构造粗网：引脚映射去重、丢单引脚网、哈希合并平行网(权重累加)
    cg.netPtr.push_back(0);
    unordered_map<unsigned long long, vector<int>> table;
    vector<int> tmp;
    for (int e = 0; e < g.m; ++e) {
        tmp.clear();
        for (int k = g.netPtr[e]; k < g.netPtr[e + 1]; ++k)
            tmp.push_back(cmap[g.netPins[k]]);
        sort(tmp.begin(), tmp.end());
        tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
        if ((int)tmp.size() <= 1) continue;
        unsigned long long h = 1469598103934665603ull;
        for (int x : tmp) { h ^= (unsigned long long)(x + 1); h *= 1099511628211ull; }
        bool dup = false;
        for (int ce : table[h]) {
            int b = cg.netPtr[ce], len = cg.netPtr[ce + 1] - b;
            if (len == (int)tmp.size() &&
                equal(tmp.begin(), tmp.end(), cg.netPins.begin() + b)) {
                cg.netW[ce] += g.netW[e]; dup = true; break;
            }
        }
        if (!dup) {
            table[h].push_back(cg.m++);
            cg.netPins.insert(cg.netPins.end(), tmp.begin(), tmp.end());
            cg.netPtr.push_back((int)cg.netPins.size());
            cg.netW.push_back(g.netW[e]);
        }
    }
    cg.buildNodeIncidence();
    return cg;
}

// ---------------- 初始划分 ----------------
// 随机种子 BFS 贪心生长到一半重量（最粗层用）
static vector<int> growInit(const HG &g, mt19937 &rng) {
    vector<int> part(g.n, 1), order(g.n), bfs;
    iota(order.begin(), order.end(), 0);
    shuffle(order.begin(), order.end(), rng);
    vector<char> visN(g.n, 0), visE(g.m, 0);
    long long w0 = 0, half = g.totW / 2;
    size_t oi = 0, qh = 0;
    while (w0 < half) {
        int v;
        if (qh < bfs.size()) v = bfs[qh++];
        else {
            while (oi < order.size() && visN[order[oi]]) ++oi;
            if (oi == order.size()) break;
            v = order[oi]; visN[v] = 1;
        }
        part[v] = 0; w0 += g.nodeW[v];
        if (w0 >= half) break;
        for (int k = g.nodePtr[v]; k < g.nodePtr[v + 1]; ++k) {
            int e = g.nodeNets[k];
            if (visE[e]) continue;
            visE[e] = 1;
            for (int p = g.netPtr[e]; p < g.netPtr[e + 1]; ++p) {
                int u = g.netPins[p];
                if (!visN[u]) { visN[u] = 1; bfs.push_back(u); }
            }
        }
    }
    return part;
}

// 随机平衡初始划分（单层 FM baseline 用）
static vector<int> randInit(const HG &g, mt19937 &rng) {
    vector<int> part(g.n, 1), order(g.n);
    iota(order.begin(), order.end(), 0);
    shuffle(order.begin(), order.end(), rng);
    long long w0 = 0, half = g.totW / 2;
    for (int v : order) {
        if (w0 >= half) break;
        part[v] = 0; w0 += g.nodeW[v];
    }
    return part;
}

// ---------------- 顶层驱动 ----------------
static vector<int> multilevel(const HG &g0, double eps, unsigned seed, long long &cutOut) {
    mt19937 rng(seed);
    const long long W = g0.totW;
    const long long hi = (long long)floor((0.5 + eps) * (double)W);
    const long long lo = W - hi;
    const long long maxClusterW = (W / 100 > 1) ? W / 100 : 1;  // 簇重<=1%总重,保证eps=2%可行
    const int COARSEST = 160;

    vector<HG> levels; levels.push_back(g0);
    vector<vector<int>> maps;
    while (levels.back().n > COARSEST && (int)levels.size() < 50) {
        vector<int> cmap;
        HG cg = coarsen(levels.back(), cmap, rng, maxClusterW);
        if (cg.n >= (int)(0.97 * levels.back().n)) break;       // 收缩停滞
        levels.push_back(std::move(cg));
        maps.push_back(std::move(cmap));
    }

    // 最粗层：多次初始划分+FM，取最优
    HG &cg = levels.back();
    FMRefiner cref(cg, lo, hi);
    vector<int> part; long long cut = LLONG_MAX;
    for (int t = 0; t < 10; ++t) {
        vector<int> p = growInit(cg, rng);
        long long c = cref.refine(p, 20);
        if (c < cut) { cut = c; part = std::move(p); }
    }

    // 逐层投影回细层并 FM 精化
    for (int l = (int)levels.size() - 2; l >= 0; --l) {
        vector<int> fine(levels[l].n);
        for (int v = 0; v < levels[l].n; ++v) fine[v] = part[maps[l][v]];
        FMRefiner ref(levels[l], lo, hi);
        cut = ref.refine(fine, l == 0 ? 8 : 6);
        part = std::move(fine);
    }
    cutOut = cut;
    return part;
}

static vector<int> singleLevelFM(const HG &g, double eps, unsigned seed, long long &cutOut) {
    mt19937 rng(seed);
    const long long hi = (long long)floor((0.5 + eps) * (double)g.totW);
    const long long lo = g.totW - hi;
    vector<int> part = randInit(g, rng);
    FMRefiner ref(g, lo, hi);
    cutOut = ref.refine(part, 20);
    return part;
}

} // namespace mlpart

// ============================================================
// Solution 成员函数
// ============================================================
void Solution::read_benchmark(Graph &graph, string benchmark_name) {
    ifstream file(benchmark_name);
    if(!file.is_open()) {
        cerr << "Failed to open the file!" << endl;
        exit(-1);
    }
    int edge_num, node_num;
    string line;
    getline(file >> ws, line);
    istringstream iss(line);
    iss >> edge_num;
    iss >> node_num;
    edge_num_ = edge_num;        // 记录声明的规模(孤立点不会出现在Graph里,
    node_num_ = node_num;        // 但输出文件和平衡约束都必须覆盖全部顶点)

    for(int i = 0; i < edge_num; i++) {
        getline(file, line);
        istringstream iss2(line);
        int node_id;
        Net *net = graph.add_net(i);
        while(iss2 >> node_id) {
            Node *node = graph.get_or_create_node(node_id);
            node->add_net(net);
            net->add_node(node);
        }
    }
    file.close();
    cout << "Declared: " << edge_num_ << " nets, " << node_num_ << " nodes" << endl;
}

void Solution::my_partition_algorithm(Graph &graph, set<int> &X, set<int> &Y,
                                      const string &mode, int runs, unsigned seed) {
    using namespace mlpart;
    if (runs < 1) runs = 1;

    // Graph -> CSR 超图（顶点 1-based -> 内部 0-based；网内引脚去重；丢弃单引脚网）
    HG g;
    g.n = node_num_;
    g.nodeW.assign(g.n, 1);
    g.totW = g.n;
    g.netPtr.push_back(0);
    vector<int> stamp(g.n, -1);
    int eid = 0;
    for (Net *net : graph.get_nets()) {
        size_t before = g.netPins.size();
        for (Node *nd : net->get_nodes()) {
            int id = nd->get_index() - 1;
            if (id < 0 || id >= g.n) continue;
            if (stamp[id] == eid) continue;      // 同一条网内重复顶点去重
            stamp[id] = eid;
            g.netPins.push_back(id);
        }
        if (g.netPins.size() - before <= 1) {
            g.netPins.resize(before);            // 单引脚网不可能被割,内部丢弃
        } else {
            g.netPtr.push_back((int)g.netPins.size());
            g.netW.push_back(1);
            g.m++;
        }
        eid++;
    }
    g.buildNodeIncidence();

    const double eps = 0.02;
    long long bestCut = LLONG_MAX;
    vector<int> bestPart;
    for (int r = 0; r < runs; ++r) {
        long long cut = 0;
        unsigned s = seed + 97u * (unsigned)r;
        vector<int> part = (mode == "fm") ? singleLevelFM(g, eps, s, cut)
                                          : multilevel(g, eps, s, cut);
        cout << "[" << mode << " run " << r << "] cut = " << cut << endl;
        if (cut < bestCut) { bestCut = cut; bestPart = std::move(part); }
    }
    part_ = std::move(bestPart);
    cout << "best cut = " << bestCut
         << " (verified = " << cutSize(g, part_) << ")" << endl;

    X.clear(); Y.clear();
    for (int v = 0; v < g.n; ++v) {
        if (part_[v] == 0) X.insert(v + 1);      // 输出 1-based,与 evaluate 对齐
        else               Y.insert(v + 1);
    }
}

string Solution::write_partition(const string &benchmark_name) const {
    string base = benchmark_name;
    size_t slash = base.find_last_of("/\\");
    if (slash != string::npos) base = base.substr(slash + 1);
    size_t dot = base.find_last_of('.');
    if (dot != string::npos) base = base.substr(0, dot);
    string out_name = base + "_partition.txt";
    ofstream out(out_name);
    for (int p : part_) out << p << '\n';
    cout << "Partition written to " << out_name << endl;
    return out_name;
}