# 测试文档(petgraph MoonBit 移植版)

本文档详细说明本项目的测试体系、测试用例清单、运行方式、覆盖率情况以及测试中
发现并修复的问题。本移植以 Rust 原版 **petgraph** 作为**行为基准(oracle)**:凡是
移植的数据结构与算法,其结果都应与原版一致。

> 配套文档:架构与设计见 [`DESIGN.md`](./DESIGN.md);英文版测试说明见
> [`TESTING.md`](./TESTING.md);开发过程见 [`开发报告.md`](./开发报告.md);
> 上游来源与许可见 [`THIRD_PARTY.md`](./THIRD_PARTY.md)。

> **本文数据的采集方式(2026-08-15)**
>
> - 用例总数与四后端结果:`moon test --target all`
> - 分包用例数:`moon test src/<pkg>`(逐包运行)
> - 分文件用例数:统计各测试文件中的 `test "..."` 顶层用例,以及实现文件里
>   ```` ```mbt ```` doc-test 代码块的数量
> - 覆盖率:`moon test --enable-coverage` + `moon coverage report -f summary`
> - 工具链:`moon 0.1.20260807` / `moonc v0.10.7`
>
> 本文所有数字均为上述命令的实测输出,未做估算。

---

## 1. 总览

| 指标 | 结果 |
|------|------|
| 测试用例总数 | **331** |
| 通过 / 失败 | 331 / 0 |
| 运行后端 | `wasm`、`wasm-gc`、`js`、`native`(四后端**各自** 331/331 通过) |
| 其中:测试文件中的用例 | 288 |
| 其中:doc-test(实现文件与 README 里的 ```` ```mbt ```` 代码块) | 40 |
| 其中:**沿用上游 petgraph 测试函数名的移植用例** | **161**(见 §9) |
| 静态检查 | `moon check --target all --deny-warn` **零告警零错误** |
| 行覆盖率 | **2311 / 2471 ≈ 93.5%**(见 §5) |
| 测试代码规模 | 25 个测试 `.mbt` 文件,共 8218 行(实现侧 55 个文件 7118 行) |

各包测试分布:

| 包 | 黑盒 | 白盒 | doc-test | 小计 | 其中移植自 petgraph | 测试代码行 |
|----|----:|----:|----:|----:|----:|----:|
| `graph` | 45 | 5 | 0 | **50** | 22 | 1637 |
| `unionfind` | 20 | 4 | 3 | **27** | 10 | 564 |
| `visit` | 33 | 0 | 10 | **43** | 6 | 745 |
| `dot` | 13 | 0 | 0 | **13** | 5 | 284 |
| `algo` | 168 | 0 | 24 | **192** | 118 | 4988 |
| 根包(`README.mbt.md` + `petgraph.mbt`) | 0 | 0 | 6 | **6** | 0 | — |
| **合计** | **279** | **9** | **43** | **331** | **161** | **8218** |

("黑盒"= `*_test.mbt`,"白盒"= `*_wbtest.mbt`,三列互不重叠、相加即小计。
"移植自 petgraph"的判定口径见 §9.1。)

---

## 2. 测试分层策略

### 2.1 黑盒测试(`*_test.mbt`)
仅通过公开 API 进行测试,模拟真实使用者的视角。每个公开函数至少有一个黑盒用例。
断言统一使用 `debug_inspect(value, content=...)` 与 `json_inspect(arr, content=[...])`;
快照内容先以 `moon test --update` 生成,再**逐一对照 petgraph 语义人工核验**,绝不盲目
接受工具生成的输出。

### 2.2 白盒测试(`*_wbtest.mbt`)
深入包内部,校验公开 API 无法直接观测的**表示不变量(representation invariant)**:

- `graph`(`graph_wbtest.mbt`,5 例):每次 `remove_node` / `remove_edge`(采用
  swap-remove + 链接修补)之后,邻接链表仍保持自洽 —— 每个结点的 `next_out` / `next_in`
  链都能终止于哨兵 `END`,不存在悬空的 `EdgeId`,每条边的 `src` / `dst` 与其在邻接表中的
  位置一致。覆盖删除中间结点(触发交换)、删除末尾结点、自环、多种边删除顺序、无向图等场景。
  新增的 `retain_nodes` / `retain_edges` 复用同一条删除路径,其不变量校验在
  `extended_test.mbt` 中以黑盒方式补充。
- `unionfind`(`unionfind_wbtest.mbt`,4 例):路径压缩(halving)与按秩合并后的
  `parent` / `rank` 数组内部状态。

