MoonGraph is a general-purpose graph data-structure and algorithm library written entirely in MoonBit. It provides a generic adjacency-list graph, pathfinding, connectivity analysis, scheduling utilities, network flow, matching, and Graphviz DOT export without third-party runtime dependencies.
Features
Core graph model
Graph[N, E] stores generic node weights N and edge weights E.
Directed and undirected graphs are supported.
Safe node and edge inspection: indices, weights, degrees, adjacency checks, and invalid-index handling.
The library reports unreachable integer distances as 2147483647, matching the existing single-source shortest-path APIs. Maximum flow accepts non-negative integer capacities, aggregates parallel directed edges, and rejects unsupported input with Result errors.
The application layer also includes a dependency planner for compiler and build pipelines. Task and TaskPlan model named jobs, dependencies, durations, earliest start and finish times, makespan, and critical-path length; invalid durations, duplicate task names, missing dependencies, and cycles are reported as errors.
Install and import
Install the module from Mooncakes:
moon add wedarp/moongraph
The source package is imported as wedarp/moongraph/src:
import {
"wedarp/moongraph/src" @moongraph,
}
fn main {
let graph : @moongraph.Graph[String, Int] =
@moongraph.Graph::new(directed=true)
let source = graph.add_node("source")
let sink = graph.add_node("sink")
let _ = graph.add_edge(source, sink, 7)
println("\{graph.node_count()}")
}
Runnable demo
The repository includes a standalone command package that imports the library through its public module path:
moon run cmd/demo --target wasm-gc
Expected output includes node and edge counts, a BFS summary, a shortest-path result, a topological-order summary, and Graphviz DOT text. Native execution is also supported when a system C compiler is available:
moon run cmd/demo --target native
Development and verification
The workflow follows the MoonBit community check template and installs the currently available official stable MoonBit toolchain through the latest channel. Historical binary archives are not consistently downloadable from the installer service, so the workflow uses the supported channel and records the exact toolchain with moon version --all.
moon version --all
moon update
moon fmt
git restore -- cmd/demo/moon.pkg cmd/benchmark/moon.pkg
git diff -- '*.mbt' '*.mbti'
git diff --exit-code
moon check --target all --deny-warn
moon build --target all --deny-warn
moon test --target all --deny-warn
moon run cmd/benchmark --target wasm-gc
moon info
On a machine without a native C compiler, the WebAssembly target is sufficient for local validation:
moon check --target wasm-gc --deny-warn
moon build --target wasm-gc --deny-warn
moon test --target wasm-gc --deny-warn
moon run cmd/demo --target wasm-gc
The acceptance revision contains 42 automated tests across the core data structure, algorithm, scheduling, routing, sampling, centrality, and compressed-storage modules. The current checkout measures 38 MoonBit source files and 4,305 lines including tests, with 3,523 production lines; generated _build and .mbti files are ignored.
Reproducible benchmark data
Run the deterministic benchmark suite with:
moon run cmd/benchmark --target wasm-gc
The suite uses a checked-in copy of the standard Zachary Karate Club network, a compiler dependency pipeline, and a generated sparse network. The expected measurements below are regression anchors, not performance claims:
Workload
Input
Expected measurements
Zachary Karate Club
34 nodes, 78 undirected edges
45 triangles, 1 component, diameter 5, average distance 2.408199
Compiler pipeline
12 tasks with dependency edges
makespan 45, critical-path length 11
Sparse network
500 nodes, 600 directed edges
500 reachable from node 0, diameter 84, distance from 0 to 499 is 67
The Karate Club edge list is in bench/data/karate_club_edges.csv, with provenance and the upstream NetworkX/Zachary references in bench/data/README.md. The benchmark embeds its inputs so that the wasm command is reproducible without downloading data.
Boundary tests cover empty graphs, isolated nodes, invalid indices, self-loops, parallel edges, disconnected graphs and forests, negative capacities and task durations, missing dependencies, cycles, unreachable nodes, saturated path counts, zero and negative walk lengths, deterministic routing, multi-source BFS, k-hop limits, invalid CSR rows, mask length errors, and centrality on disconnected graphs.
MoonGraph is an independent MoonBit implementation. The project references petgraph for ecosystem positioning, common graph-algorithm terminology, and API-scope comparison; it does not copy petgraph source code. MoonGraph itself is released under MIT; petgraph remains under its upstream MIT/Apache-2.0 dual license.
Contributing
Keep public APIs documented, add a regression test for every behavior change, run the commands above before committing, and keep the public repository history attributable to the project creator. New algorithms should state their input constraints and asymptotic complexity.
Changelog
Acceptance revision
Added cross-platform CI using the official latest stable MoonBit toolchain.
Migrated project metadata to the current moon.mod and moon.pkg format.
Added safe graph inspection APIs and invalid-index handling.
Added connectivity, closure, all-pairs shortest paths, DAG analysis, graph coloring, low-link analysis, max-flow, matching, Eulerian trails, Prim forests, shortest-path reconstruction, and topological layers.
Added a standalone cmd/demo package and reproducible validation commands.
Added compiler-pipeline dependency planning with makespan and critical-path reporting.
MoonGraph
MoonGraph 是一个纯 MoonBit 实现的通用图论数据结构与算法基础库,面向依赖解析、网络拓扑、路径规划、编译器基础设施和教学实验等场景。项目采用邻接表存储,节点和边支持泛型权重,算法模块零第三方运行时依赖。
MoonGraph is a general-purpose graph data-structure and algorithm library written entirely in MoonBit. It provides a generic adjacency-list graph, pathfinding, connectivity analysis, scheduling utilities, network flow, matching, and Graphviz DOT export without third-party runtime dependencies.
Features
Core graph model
Algorithms
The library reports unreachable integer distances as 2147483647, matching the existing single-source shortest-path APIs. Maximum flow accepts non-negative integer capacities, aggregates parallel directed edges, and rejects unsupported input with Result errors.
The application layer also includes a dependency planner for compiler and build pipelines. Task and TaskPlan model named jobs, dependencies, durations, earliest start and finish times, makespan, and critical-path length; invalid durations, duplicate task names, missing dependencies, and cycles are reported as errors.
Install and import
Install the module from Mooncakes:
The source package is imported as wedarp/moongraph/src:
Runnable demo
The repository includes a standalone command package that imports the library through its public module path:
Expected output includes node and edge counts, a BFS summary, a shortest-path result, a topological-order summary, and Graphviz DOT text. Native execution is also supported when a system C compiler is available:
Development and verification
The workflow follows the MoonBit community check template and installs the currently available official stable MoonBit toolchain through the
latestchannel. Historical binary archives are not consistently downloadable from the installer service, so the workflow uses the supported channel and records the exact toolchain withmoon version --all.On a machine without a native C compiler, the WebAssembly target is sufficient for local validation:
The acceptance revision contains 42 automated tests across the core data structure, algorithm, scheduling, routing, sampling, centrality, and compressed-storage modules. The current checkout measures 38 MoonBit source files and 4,305 lines including tests, with 3,523 production lines; generated _build and .mbti files are ignored.
Reproducible benchmark data
Run the deterministic benchmark suite with:
The suite uses a checked-in copy of the standard Zachary Karate Club network, a compiler dependency pipeline, and a generated sparse network. The expected measurements below are regression anchors, not performance claims:
The Karate Club edge list is in bench/data/karate_club_edges.csv, with provenance and the upstream NetworkX/Zachary references in bench/data/README.md. The benchmark embeds its inputs so that the wasm command is reproducible without downloading data.
Boundary tests cover empty graphs, isolated nodes, invalid indices, self-loops, parallel edges, disconnected graphs and forests, negative capacities and task durations, missing dependencies, cycles, unreachable nodes, saturated path counts, zero and negative walk lengths, deterministic routing, multi-source BFS, k-hop limits, invalid CSR rows, mask length errors, and centrality on disconnected graphs.
Repository and provenance
MoonGraph is an independent MoonBit implementation. The project references petgraph for ecosystem positioning, common graph-algorithm terminology, and API-scope comparison; it does not copy petgraph source code. MoonGraph itself is released under MIT; petgraph remains under its upstream MIT/Apache-2.0 dual license.
Contributing
Keep public APIs documented, add a regression test for every behavior change, run the commands above before committing, and keep the public repository history attributable to the project creator. New algorithms should state their input constraints and asymptotic complexity.
Changelog
Acceptance revision
License
MoonGraph is released under the MIT License. See LICENSE.