moonbit-pathfinding

🌐 Language: English · 简体中文

⚠️ This is the static README. The canonical, always-up-to-date README is README.mbt.md, which runs as executable tests via moon test README.mbt.md — every code example is verified on every CI run. 本文件仅为静态副本，最新权威版本请查看 README.mbt.md（可执行文档，示例即测试）。

A MoonBit-native pathfinding and graph algorithms library built for rigorous engineering.

A production-grade pathfinding and graph algorithms library for MoonBit, built to compete with Rust's pathfinding crate on the axes that matter: executable proof predicates, executable Markdown documentation, multi-backend consistency (wasm-gc / native / js), and reproducible validation scripts.

---

Why this project (three stories)

1. Filling an ecosystem gap — a production-grade pathfinding / graph algorithms library for MoonBit: 38+ algorithms (BFS → A* → JPS → ALT → CH → Hub Labels → PHAST) plus 20 infra directions, published on mooncakes.io with a live in-browser playground.
2. An engineering benchmark for the ecosystem — 3339 tests across four backends (wasm-gc / native / js / wasm), executable proof predicates, executable README (moon test README.mbt.md), DST + differential PBT, zero-warning --deny-warn CI gates, and a published head-to-head vs Rust's pathfinding crate (≈2.7× median same-algorithm speedup; bidirectional variants reported separately).
3. Real data, end to end — real OSM road networks (Beijing / Xiamen) drive the point-to-point hierarchy (bidirectional Dijkstra → ALT → CH → HL, up to 13279×) with full cross-validation, all reproducible from checked-in scripts and artifacts.

Downstream usage: two independent repositories consume the published mooncakes.io package (moon add Suquster/moonbit-pathfinding) as a regular dependency, each with its own tests and CI: Suquster/moonbit-pathfinding-demo (a warehouse robot route planner) and Suquster/moonbit-maze (a perfect-maze generator + A* solver CLI with a Dijkstra cross-check oracle).

---

Ported from

本库 API 哲学 参考自 Rust 社区的 pathfinding crate（v4.15.0， 双许可 MIT OR Apache-2.0）。核心借鉴:

• "Successor function" 极简设计 — 算法不强制图数据结构,用户通过 fn(N) -> Array[N] 或 fn(N) -> Array[(N, W)] 定义邻居关系。
• 泛型节点类型 — N : Eq + Hash 足够,无需 Ord 约束。
• 返回类型风格 — Option[(Array[N], W)] 表示"可能无解的带权最短路"。

但所有算法实现均独立派生自原始论文,不是逐行移植。本库在此基础上原 创贡献:

1. Executable proof predicates for BFS/Dijkstra contracts, with runtime regression tests today and a clear moon prove upgrade path.
2. Executable README examples via moon test README.mbt.md, so examples are compiled and snapshot-checked instead of drifting.
3. 四后端一致性 — wasm-gc / native / js / wasm 差分测试 CI 门禁 + WASI 交付门禁 + wasm 组件模型交付门禁。
4. AI-agent-friendly successor-function APIs and graph input guides that keep callers free from a forced graph data structure.

See docs/ECOSYSTEM_COMPARISON.md for a per-domain comparison with existing MoonBit ecosystem packages (pathfinding, hash, compress, TOML, diff, etc.) and the tradeoffs behind each choice, and docs/STRATEGY_CLOSURE.md for the project's six-layer closure positioning (pathfinding ⊂ graph algorithms ⊂ verification infra ⊂ general infra ⊂ language tooling ⊂ AI-native software factory).

---

Quick Start

1. 安装依赖

在你的 MoonBit 项目根目录执行:

moon add Suquster/moonbit-pathfinding

在需要调用算法的包的 moon.pkg 里声明导入:

import {
  "Suquster/moonbit-pathfinding/src/directed" @directed,
}

More copy-ready import patterns are in AI_AGENT_USAGE.md.

2. Dijkstra 最短路 · 5 节点小图

考虑下面的有向带权图 (节点 A..E 对应索引 0..4):

边列表 (起点 → 终点, 权重):
  A(0) → B(1) : 1
  A(0) → C(2) : 4
  B(1) → C(2) : 2
  B(1) → E(4) : 3
  C(2) → D(3) : 1
  E(4) → D(3) : 2