### 2.3 快照测试(DOT 输出)
DOT 渲染结果与 petgraph 自带测试模块中的**黄金字符串**逐字节比对,保证有向 `->` /
无向 `--`、转义、结点/边标签的格式完全一致。

### 2.4 属性式交叉验证
用确定性构造的图,验证对**任意输入**都应成立的性质(详见 §4):例如非负权图上
`dijkstra` / `spfa` / `bellman_ford` / `floyd_warshall` 结果一致、`johnson` ≡
`floyd_warshall`、`dinics` ≡ `ford_fulkerson`、Kosaraju 与 Tarjan 的 SCC 一致等。
本项目**全部三个真实逻辑缺陷都由这一层抓出或由它固化为回归用例**(§7)。

### 2.5 回归测试(`*_regression_test.mbt` / `*_degenerate_test.mbt`)
针对已修复的具体缺陷,用**能重现该缺陷的最小夹具**固化下来,文件头写明缺陷成因,
防止回潮。目前有两组:`src/algo/undirected_regression_test.mbt`(无向遍历,5 例)与
`src/algo/flow_degenerate_test.mbt`(最大流退化输入,2 例)。

### 2.6 文档即测试(doc-test)
两处:

- `src/README.mbt.md`(已软链到仓库根的 `README.md`)中的代码块以 ```` ```mbt check ````
  形式被编译并执行(3 例)。
- 实现文件的文档注释里带可运行示例(37 例:`algo` 24、`visit` 10、`unionfind` 3)。这保证
  API 文档中的示例永远与真实签名同步、**可复现**。注意 `graph` 与 `dot` 两个包目前
  **没有** doc-test,其公开 API 只由 `*_test.mbt` 覆盖 —— 这是后续可补的一块。

---

## 3. 测试用例清单

### 3.1 `graph` 包(50)

| 文件 | 用例 | 内容 |
|------|----:|------|
| `graph_test.mbt` | 15 | 构造与计数、增点/增边、`update_edge` 更新与新增、`find_edge`(有向/无向)、邻居逆插入序、无向邻居与自环跳过、`edges_directed` 顺序、`externals`、`node_ids`/`edge_ids`、`from_edges` / `from_edges_undirected`、`reverse`、`clear` / `clear_edges`、`remove_edge`、`remove_node` |
| `graph_ported_test.mbt` | 13 | 移植自上游 `tests/graph.rs`(见 §9.1) |
| `extended_test.mbt` | 17 | 本轮新增 API:`edge_references` 按索引序、有向/无向边迭代器、`edges_connecting` 顺序、多重边迭代、`map` / `filter_map`(含"全部丢弃得到空图")、`retain_edges` / `retain_nodes`(有向多重图、无向含自环)、权重迭代器、`extend_with_edges`、`first_edge` / `next_edge` 走邻接链表、`into_nodes_edges` 拆解 |
| `graph_wbtest.mbt` | 5 | 白盒:删除后的邻接链表不变量(见 §2.2) |

### 3.2 `unionfind` 包(27)

| 文件 | 用例 | 内容 |
|------|----:|------|
| `unionfind_test.mbt` | 10 | 新建集合互不相交、`union` 合并且 `find` 一致、`union` 返回值反映是否真的合并、`same_set`、长链塌缩、`into_labeling`(单集合 / 多不相交集合)、`new_set` 增量扩容、`try_*` 越界、成对 union 与 find 的较大规模一致性场景 |
| `unionfind_ported_test.mbt` | 10 | 移植自上游 `tests/unionfind.rs`(见 §9.1) |
| `unionfind_wbtest.mbt` | 4 | 白盒:`parent[i]=i` / `rank[i]=0` 初始化、等秩合并抬升根的秩、小树挂大树、`find` 的路径压缩(halving) |
| `unionfind.mbt` doc-test | 3 | 公开入口的可运行示例 |

### 3.3 `visit` 包(43)

| 文件 | 用例 | 内容 |
|------|----:|------|
| `traversal_test.mbt` | 7 | 邻居逆插入序;`Dfs` / `Bfs` / `DfsPostOrder` / `Topo` 在样例 DAG 上的精确访问顺序;`Topo` 跳过环上结点;`Dfs` 的 `reset` 与 `move_to` |
| `dfs_visit_test.mbt` | 4 | `depth_first_search`:发出 discover/finish 与 tree edge;检测回边;`Break` 提前终止;`Prune` 跳过某结点的出边 |
| `traversal_ported_test.mbt` | 6 | 移植自上游 `tests/graph.rs` / `tests/quickcheck.rs` 的遍历部分(见 §9.1) |
| `adapters_test.mbt` | 16 | 本轮新增:`Reversed` 交换 Outgoing/Incoming、`Dfs`/`Bfs`/`Topo` 在 `Reversed` 上反向走图;`NodeFiltered` 同时从 `node_ids` 与邻居表中剔除结点、各遍历随之跳过;`EdgeFiltered` 只删边不删点、谓词可读边权;`UndirectedAdaptor` 双向报告邻居、使有向路径可从两端遍历;`Walker::iter` 与手写 `next` 循环逐点一致(四种遍历器各一)、`walk_next` 单步且单趟、`Walker` 与适配器可组合 |
| 实现文件 doc-test | 10 | `dfs`/`bfs`/`topo`/`dfs_visit`/`reversed`/`undirected_adaptor` 各 1,`filter`/`walker` 各 2 |

### 3.4 `dot` 包(13)

| 文件 | 用例 | 内容 |
|------|----:|------|
| `dot_test.mbt` | 8 | 有向图(int 权)、无向图(`graph` 关键字与 `--` 边)、`NodeIndexLabel`、`EdgeIndexLabel`、`EdgeNoLabel`、`NodeNoLabel`、`GraphContentOnly`、引号/反斜杠/换行的转义 |
| `dot_ported_test.mbt` | 5 | 移植自上游 `src/dot/mod.rs` 的内联测试(见 §9.1) |

### 3.5 `algo` 包(192)

| 文件 | 用例 | 覆盖的入口 |
|------|----:|------|
| `path_test.mbt` | 7 | `dijkstra`(单位权 / 带权 + goal 提前终止)、`astar`(最优路径 / 无路径返回 `None`)、`bellman_ford`(距离与前驱 / 检测负环)、`dijkstra ≡ bellman_ford` 交叉验证 |
| `structure_test.mbt` | 12 | `toposort`、`is_cyclic_directed`、`is_cyclic_undirected`、`connected_components`、`kosaraju_scc`、`tarjan_scc`、`min_spanning_tree`,以及三条交叉验证 |
| `dijkstra_ported_test.mbt` | 8 | 上游 dijkstra / astar / bellman_ford 的 doctest 与 `test_astar_*` |
| `scc_ported_test.mbt` | 11 | 上游 SCC / toposort / 连通分量测试 |
| `mst_ported_test.mbt` | 5 | 上游 Kruskal 测试(其中三条 `mst_prim_*` 用例在首轮以 Kruskal 等价验证,标注 "via kruskal") |
| `connectivity_test.mbt` | 16 | `articulation_points`(9 个夹具:单点、双连通分量、链、星、团、3×3 网格、非连通图等)、`bridges`、`simple_fast` / `Dominators`(2)、`condensation`(2,含无向图)、`has_path_connecting`、`is_bipartite_undirected` |
| `flow_tree_test.mbt` | 22 | `ford_fulkerson`(Int + Double)、`dinics`(上游 7 个夹具 a–g)、二者一致性、汇点不可达、`min_spanning_tree_prim`(5)、`steiner_tree`(`example_kous_paper`、`b01_vienna_test`、`b07_vienna_test`)、`dag_transitive_reduction_closure`(`test_easy_tred`、可达性保持)、`dag_to_toposorted_adjacency_list` |
| `paths_extended_test.mbt` | 32 | `floyd_warshall`(7)、`johnson`(6)、`spfa`(7)、`k_shortest_path`(2)、`bidirectional_dijkstra`(3)、`find_negative_cycle`(3),外加 4 条跨算法交叉验证 |
| `combinatorial_test.mbt` | 48 | `maximal_cliques`(6)、`greedy_matching` / `maximum_matching`(13,含 Petersen 图完美匹配、blossom 收缩、与暴力枚举 oracle 比对)、`dsatur_coloring`(3)、`all_simple_paths` / `all_simple_paths_multi`(22,含惰性求值验证)、`greedy_feedback_arc_set`(4) |
| `undirected_regression_test.mbt` | 5 | §7.1 缺陷的回归套件 |
| `flow_degenerate_test.mbt` | 2 | §7.2 缺陷的回归套件 |
| 实现文件 doc-test | 24 | 每个新增公开入口至少一段可运行示例 |

### 3.6 根包文档示例(6)

`src/README.mbt.md`(5 个):shortest path and spanning tree、dot export、traversal
and cycles、maximum flow(`dinics` 与 `ford_fulkerson` 在同一网络上取值一致)、
reversed view(`Reversed` 适配器让 `Dfs` 反向遍历有向路径)。

`src/petgraph.mbt`(1 个):`version()` 与 `moon.mod` 的 `version` 字段一致。

> `src/README.mbt.md` 由根目录 `README.md` 机械生成(去掉 CI 徽章与语言切换行),
> 因此 README 里展示的示例与实际被编译执行的示例不会漂移。

---

## 4. 重点:属性式交叉验证

这些用例不依赖单一"标准答案",而是用一个算法的结果验证另一个算法,显著提升可信度。
本轮随新算法一并扩充:

| 性质 | 含义 | 所在文件 |
|------|------|----------|
| `dijkstra` ≡ `bellman_ford` | 非负权图上两种最短路算法的距离逐点相等 | `path_test.mbt` |
| `spfa` ≡ `bellman_ford` | 含负权(无负环)图上距离逐点相等 | `paths_extended_test.mbt` |
| `spfa` ≡ `dijkstra` ≡ `floyd_warshall` 的对应行 | 非负权图上单源与全源结果一致 | `paths_extended_test.mbt` |
| `johnson` ≡ `floyd_warshall` | 两种全源最短路的整张距离矩阵相等 | `paths_extended_test.mbt` |
| `k_shortest_path`(k=1) ≡ `dijkstra` | k=1 退化为普通最短路 | `paths_extended_test.mbt` |
| `dinics` ≡ `ford_fulkerson` | 同一网络上两种最大流算法的流量相等 | `flow_tree_test.mbt` |
| `maximum_matching` ≡ 暴力枚举 | 小图上与穷举 oracle 的匹配数一致 | `combinatorial_test.mbt` |
| `toposort` 尊重边序 | 排序结果中每条边的 source 都排在 target 之前 | `structure_test.mbt`、`flow_tree_test.mbt` |
| `is_cyclic_directed` ⇔ `toposort` 为 `Err` | 对包含自环在内的多个图均成立 | `structure_test.mbt` |
| `tarjan_scc` ≡ `kosaraju_scc` | 同一有向图上两种 SCC 算法的数量与内容一致 | `structure_test.mbt` |
| `connected_components` ≡ kosaraju SCC 数 | 对称(双向)有向图上无向连通块数等于其 SCC 数 | `structure_test.mbt` |
| 传递归约保持可达性 | `dag_transitive_reduction_closure` 的归约图与原图可达关系相同 | `flow_tree_test.mbt` |

---

## 5. 覆盖率明细

采集命令与实测结果:

```
$ moon test --enable-coverage
Total tests: 331, passed: 331, failed: 0.
$ moon coverage report -f summary
...
Total: 2311/2471
```

**行覆盖 2311 / 2471 ≈ 93.5%。** `-f summary` 只列出**存在未覆盖行**的文件;未出现在下表中的
实现文件为 100% 覆盖。下表是本次实测输出的全部条目:

| 文件 | 覆盖 | 文件 | 覆盖 |
|------|------|------|------|
| algo/bellman_ford.mbt | 39/40 | algo/steiner_tree.mbt | 98/108 |
| algo/bidirectional_dijkstra.mbt | 79/87 | algo/toposort.mbt | 28/32 |
| algo/bridges.mbt | 42/43 | dot/dot.mbt | 78/81 |
| algo/condensation.mbt | 37/41 | graph/access.mbt | 62/64 |
| algo/connectivity.mbt | 33/34 | graph/edge_refs.mbt | 46/52 |
| algo/cyclic.mbt | 33/35 | graph/index.mbt | 11/15 |
| algo/dominators.mbt | 71/72 | graph/mutate.mbt | 122/127 |
| algo/feedback_arc_set.mbt | 109/114 | graph/neighbors.mbt | 64/73 |
| algo/floyd_warshall.mbt | 31/32 | graph/retain.mbt | 16/18 |
| algo/ford_fulkerson.mbt | 72/80 | unionfind/unionfind.mbt | 58/60 |
| algo/johnson.mbt | 51/52 | visit/dfs_post_order.mbt | 25/29 |
| algo/k_shortest_path.mbt | 17/19 | visit/dfs_visit.mbt | 38/42 |
| algo/matching.mbt | 150/157 | visit/filter.mbt | 31/32 |
| algo/maximal_cliques.mbt | 54/55 | visit/topo.mbt | 28/33 |
| algo/min_spanning_tree.mbt | 16/17 | visit/visit_map.mbt | 14/17 |
| algo/negative_cycle.mbt | 35/45 | cmd/main/main.mbt | 0/32 |
| algo/scored.mbt | 2/4 | petgraph.mbt | 0/1 |
| algo/simple_paths.mbt | 100/104 | | |
| algo/spfa.mbt | 41/44 | **合计** | **2311 / 2471** |

未覆盖部分主要来自三处:

1. **演示程序 `cmd/main/main.mbt`(0/32)与门面文件 `petgraph.mbt`(0/1)** —— 演示与
   模块文档,不计入有效逻辑。剔除这两者后为 **2311 / 2438 ≈ 94.8%**。
2. **防御性分支** —— 如 `scored.mbt`(2/4)、`graph/index.mbt`(11/15)中越界或哨兵路径的
   分支,以及 `Measure` / `BoundedMeasure` 实例中未被全部算法路径触及的比较分支。
3. **本轮新增算法中未被上游夹具覆盖的边角路径** —— `negative_cycle.mbt`(35/45)、
   `steiner_tree.mbt`(98/108)、`ford_fulkerson.mbt`(72/80)、
   `bidirectional_dijkstra.mbt`(79/87)相对偏低,是后续补测的优先目标。

---

## 6. 如何运行

```bash
export PATH="$HOME/.moon/bin:$PATH"   # 若 moon 不在 PATH 中

