本项目实现了一个面向 VLSI 电路网表的超图二路划分算法，目标是在满足平衡约束 ε = 2%（即每侧顶点数占比落在 48% ~ 52%）的前提下，最小化两个划分之间的割代价 （cutsize，即跨越两侧的超边数量）。
在 ISPD98 IBM01~18 全部 18 个基准电路上，本算法相比单层 FM baseline 总割代价降低 85.1%，与已知最优解的总体差距为 5.6%， 最大数据集 IBM18（约 21 万顶点）10 次独立重启总耗时不足 5 秒。
整体采用经典的多层（multilevel）框架，分三个阶段：
原图 G0 ──粗化──> G1 ──粗化──> ... ──> Gk (最粗层, ~160 个超点)
│
多次初始划分 + FM，取最优
│
G0 <──投影+FM精化── G1 <──投影+FM精化── ──┘
-
粗化（Heavy-Edge Matching） 按
score(u,v) = Σ w(e)/(|e|−1)给邻居打分，优先合并连接紧密的顶点对； 限制簇重量 ≤ 总重 1% 以保证粗层平衡可行；粗化时对网内引脚去重、 丢弃单引脚网、哈希合并平行网并累加权重。 -
最粗层初始划分 随机种子 BFS 贪心生长到一半总权重得到平衡初始解，FM 精化，重复 10 次取割最小者。
-
逐层还原 + FM 精化 粗层划分按映射投影回细层，每层运行带平衡硬约束的 FM （增益桶 O(1) 选点、移动后锁定、回滚到割最小前缀、连续无改进早停）。
顶层支持多随机种子独立重启取最优。同时保留单层 FM baseline（命令行切换）用于对比实验。
粗层上移动一个超点等价于原图上同时移动一组紧密相连的顶点， 能跳出单层 FM 容易陷入的局部最优；且粗层规模小，多次重启的代价极低。
lab1/
├── main.cpp # 入口：命令行解析、计时、调用算法与 evaluate
├── solution.cpp/.h # 核心算法：CSR 超图、FM 精化器、粗化、多层驱动
├── Graph.cpp/.h # 图类（助教框架，修复了节点查找的线性扫描）
├── Node.cpp/.h # 顶点类（助教框架）
├── Net.cpp/.h # 超边类（助教框架）
├── evaluate.cpp/.h # 助教提供的划分结果校验与割计算
├── Makefile
├── run_all.sh # 批量运行全部 benchmark（fm + ml 两种模式）
├── summary.sh # 从日志汇总生成 Markdown 结果对比表
└── benchmark/ # ISPD98 数据集（不包含在仓库中，需自行下载解压）
make all# 用法: ./main <benchmark.hgr> [ml|fm] [runs] [seed]
./main benchmark/ibm01.hgr # 多层改进算法（默认，3 次重启取最优）
./main benchmark/ibm01.hgr ml 10 # 多层算法，10 次重启（结果更稳更优）
./main benchmark/ibm01.hgr fm 3 # 单层 FM baseline（对比实验用）批量复现实验结果：
chmod +x run_all.sh summary.sh
./run_all.sh # 跑全部 18 个数据集（fm 3 次 + ml 10 次重启）
./summary.sh # 输出含最优解 gap 的 Markdown 汇总表- 输入：
.hgr超图文件。首行为边数 顶点数（顶点编号从 1 开始）， 之后每行为一条超边连接的顶点列表。 - 输出：
<benchmark名>_partition.txt，第 i 行为顶点 i 的归属（0 = X 侧，1 = Y 侧）。 程序结束时自动调用evaluate校验平衡约束并复算割代价。
| Testcase | Baseline 单层FM | 改进多层 | 相比Baseline降低 | 最优解 | 距最优解 |
|---|---|---|---|---|---|
| IBM01 | 1060 | 204 | 80.8% | 200 | 2.0% |
| IBM02 | 502 | 342 | 31.9% | 307 | 11.4% |
| IBM03 | 3766 | 1018 | 73.0% | 951 | 7.0% |
| IBM04 | 3132 | 607 | 80.6% | 573 | 5.9% |
| IBM05 | 4097 | 1772 | 56.7% | 1706 | 3.9% |
| IBM06 | 2338 | 1018 | 56.5% | 962 | 5.8% |
| IBM07 | 5112 | 929 | 81.8% | 878 | 5.8% |
| IBM08 | 6831 | 1150 | 83.2% | 1140 | 0.9% |
| IBM09 | 5420 | 634 | 88.3% | 620 | 2.3% |
| IBM10 | 8011 | 1345 | 83.2% | 1253 | 7.3% |
| IBM11 | 9689 | 1152 | 88.1% | 1051 | 9.6% |
| IBM12 | 8385 | 1987 | 76.3% | 1919 | 3.5% |
| IBM13 | 9750 | 857 | 91.2% | 831 | 3.1% |
| IBM14 | 16434 | 1887 | 88.5% | 1842 | 2.4% |
| IBM15 | 15808 | 2811 | 82.2% | 2730 | 3.0% |
| IBM16 | 20730 | 2189 | 89.4% | 1827 | 19.8% |
| IBM17 | 23540 | 2372 | 89.9% | 2270 | 4.5% |
| IBM18 | 15930 | 1567 | 90.2% | 1521 | 3.0% |
| 合计 | 160535 | 23841 | 85.1% | 22581 | 5.6% |
测试环境：WSL (Ubuntu)，g++ -O2；baseline 为 3 次重启取最优，多层为 10 次重启取最优； 固定随机种子，结果可复现。最优解为 ε=2% 下的已知最优参考值。
- CSR 压缩存储：算法内部把指针式 Graph 转为
netPtr/netPins/nodePtr/nodeNets数组表示，cache 友好且支持粗化重建。 - 增益桶 FM：双向链表桶 O(1) 取最大增益；网两侧引脚计数
cnt0/cnt1按 FM 标准四规则增量更新邻居增益；桶内扫描深度限制防退化。 - 平衡硬约束：每步移动前检查两侧权重是否仍在
[lo, hi]内，解必然合法。 - 回滚 + 早停：每轮 pass 允许中途劣化移动，结束后回滚到割最小前缀；
连续
max(300, n/20)步无改进提前结束。 - 工程修复：助教框架中
Graph::get_or_create_node的 O(n) 线性扫描改为 map 查找（否则大图读入不可用）；Makefile 补充evaluate.cpp并开启-O2。
- 个别电路（如 IBM16）存在较深的次优盆地，单纯增加重启难以逃出， 计划引入 V-cycle（对现有解反复再粗化—再精化）。
- 粗化仅做两两匹配，可改用 FirstChoice 多顶点聚簇提升对星形大网的聚类能力。
- 精化阶段可加入受控随机扰动（iterated local search）或 look-ahead 增益策略。
- 多次重启相互独立，可多线程并行加速。
- C. M. Fiduccia and R. M. Mattheyses, "A Linear-Time Heuristic for Improving Network Partitions," DAC 1982.
- G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar, "Multilevel Hypergraph Partitioning: Applications in VLSI Domain," DAC 1997 (hMETIS).
- ISPD98 Circuit Benchmark Suite.