目标: 求 A → D 的最短路径。

三条候选路径:

#	路径	代价计算	总代价
1	A → B → C → D	1 + 2 + 1	4 ✅
2	A → C → D	4 + 1	5
3	A → B → E → D	1 + 3 + 2	6

完整可运行示例 (cmd/main/main.mbt):

fn main {
  // 邻接表: 索引 0..4 对应节点 A..E
  // 每个元素为 (邻居节点, 边权)
  let adj : Array[Array[(Int, Int)]] = [
    [(1, 1), (2, 4)], // A: A->B(1), A->C(4)
    [(2, 2), (4, 3)], // B: B->C(2), B->E(3)
    [(3, 1)],         // C: C->D(1)
    [],               // D: 目标,无出边
    [(3, 2)],         // E: E->D(2)
  ]
  let start = 0 // A
  let goal = 3 // D
  match @directed.dijkstra(start, fn(n) { adj[n] }, fn(n) { n == goal }) {
    Some((path, cost)) => {
      println("cost = \{cost}")
      println("path = \{path}")
    }
    None => println("unreachable")
  }
}

运行:

moon run cmd/main

预期输出:

cost = 4
path = [0, 1, 2, 3]

即最短路径为 A → B → C → D, 总代价 4,与上方表格第 1 行结果吻合。

💡 小贴士: dijkstra 的签名是 fn[N : Eq + Hash, W : @core.Weight + Compare + Eq](N, (N) -> Array[(N, W)], (N) -> Bool) -> (Array[N], W)? — 节点类型 N 可用 Int / String / 任意实现了 Eq + Hash 的自定义类型; 权重类型 W 可用内置的 Int / Double(见 src/core/prelude.mbt 的 Weight 实现)。

---

Example Workflows

The repository ships runnable workflows that exercise different user stories instead of isolated snippets — pathfinding and INFRA directions alike:

Example	Command	Direction	What it proves
Maze solver	moon run examples/maze_solver	BFS	ASCII maze shortest paths, including an unreachable goal
Network routing	moon run examples/network_routing	Dijkstra	Minimum-latency routes over routers A..J, including asymmetric unreachable routing
Eight puzzle	moon run examples/eight_puzzle	A*	Sliding-tile solution traces with Manhattan heuristic and a 20-move scenario
Mini compiler pipeline	moon run examples/mini_compiler_pipeline	mini_compiler	Full mini-ML chain: lexer → parser → HM inference → optimizer → bytecode VM with TCO, interpreter differential, JS emission
Regex toolkit	moon run examples/regex_toolkit	regex_engine	Log scrubbing: named captures, replace_all redaction, split, linear-time ReDoS resistance
Log pipeline	moon run examples/log_pipeline	logging	Trace spans + W3C traceparent, JSON/logfmt/pretty renderers, PII redaction, env-filter
Actor worker pool	moon run examples/actor_worker_pool	actor	Supervised worker pool with faults + restart, deathwatch, ask pattern, routing strategies, bounded-mailbox backpressure
Build pipeline	moon run examples/build_pipeline	build_tool	Rule parsing, parallel wave scheduling, minimal incremental rebuilds, cached execution, auto-bisect
Serialization studio	moon run examples/serialization_studio	serialization	.proto parse/validate, typed wire + JSON round-trips, canonical bytes, breaking-change detection, codegen
DST explorer	moon run examples/dst_explorer	dst	Seeded deterministic replays, partition/crash fault injection, DPOR exploration, shrinking, linearizability checking
Config & diff ops	moon run examples/config_diff_ops	infra_config + infra_diff	TOML/INI parsing, unified diffs, patch apply/revert, diff3 merge with conflicts, semver gates
Hash integrity	moon run examples/hash_integrity	infra_hash	SHA-2/SHA-3/BLAKE2b digests (sha256 matches sha256sum), HMAC tamper detection, HKDF/PBKDF2 key derivation, streaming == one-shot, xxHash sharding
Compress workbench	moon run examples/compress_workbench	infra_compress	DEFLATE/zlib/gzip/zstd/LZ4 ratio shoot-out, lossless round-trips, dictionary compression, corrupted-archive rejection
Time scheduler	moon run examples/time_scheduler	infra_time + infra_timer	RFC 3339/2822 + strftime, civil arithmetic, POSIX TZ DST rules, duration round-trip, timer wheel, work-stealing scheduler with real steals
Resilience gateway	moon run examples/resilience_gateway	infra_resilience	Capped backoff + retry, circuit-breaker state machine, token bucket vs sliding window, bulkhead, AIMD, hedged requests
CLI devtool	moon run examples/cli_devtool	infra_cli	Subcommand parsing with defaults, typed validation with choices, typo suggestions, bundled shorts, generated help + bash completion
Observability kit	moon run examples/observability_kit	infra_metrics	HDR histogram tail percentiles, mergeable DDSketch quantiles, span tracer with total vs self time
Text editor core	moon run examples/text_editor_core	infra_text + infra_ds	Rope + piece-table edits converge, graphemes/display width, Myers diff, LRU eviction, bloom filter, roaring-bitmap intersection
Parser playground	moon run examples/parser_playground	parser_combinator	Precedence-correct expression eval, JSON with rendered error positions, error recovery diagnostics, incremental chunked parsing
PBT & fuzz lab	moon run examples/pbt_fuzz_lab	infra_pbt + infra_fuzz	Property checking, shrinking to boundary counterexample (500), distribution stats, round-trip laws, seeded graph fuzzing + structural shrinking