moon test                  # 默认后端(wasm-gc)运行全部测试
moon test --target all     # 在 wasm / wasm-gc / js / native 四后端运行
moon test src/graph        # 仅运行某个包的测试
moon test --deny-warn      # 测试代码中的告警视为错误(CI 用)
moon test --update         # 重新生成快照(随后务必人工核验)

# 覆盖率
moon test --enable-coverage
moon coverage report -f summary
```

持续集成(`.github/workflows/ci.yml`)分两个 job:

1. **验收门禁**:`moon check --target all --deny-warn`、`moon fmt && git diff --exit-code`、
   `moon info && git diff --exit-code`(公开接口 `.mbti` 不得漂移)、`moon test --deny-warn`。
2. **四后端矩阵**:在 `wasm` / `wasm-gc` / `js` / `native` 上分别构建与测试。

---

## 7. 测试中发现并修复的真实缺陷

测试不是走过场。以下按发现时间倒序,前两条是本轮扩展中发现的**真实实现缺陷**。

### 7.1 `dijkstra` / `astar` / `bellman_ford` 在无向图上漏边(修复提交 `84fdc30`)

**缺陷。** 一条无向边在存储上**只存一次**,带一个固定的 `(src, dst)`,却同时出现在
**两个端点**的关联边链表里。这三个算法当时都是"遍历 `edges_directed(node, Outgoing)`,
再无条件把这条边存储的 `dst` 当作邻居":

```
for edge in g.edges_directed(node, Outgoing) {
  guard g.edge_endpoints(edge) is Some((_, next)) else { continue }
  ...
}
```

于是任何被存成 `(other, node)` 的无向边,读出来的 `dst` 恰好是 `node` 自己,搜索**直接走回
起点**。后果:在无向图上三个算法只探索"碰巧存对方向"的那些边,**把可达结点静默报成不可达**,
而且从两端搜索的结果不对称。

**如何重现。** 构造一条 4 结点的无向路径 `0 -- 1 -- 2 -- 3`,但把每条边都"反着存"
(以较大索引作 source):

```
g.add_edge(NodeId::new(1), NodeId::new(0), 1)
g.add_edge(NodeId::new(2), NodeId::new(1), 1)
g.add_edge(NodeId::new(3), NodeId::new(2), 1)
```

从结点 0 跑 `dijkstra`。**修复前**返回的距离表只有 1 项(起点自己),结点 1/2/3 全被判为
不可达;**修复后**返回 4 项,距离为 0/1/2/3。同一夹具从结点 3 出发必须给出镜像结果 3/2/1/0。

**修复。** 三处统一改走 `Graph::edges(node)`。这个访问器对每条关联边做端点规范化,保证
`target` 是**背离 `node`** 的那一端,正是 petgraph `Edges` / `EdgeRef::target` 的语义:

```
for eref in g.edges(node) {
  let next = eref.target
  ...
  let next_score = node_score.add(edge_cost(eref.id))
}
```

有向图行为完全不变(对有向图 `edges(a)` 恰好是 `a` 的出边),所有既有用例无需改动。

**回归套件。** `src/algo/undirected_regression_test.mbt`,5 例:`dijkstra` 走反着存的无向边、
`dijkstra` 的无向对称性、`astar` 同题(校验代价与完整路径 `[0,1,2,3]`)、`bellman_ford`
同题、以及"无向自环不得被误当作前进一步"(自环两端相等,端点规范化必须报告结点自己且不重复计数)。

**为什么以前没抓到。** 首轮 `dijkstra` / `astar` / `bellman_ford` 的用例
(`src/algo/path_test.mbt`)**全是有向图**;唯一的无向夹具是 `bellman_ford` 负环 doctest,
而它的每条边都恰好"正着存"(source 索引小于 target),有缺陷的代码路径照样能走通。缺陷完整
落在测试盲区,直到本轮六路并行扩展合并后跑全量联测才暴露。

### 7.2 `dinics` 在 `source == destination` 时不终止(修复提交 `84fdc30`)

**缺陷。** 调用 `dinics(g, source=a, destination=a, ...)` **永不返回**。层次图始终把
destination 放在一个正的层级上,外层循环因此永远等不到"层级为 0"的终止条件;而每一轮找到的
增广路都是空的,流量一点不增 —— 死循环。**上游 petgraph 存在同样的缺陷**,不是本移植引入的。

**如何重现。** 两结点、一条容量 5 的有向边,令 source = destination = 结点 0,调用
`dinics`。本地实测该调用**超过 2 分钟仍未返回**(被超时中断);同一输入下 `ford_fulkerson`
立刻返回 0。

**修复。** 在 `dinics` 入口显式挡掉这一退化输入,报告零流量,与本来就能正常终止的
`ford_fulkerson` 对齐:

```
if source == destination {
  return (max_flow, flows)
}
```

代码注释里写明了取舍理由:**不终止比与上游行为有出入更糟**;而且"从一个结点到它自己的最大流"
本来就该是 0。

**回归套件。** `src/algo/flow_degenerate_test.mbt`,2 例:`source == destination` 时
`dinics` 与 `ford_fulkerson` 都返回 0 且没有任何边带流量(用例本身若不终止即为失败);
以及"汇点不可达"这一相邻的退化情形,同样要求两者一致。

### 7.3 `kosaraju_scc` 返回空结果(降序 range 不迭代)

MoonBit 的区间 `for x in a..=b` 仅支持升序,`(len-1)..=0` 这类降序写法**根本不会迭代**。
这导致 Kosaraju 第二趟按完成时间逆序处理结点的循环空转,SCC 结果为空。修复:改用显式
递减的 `for` 循环。该缺陷正是被"tarjan 与 kosaraju 必须一致"这条交叉验证用例抓出来的。

### 7.4 `Show` → `Debug` 迁移导致的快照差异

早期 MoonBit 工具链从 `Show` 迁移到 `Debug` 作为调试输出。`debug_inspect` 会给字符串加引号
(`Some("b")`),而旧的 `Show` 不加(`Some(b)`)。统一改用 `derive(Debug)` + `debug_inspect`
后,相应快照同步更新并核验。

### 7.5 DOT 字符串断言方式

多行 DOT 字符串若用 `debug_inspect` 会被转义成单行,改用 `assert_eq` 对照 `#|` 多行字符串
字面量(末尾补一个空 `#|` 行以匹配结尾换行)。

### 7.6 工具链升级(`moonc v0.10.7`)带来的测试侧改写

升级后 `moon test --deny-warn` 报出两类新告警,均已迁移(提交 `6a4ec0a`),**属于语法迁移
而非缺陷**:

- 空 Map 字面量 `{}` 被弃用,迁移提交改写了 6 处为 `Map([])`。
- 测试与内部断言里非穷尽的 `guard ... is Some(x)`(即"不匹配就该 panic"的守卫)必须显式
  写成 `guard!`,迁移提交改了 7 处。

本轮新增代码一律沿用新写法,目前全仓共 26 处 `Map([])` 与 13 处 `guard!`,后者分布在
`scc_ported_test.mbt`、`structure_test.mbt`、`mst_ported_test.mbt`、`connectivity_test.mbt`
与 `matching.mbt`。

---

## 8. 确定性与可复现性说明

- **邻居顺序**遵循 petgraph 的**逆插入序**(侵入式链表头插)。凡比较邻居/遍历序列的
  用例,要么期望该精确顺序,要么先排序再断言。
- **SCC 分量内部**结点顺序是任意的;比较前会对内部数组排序,使输出在不同运行/后端
  之间稳定。同理,`maximal_cliques`、`all_simple_paths` 等返回集合族的算法在断言前统一
  做字典序规范化(注意 `Array` 的派生序会先比长度,因此用例里自带 `lex_compare` 辅助函数)。