Verify all example outputs with checked markers:

bash scripts/demos_guard.sh

Latest evidence: docs/examples/latest-examples-run.md and docs/examples/latest-examples-run.json.

Hands-on tutorials for every direction (key APIs + minimal snippets + the demo that exercises them): docs/tutorials/README.md (中文版: docs/zh/tutorials.md).

---

Release Readiness

Package metadata is checked against mooncakes.io publishing expectations: SemVer version, SPDX license, repository, homepage, keywords, README, changelog, and package artifact generation.

pwsh -NoLogo -NoProfile -ExecutionPolicy Bypass -File scripts\release_guard.ps1

Latest evidence: docs/release/latest-release-readiness.md and docs/release/latest-release-readiness.json. The current local guard passes with one environment warning: moon publish --dry-run needs mooncakes credentials from moon login or CI secrets.

---

Algorithm Catalog

当前已落地 30 种经典图/路径算法 与 8 种前沿算法。 CH / ALT / Hub Labeling 已有生产级稠密快路径变体（src/directed/）； ALT 的 farthest-first 地标选择会优先为尚未覆盖的非连通分量播种， 避免重复地标削弱启发式；三者均附真实 OSM 路网基准证据（北京驾车网： CH 相对双向 Dijkstra 46.7×，HL 距离查询 0.47 µs（13279×），PHAST 一到全 SSSP 相对全量 Dijkstra 6.27×，many-to-many 64×64 距离表相对逐对 CH 16–27×，RPHAST 目标子集限定再提 7.2–9.4×，见 benches/results/osm-real-networks-ch-native-2026-07-08.md、 benches/results/osm-alt-hl-native-2026-07-08.md； 2026-07-12 异机复测同量级可复现，见 benches/results/osm-suite-native-2026-07-12.md）。HL 支持路径还原 （query_via / query_path）。