- 随机性测试使用确定性的小型种子生成器(LCG),不引入外部 quickcheck 依赖,保证可复现。
- **浮点**:上游用 `f32` 的夹具在本项目用 `Double` 复跑;`BoundedMeasure for Double` 的
  `max_value()` 是 `+inf`,`checked_add` 永不报溢出而是饱和,这与上游 `f32` 的行为一致。

---

## 9. 与 petgraph 真实测试用例的移植对照

本项目**系统性移植了 petgraph 自身测试套件中属于本项目范围的用例**,忠实保留原始 Rust 测试
函数名(直接作为 MoonBit 用例名,或加 `port:` 前缀)。移植来源:petgraph 的
`crates/petgraph/tests/*.rs`、`src/algo/*.rs` 与 `src/graph_impl/mod.rs` 的内联 `#[test]`
及 doctest。

首轮移植了 58 条,置于各包的 `*_ported_test.mbt`;本轮随六个并行工作包又移植了约 103 条,
与新算法的自研用例合放在按主题命名的 `*_test.mbt` 中(文件头注明上游来源文件)。

### 9.1 已移植清单(按包)

**计数口径:** 下表统计"用例名沿用了上游 Rust 测试函数名(或上游 doctest)"的用例;
纯自研的交叉验证、边界与回归用例不计入。