#	Algorithm	Module	Status	Paper
1	BFS	src/unweighted/bfs.mbt	✅ v0.0.1	— (folklore / Moore 1959)
2	DFS	src/directed/dfs.mbt	✅ v0.0.1	— (folklore / Tarjan 1972)
3	Dijkstra	src/directed/dijkstra.mbt	✅ v0.0.1	Dijkstra 1959
4	A*	src/directed/astar.mbt	✅ v0.0.1	Hart, Nilsson & Raphael 1968
5	Bellman-Ford	src/directed/bellman_ford.mbt	✅ v0.0.1	Bellman 1958
6	Floyd-Warshall	src/directed/floyd_warshall.mbt	✅ v0.0.1	Floyd 1962
7	Kruskal MST	src/undirected/kruskal.mbt	✅ v0.0.1	Kruskal 1956
8	Connected Components	src/undirected/connected_components.mbt	✅ v0.0.1	— (Hopcroft & Tarjan 1973)
9	Bidirectional BFS	src/directed/bidirectional_bfs.mbt	✅ v0.0.1	Pohl 1971
10	Topological Sort	src/directed/topo_sort.mbt	✅ v0.0.1	Kahn 1962
11	Tarjan SCC	src/directed/tarjan_scc.mbt	✅ v0.0.1	Tarjan 1972
12	Edmonds-Karp (Max-Flow)	src/directed/edmonds_karp.mbt	✅ v0.0.1	Edmonds & Karp 1972
13	IDA*	src/directed/ida_star.mbt	✅ v0.0.1	Korf 1985
14	Yen K-Shortest Paths	src/directed/yen.mbt	✅ v0.0.1	Yen 1971
15	Kuhn-Munkres (Hungarian)	src/undirected/kuhn_munkres.mbt	✅ v0.0.1	Kuhn 1955
16	Prim MST	src/undirected/prim.mbt	✅ v0.0.2	Prim 1957
17	DAG Shortest Path	src/directed/dag_shortest_path.mbt	✅ v0.0.2	— (CLRS §24.2; supports negative edges)
18	Bridges & Articulation Points	src/undirected/bridges.mbt	✅ v0.0.2	Tarjan 1974
19	Bidirectional Dijkstra	src/directed/bidirectional_dijkstra.mbt	✅ v0.0.2	Pohl 1971
20	Dijkstra (full SSSP tree)	src/directed/dijkstra_all.mbt	✅ v0.0.3	Dijkstra 1959
21	BFS (full SSSP tree)	src/unweighted/bfs_all.mbt	✅ v0.0.3	— (folklore / Moore 1959)
22	Bellman-Ford (path tree)	src/directed/bellman_ford_paths.mbt	✅ v0.0.3	Bellman 1958
23	Floyd-Warshall + paths	src/directed/floyd_warshall_paths.mbt	✅ v0.0.3	Floyd 1962
24	Johnson (all-pairs, sparse)	src/directed/johnson.mbt	✅ v0.0.3	Johnson 1977
25	Dinic (Max-Flow)	src/directed/dinic.mbt	✅ v0.0.3	Dinitz 1970
26	Min s-t Cut	src/directed/min_cut.mbt	✅ v0.0.3	Ford & Fulkerson 1956
27	Min-Cost Max-Flow	src/directed/min_cost_flow.mbt	✅ v0.0.3	Edmonds & Karp 1972
28	Hopcroft-Karp Matching	src/undirected/hopcroft_karp.mbt	✅ v0.0.3	Hopcroft & Karp 1973
29	Eulerian Path (Hierholzer)	src/directed/eulerian.mbt	✅ v0.0.3	— (Hierholzer 1873)
30	SCC Condensation DAG	src/directed/condensation.mbt	✅ v0.0.3	Tarjan 1972
31	🔥 Contraction Hierarchies	src/advanced/ch.mbt · 生产级 src/directed/ch.mbt	✅ OSM 实测 46.7×	Geisberger, Sanders, Schultes & Delling 2008
32	🔥 Jump Point Search	src/advanced/jps.mbt	🧪 experimental	Harabor & Grastien 2011
33	🔥 ALT (A* + Landmarks + Δ)	src/advanced/alt.mbt · 生产级 src/directed/alt.mbt	✅ OSM 实测 6.5×	Goldberg & Harrelson 2005 (SODA)
34	🔥 Hub Labeling (2-hop)	src/directed/hub_labels.mbt	✅ OSM 实测 13279×	Abraham, Delling, Goldberg & Werneck 2011
35	🔥 PHAST (一到全 SSSP)	src/directed/phast.mbt	✅ OSM 实测 6.27×	Delling, Goldberg, Nowatzyk & Werneck 2011
36	🔥 Many-to-many 距离表	src/directed/many_to_many.mbt	✅ OSM 实测 16–27×	Knopp, Sanders, Schultes, Schulz & Wagner 2007
37	🔥 RPHAST (目标子集限定)	src/directed/rphast.mbt	✅ OSM 实测 7.2–9.4×	Delling, Goldberg, Nowatzyk & Werneck 2011
38	🔥 Customizable CH (CCH)	src/directed/cch.mbt	✅ OSM 实测换权 13–19×	Dibbelt, Strasser & Wagner 2014

✅ v0.0.1 = 源码 + 单元测试 + PBT 已合入主干 ✅ v0.0.2 = 新增算法（Prim / DAG-SP / 桥与割点 / 双向 Dijkstra），源码 + 单元测试已合入主干 ✅ v0.0.3 = 系统性补全：全表单源最短路树（Dijkstra/BFS/Bellman-Ford）、全对最短路（Floyd-Warshall 路径重建 / Johnson）、网络流家族（Dinic / 最小割 / 最小费用最大流）、匹配（Hopcroft-Karp）、欧拉路径、SCC 缩点 DAG 🧪 experimental = source + tests exist, but API/performance evidence is not yet frozen 🔥 = Rust pathfinding crate 未实现的独家算法 (对应 R18 前沿算法撒手锏)

---

Playground

Status: live — in-browser WASM demo, deployed to GitHub Pages on every push to main (.github/workflows/pages.yml).

Interactive grid pathfinding visualiser, powered by the very library in src/ compiled to wasm-gc:

• Live demo: https://Suquster.github.io/moonbit-pathfinding/
• moon build --target wasm-gc --release links the src/playground export layer into a ≤ 100 KB playground.wasm (enforced by scripts/wasm_size_guard.ps1 in CI)
• Paint walls with the mouse, drag start/goal, and watch BFS / DFS / Dijkstra / A* / JPS expand frame-by-frame at 60 fps with a live FPS meter
• Three-tier fallback (wasm-gc → JS glue → pure-JS) so the demo runs in any environment, including fully offline (python -m http.server from playground/web/ + the built .wasm)
• Bridge correctness is test-gated: playground/solver_test.mbt and src/playground/*_test.mbt assert the playground answers are identical to the library's
• Real OSM road network mode (https://Suquster.github.io/moonbit-pathfinding/osm.html): the Xiamen driving network (125k nodes / 216k edges, OpenStreetMap © contributors, ODbL 1.0) is loaded into the same wasm-gc engine via the pg_osm_* graph export layer; click any two points to snap to the nearest road nodes and run unidirectional vs. bidirectional Dijkstra with live settled-node and timing comparison (identical costs cross-checked on every query). The network artifact is reproducible via python3 scripts/build_playground_osm.py

对应需求: R16 (WASM Playground) · R26 (实时 JPS Playground 杀手锏)。

---

Formal verification

状态: executable runtime predicates exist today; src/proofs is proof-enabled, and scripts/proof_evidence.ps1 records the current moon prove result or the exact local toolchain blocker.

The src/proofs/ package encodes post-condition predicates as ordinary MoonBit functions and tests them in CI. These predicates are the contract vocabulary that moon prove annotations can reference as the verifier surface settles. Official MoonBit documentation currently describes moon prove as experimental, backed by Why3 and SMT solvers.

算法	证明性质	状态
bfs	start/end/edge-validity/minimality/None-witness post-conditions, including bad-witness rejection	✅ runtime-checked
dijkstra	non-negative outputs, weighted path-validity, cost consistency, including bad-witness rejection	✅ runtime-checked
moon prove static discharge	proof-enabled package, Why3-backed verifier invocation	environment-gated

Run the current evidence chain with:

pwsh -NoLogo -NoProfile -ExecutionPolicy Bypass -File scripts\proof_evidence.ps1

Latest local evidence is stored in docs/verification/latest-proof-evidence.md. On this machine, runtime proof predicates passed, moon prove --help is available, and static discharge is blocked because Why3 is not on PATH.

对应需求: R8 (形式化证明撒手锏) · R25 (答辩故事张力)。

---

Benchmarks

对应 tasks.md 29.x · Requirements R14.1 / R14.2 · design.md §15.4

moonbit-pathfinding 以 benches/ 目录承载可复现、可 CI 回归的性能证据： moon test smoke guards 验证工作负载正确性，moon bench 原生 @bench.T 块记录更低噪声的算法级时间。当前基准覆盖 4 个 MVP 算法：

算法	基准文件	输入规模	图形	期望
BFS	benches/bfs_bench/bfs_bench.mbt	1k 节点 × ~10k 边	随机稀疏有向图 (density 1%)	求 0 → 999 最短路径
Dijkstra	benches/dijkstra_bench/dijkstra_bench.mbt	1k 节点 × ~10k 带权边	权值 ∈ [1, 10]	求 0 → 999 最小代价
A*	benches/astar_bench/astar_bench.mbt	32×32 = 1024 节点	开放网格 4-向	(0,0) → (31,31)，cost = 62
Kruskal MST	benches/kruskal_bench/kruskal_bench.mbt	1k 节点 × 10k 无向带权边	权值 ∈ [1, 100]	MST 包含 ≤ 999 条边

运行

chcp 65001
moon test
pwsh -NoLogo -NoProfile -ExecutionPolicy Bypass -File scripts\benchmark_native.ps1
pwsh -NoLogo -NoProfile -ExecutionPolicy Bypass -File scripts\benchmark_native_guard.ps1
pwsh -NoLogo -NoProfile -ExecutionPolicy Bypass -File scripts\benchmark_smoke.ps1
pwsh -NoLogo -NoProfile -ExecutionPolicy Bypass -File scripts\benchmark_guard.ps1

每个基准文件都有 test "smoke: ..." 和 test "bench: ..." (b : @bench.T) 两层入口：前者进入普通测试，后者由 moon bench 采样。 scripts/benchmark_native.ps1 会生成算法级结果： benches/results/latest-native.md 与 benches/results/latest-native.json。 scripts/benchmark_native_guard.ps1 会把当前 native run 写入 _build/native-benchmark-guard/ 临时目录，并和 checked-in baseline 比较 median moon bench mean timing，生成 benches/results/latest-native-guard.md 与 benches/results/latest-native-guard.json。 scripts/benchmark_smoke.ps1 会额外生成可审计结果： benches/results/latest-smoke.md 与 benches/results/latest-smoke.json。 scripts/benchmark_guard.ps1 会把当前 smoke run 写入 _build/benchmark-guard/ 临时目录，并和 checked-in baseline 比较 median，生成 benches/results/latest-guard.md 与 benches/results/latest-guard.json。

对标 Rust pathfinding crate（✅ published head-to-head）

A reproducible head-to-head comparison against Rust's pathfinding crate (v4.11.0, cargo --release) is published in benches/results/latest-rust-comparison.md (run via pwsh scripts/rust_comparison.ps1; native backend, bit-identical xorshift64 workloads with a golden element-wise cross-check, per-query result signatures verified equal on both sides):

• Same-algorithm tier (unidirectional BFS / Dijkstra / A* on both sides, 18/18 cases included, up to 100k nodes / 1.6M edges): median speedup ≈2.7× over Rust (range 2.1–3.6×).
• Library-capability bonus tier: this library's bidirectional variants (no counterpart API in the Rust crate) reach 8–68× over its own unidirectional baseline on the same workloads, with signatures cross-checked element-wise — reported separately and excluded from the same-algorithm speedup, so no unsupported claims.

Beyond the Rust comparison, checked-in benches/results/*.json artifacts are local regression evidence. Native artifacts record moon bench statistics from @bench.T blocks; smoke artifacts record end-to-end package timing. Both include machine, backend, input size, command output, and methodology so regressions can be discussed with concrete data.

The native guard defaults to a 25% regression tolerance. The smoke guard remains available with a deliberately loose 50% default because it times end-to-end moon test -p ... package execution.

OSM 真实路网（✅ landed · Tier-3）

真实 OSM 路网基准已落地（benches/advanced_bench/osm_alt_bench.mbt， 厦门/北京驾车网）：单向/双向 Dijkstra、ALT 双向 A*、CH 四档同批 查询对拍 + 计时，证据归档于 benches/results/osm-alt-hl-native-2026-07-08.md 与 benches/results/osm-real-networks-ch-native-2026-07-08.md（历史：alt-indexed-osm-20260705.md、ch-osm-20260705.md）。任何加速比都必须来自 benches/results/ 中记录的机器、backend、输入和原始计时。

---

Multi-backend consistency · 四后端一致性

对应 tasks.md 39.x · Requirement R17 · design.md §15.1

This library is built to compile and run identically on all four MoonBit backends: wasm-gc, js, native, and pure wasm (linear memory). Every push to main and every PR triggers the ci workflow's 4-backend matrix, which executes the full test suite (2683 cases) on each backend, plus a WASI delivery gate (scripts/wasi_gate.sh) that runs the release wasm artifacts under wasmtime and byte-diffs the output against the js backend, and a component model gate (scripts/component_gate.sh) that componentizes the core wasm modules via the wasi_snapshot_preview1 command adapter (wasm-tools component new), validates the component-model binaries, and runs them under wasmtime with the same byte-level diff against the js backend. Any output divergence — including snapshot mismatches from inspect(..., content=...) — fails the entire build, giving us a differential test of algorithmic behaviour across backends for free.

Backend × Algorithm matrix

Algorithm	wasm-gc	js	native	Notes
BFS, DFS, Dijkstra, A*, Bellman-Ford, Floyd-Warshall	✅	✅	✅	MVP, uniform
Kruskal, Connected Components, Bidirectional BFS	✅	✅	✅
Topological Sort, Tarjan SCC, Edmonds-Karp	✅	✅	✅
IDA*, Yen K-shortest, Kuhn-Munkres	✅	✅	✅
Contraction Hierarchies (CH)	✅	✅	✅	correctness-first implementation
Jump Point Search (JPS)	✅	✅	✅	v1.0.0 ship
ALT (A* + Landmarks)	✅	✅	✅	v1.0.0 ship

Performance evidence

Current benchmark tests are smoke gates, not a published backend comparison. The repository now includes reproducible smoke artifacts under benches/results/ with:

Required field	Why it matters
MoonBit version and target backend	Toolchain performance changes over time
Machine / OS / CPU	Makes local numbers interpretable
Input generator and seed	Allows exact reruns
Algorithm, graph size, edge count, query count	Prevents vague benchmark claims
Raw timing and summary statistics	Keeps release notes auditable

Native and smoke regression guards are available through scripts/benchmark_native_guard.ps1, scripts/benchmark_guard.ps1, and optional local acceptance:

pwsh -NoLogo -NoProfile -ExecutionPolicy Bypass -File scripts\acceptance.ps1 -SkipCoverage -RunNativeBenchmarkGuard -RunBenchmarkGuard

The native guard is the lower-noise gate; the smoke guard remains useful for package-level harness regressions.

Target restrictions

Currently no algorithm is backend-restricted. Future additions that rely on backend-specific features (e.g. SIMD intrinsics on native) will declare supported_targets in their moon.pkg.json. Template follows design.md §15.1.

---

---

Acknowledgements · 致谢

This project stands on the shoulders of three communities:

1. MoonBit Team & Community — for the toolchain, Discourse feedback, and the hard work behind moon prove, Markdown-oriented programming, and the three-backend ecosystem that makes this library possible.
2. Rust pathfinding crate authors (evenfurther & contributors) — for the minimalist "successor function" API philosophy that we ported into MoonBit. Thank you for a decade of principled design in open source.
3. OSC 2026 mentors & reviewers — for the spec-driven methodology and continuous, candid feedback during Milestones 0–3.

External code reviewers and discussion participants who shaped this library (alphabetical, by GitHub handle) are recorded in docs/community/ as the project grows. Pull requests are warmly welcomed — see CONTRIBUTING.md.

For code agents and scripted integrations, see AI_AGENT_USAGE.md.

For the full development story — design tradeoffs, the road-network SOTA climb (Dijkstra → ALT → CH → Hub Labeling), falsified experiments, and the human–AI collaboration record — see the development article (Chinese): docs/zh/development-article.md.

---

License

Apache-2.0 © 2026 Suquster. See LICENSE.

Benchmark fixtures under cache/ contain map data © OpenStreetMap contributors, retrieved via the Overpass API and redistributed under the ODbL 1.0 license.