| 包 | 文件 | 移植数 | 对应的上游来源与测试名 |
|----|------|----:|------------------------|
| `graph` | `graph_ported_test.mbt` | 13 | `tests/graph.rs`:undirected, selfloop, multi, update_edge, without, from_edges, neighbors_selfloops, neighbor_order, test_neighbors_iteration_order, test_neighbors_directed_iteration_order, test_neighbors_undirected_iteration_order, test_edges_iteration_order, test_edges_directed_iteration_order |
| `graph` | `extended_test.mbt` | 9 | `tests/graph.rs`:test_edge_iterators_directed, test_edge_iterators_undir, test_edges_connecting_iteration_order, iter_multi_edges, iter_multi_undirected_edges, test_map, test_filter_map, retain, test_weight_iterators |
| `unionfind` | `unionfind_ported_test.mbt` | 10 | `tests/unionfind.rs`:uf_test, uf_test_checked, uf_test_with_equiv, uf_test_with_checked_equiv, uf_rand, uf_u8, uf_u8_checked, labeling, uf_incremental, uf_test_out_of_bounds |
| `visit` | `traversal_ported_test.mbt` | 6 | dfs, dfs_order, bfs, usize_index(遍历部分), test_toposort, test_toposort_eq |
| `dot` | `dot_ported_test.mbt` | 5 | `src/dot/mod.rs`:test_escape, test_nodeindexlable_option, test_edgeindexlable_option, test_edgenolable_option, test_nodenolable_option |
| `algo` | `dijkstra_ported_test.mbt` | 8 | dijkstra / astar / bellman_ford 的 doctest,test_astar_null_heuristic, test_astar_manhattan_heuristic, test_astar_runtime_optimal, test_astar_admissible_inconsistent |
| `algo` | `scc_ported_test.mbt` | 11 | kosaraju / tarjan doctest, scc, tarjan_scc, test_toposort, test_toposort_eq, is_cyclic_directed, cyclic, connected_comp, connected_components doctest |
| `algo` | `mst_ported_test.mbt` | 5 | mst_kruskal, mst_kruskal_test_cases, mst_prim_trivial_graph / mst_prim_graph_without_edges / mst_prim_empty_graph(首轮以 Kruskal 等价验证) |
| `algo` | `connectivity_test.mbt` | 15 | `tests/articulation_points.rs`:art_single_node, art_two_connected_components, art_linear_chain, art_star_graph, art_clique, art_simple1, art_disconnected_graph, art_3x3_grid, art_simple2;`bridges.rs`:test_bridges;`dominators.rs`:test_iter_dominators, test_dominators_simple_fast;`tests/graph.rs`:condensation, test_has_path, bipartite |
| `algo` | `flow_tree_test.mbt` | 18 | `tests/ford_fulkerson.rs`:test_ford_fulkerson;`tests/dinics.rs`:test_dinics_a … test_dinics_g;`tests/min_spanning_tree.rs`:mst_prim, mst_prim_trivial_graph, mst_prim_graph_without_edges, mst_prim_empty_graph, mst_prim_test_cases;`tests/steiner_trees.rs`:example_kous_paper, b01_vienna_test, b07_vienna_test;`src/algo/tred.rs`:test_easy_tred, dag_to_toposorted_adjacency_list |
| `algo` | `paths_extended_test.mbt` | 26 | `tests/floyd_warshall.rs`(5 + doctest)、`tests/johnson.rs`(5)、`tests/spfa.rs` + doctest(7)、`tests/k_shortest_path.rs` + doctest(2)、`src/algo/dijkstra.rs` doctest 与 `tests/quickcheck.rs` 的 bidirectional_dijkstra_directed / _undirected(3)、`src/algo/bellman_ford.rs` doctest 与 test_find_negative_cycle(2)、floyd_warshall_(1) |
| `algo` | `combinatorial_test.mbt` | 35 | `tests/maximal_cliques.rs`(5)、`tests/matching.rs`:greedy_empty / greedy_disjoint / greedy_odd_path / greedy_star / maximum_empty / maximum_disjoint / maximum_odd_path(7)、`tests/coloring.rs`:dsatur_coloring_cycle6 / dsatur_coloring_bipartite(2)、`src/algo/simple_paths.rs` 的 `mod test`(21) |
| **合计** | | **161** | |

### 9.2 移植时的适配(因语言/API 差异)

忠实移植但需对接 MoonBit API,典型适配:

- **`Option` vs `Result` / panic 索引:** petgraph 用 `g[idx]` 直接索引、`try_*` 返回
  `Result`;本项目 `node_weight`/`edge_weight` 返回 `Option`,`try_*` 返回 `Option`。
- **迭代器 vs 物化数组:** petgraph 的 `neighbors(n).count()`、`walker.iter(&g)` 改为本项目的
  `neighbors(n).length()`、`Walker::iter` 或循环 `walker.next(g)`。
- **MST 返回形态:** petgraph 返回元素流/新图;本项目返回 `Array[EdgeId]`,改为校验"边数 =
  结点数 − 连通分量数"且 MST 总权重一致。
- **`steiner_tree` 返回形态:** petgraph 返回 `StableGraph`;本项目返回保留的边集合,
  "结点数"由这些边的端点推出。
- **`dag_transitive_reduction_closure` 的输入:** petgraph 用 `adj::List`;本项目用后继表
  `Array[Array[Int]]`。
- **SCC 顺序:** 两者均为逆拓扑序、SCC 内部顺序任意,比较前规范化(对内部与外层都排序),
  对应 petgraph 自己的 `assert_sccs_eq`。
- **`Ix` 泛型坍缩为 `Int`:** petgraph 的 `_u8`/`_u16`/`_u32` 索引宽度变体在本项目中等价,
  合并为单个 `Int` 用例(已注明)。
- **权重类型:** 上游用 `u8`/`u16`/`u32`/`f32` 的夹具,在本项目按 `Measure` 的实例范围
  分别用 `Int` 与 `Double` 复跑(如 `test_ford_fulkerson` 同时有 Int 与 Double 两个版本)。
- **随机性:** `uf_rand` 等用确定性 LCG 替代 Rust 的 rng,保留"大量随机 union 后校验一致性"
  的意图。
- **`debug` 路径:** 对 `Int?` 等只派生 `Show` 的组合类型,用 `json_inspect` 或布尔
  `is Some(..) && ..` 断言,避免触发 `Show`-用于调试的弃用告警,断言意图不变。

### 9.3 有意跳过的 petgraph 测试(超出本项目范围)

以下 petgraph 测试**不在移植范围**,已逐项记录原因(范围见 [`DESIGN.md` §1](./DESIGN.md)):

- **范围外数据结构:** `StableGraph`、`GraphMap`、`Csr`、`MatrixGraph`、`adj::List`、
  `Frozen` / `Acyclic` 的测试。**注意:上游有一批测试只在 `StableGraph` 上跑**
  (典型是 `steiner_tree` 与 `retain_*` 的结点/边删除场景),本项目无稳定索引图,只能跳过;
  等价语义改由 `Graph` 的删除路径 + 白盒不变量测试覆盖。
- **范围外算法:** 同构判定(iso / VF2)、`page_rank`、`parallel_johnson`(本移植无线程)、
  `degree_sequence`。
- **解析与序列化:** DOT 解析器、graph6 编解码、serde 序列化的测试 —— 本项目只输出 DOT。
- **索引宽度/容量/溢出与 panic:** `oob_index`、`u8_index_overflow*`、`test_try_add_node/edge`、
  `reserve`/`shrink_*` —— `Ix` 坍缩为 `Int` 后这些变体合并或不适用(无 `GraphError`/溢出 API)。
- **`generate` feature 的图生成器测试** 与纯 quickcheck 测试 —— 以确定性构造替代或跳过。

### 9.4 移植结论

- **首轮 58 条移植用例全部一次性通过、未触发任何实现修改。** 这在当时被解读为"行为保真"的
  强证据 —— 事后看,更准确的解读是**当时的移植面还不够宽**。
- **本轮把移植面扩大到 161 条(约占全部用例的一半)后,立刻照出了两个真实缺陷**(§7.1、
  §7.2),其中一个(`dinics` 不终止)连上游 petgraph 本身也有。
- 结论:移植上游测试是高性价比的保真手段,但**"一次通过"只说明测试面尚未覆盖到缺陷所在的
  输入类别**(本例中是"反着存的无向边"与"退化的最大流输入"),不能作为无缺陷的证明。