MoonPath

MoonPath is a MoonBit graph algorithms and pathfinding library. It targets reusable infrastructure for MoonBit ecosystem projects: game maps, routing tools, compiler passes, dependency planning, workflow engines, visualization tools, and any code that needs graph traversal.

This repository is prepared for the MoonBit 开源生态项目贡献赛 track. The current implementation includes a usable core, tests, a runnable demo, CI configuration, and contest submission materials under docs/.

Features

• Directed weighted graph with explicit nodes and edges.
• Dynamic graph mutation with edge removal, node removal, and edge clearing.
• Weighted graph summaries for total, minimum, and maximum edge cost.
• Edge-list export and reconstruction with Arc[N], plus node-filtered induced subgraphs and reachable subgraphs.
• Safe all-or-nothing graph construction from external edge lists with try_from_arcs.
• JSON and line-oriented text import/export for Graph[String] and Grid.
• BFS, BFS-tree, and DFS traversal helpers for directed graphs.
• Dijkstra, bidirectional Dijkstra, A*, and bidirectional A* shortest paths for non-negative weighted graphs, shortest-path tree export, DAG path enumeration, DAG longest paths for critical-path analysis, plus explicit path scoring, one-source distance maps, and all-pairs distance maps.
• Bellman-Ford helpers for negative-edge path and distance queries over raw Arc[N] inputs.
• Path result helpers for node and edge counts.
• A* search with custom heuristic functions.
• Reachability, ancestors/descendants, path existence, weak/strong connected components, connectivity predicates, graph transpose, degree queries, source/sink/isolated-node queries, graph eccentricity/diameter, topological sort, acyclicity checks, and topological layers.
• Rectangular grid helpers with blocked cells, obstacle inflation, terrain costs, terrain clearing, rectangular bulk updates, reachable-point/region analysis, connectivity predicates, 4-neighbor, 8-neighbor, no-corner-cutting 8-neighbor pathfinding, and heuristic-free Dijkstra variants.
• Grid export/rebuild helpers for blocked cells and terrain overrides.
• Grid resizing for expanded or cropped map copies.
• Grid line-of-sight checks and greedy path smoothing for reducing unnecessary waypoints.
• Grid path validation and path cost recomputation for 4-neighbor and 8-neighbor paths.
• Grid-to-graph conversion for users who want to reuse graph algorithms on tile maps.
• Formal benchmark command with deterministic workload summaries and moonbitlang/core/bench timing JSON.
• Blackbox tests covering graph search, cycle detection, graph structure, DAG layers, DFS, all-pairs distances, connectivity, grid routing, terrain costs, corner cutting, serialization, Bellman-Ford, bidirectional A*, generated graph/grid properties, and heuristic determinism.

Install

Install MoonBit from the official site, then run:

moon update
moon build
moon test

This repository was verified with:

moon 0.1.20260522
moonc v0.9.3

Usage

test "dijkstra demo" {
  let graph = @moonpath.Graph::new()
  graph.add_edge("A", "B", 4)
  graph.add_edge("A", "C", 1)
  graph.add_edge("C", "B", 2)
  graph.add_edge("B", "D", 1)
  guard graph.bidirectional_dijkstra("A", "D") is Some(path) else {
    fail("expected a path")
  }
  assert_eq(path.cost, 4)
  assert_true(path.nodes == ["A", "C", "B", "D"])
  assert_true(graph.path_cost(path.nodes) == Some(4))
}

Grid pathfinding:

test "grid demo" {
  let grid = @moonpath.Grid::from_blocked(
    5,
    4,
    [@moonpath.Point::{ x: 1, y: 0 }, @moonpath.Point::{ x: 1, y: 1 }],
  )
  let start = @moonpath.Point::{ x: 0, y: 0 }
  let goal = @moonpath.Point::{ x: 4, y: 0 }
  assert_true(grid.astar4(start, goal) is Some(_))
}

Weighted terrain and 8-direction pathfinding:

test "weighted grid demo" {
  let grid = @moonpath.Grid::new(3, 3)
  let rough = @moonpath.Point::new(1, 0)
  grid.set_cost(rough, 5)
  guard grid.dijkstra8(@moonpath.Point::new(0, 0), @moonpath.Point::new(2, 2)) is Some(path) else {
    fail("expected a path")
  }
  assert_eq(path.cost, 28)
}

Graph analysis:

test "component demo" {
  let graph = @moonpath.Graph::new()
  graph.add_edge("A", "B", 1)
  graph.add_edge("B", "A", 1)
  graph.add_edge("B", "C", 1)
  assert_eq(graph.weakly_connected_components().length(), 1)
  assert_eq(graph.strongly_connected_components().length(), 2)
}

Dependency direction:

test "dependency direction demo" {
  let graph = @moonpath.Graph::new()
  graph.add_edge("parse", "compile", 1)
  graph.add_edge("compile", "package", 1)
  assert_true(graph.descendants("parse") == ["compile", "package"])
  assert_true(graph.ancestors("package").length() == 2)
}

Distance maps and DAG layers:

test "analysis demo" {
  let graph = @moonpath.Graph::new()
  graph.add_edge("parse", "compile", 2)
  graph.add_edge("parse", "lint", 1)
  graph.add_edge("compile", "package", 3)
  let distances = graph.distances_from("parse")
  assert_eq(distances.get_or_default("package", -1), 5)
  assert_true(graph.topological_layers() is Some(_))
}

DAG critical path:

test "dag longest path demo" {
  let graph = @moonpath.Graph::new()
  graph.add_edge("start", "A", 2)
  graph.add_edge("start", "B", 1)
  graph.add_edge("A", "done", 3)
  graph.add_edge("B", "done", 8)
  guard graph.dag_longest_path("start", "done") is Some(path) else {
    fail("expected a critical path")
  }
  assert_eq(path.cost, 9)
  assert_true(path.nodes == ["start", "B", "done"])
}

DAG path enumeration:

test "dag path enumeration demo" {
  let graph = @moonpath.Graph::new()
  graph.add_edge("start", "lint", 1)
  graph.add_edge("start", "compile", 2)
  graph.add_edge("lint", "package", 3)
  graph.add_edge("compile", "package", 4)
  assert_eq(graph.dag_paths("start", "package").length(), 2)
}

All-pairs distances and graph summary:

test "summary demo" {
  let graph = @moonpath.Graph::new()
  graph.add_edge("A", "B", 2)
  graph.add_edge("B", "C", 3)
  let all = graph.all_pairs_distances()
  guard all.get("A") is Some(from_a) else { fail("missing A") }
  assert_eq(from_a.get_or_default("C", -1), 5)
  assert_true(graph.has_path("A", "C"))
  assert_true(graph.diameter() == Some(5))
}

Shortest-path trees:

test "shortest path tree demo" {
  let graph = @moonpath.Graph::new()
  graph.add_edge("A", "B", 5)
  graph.add_edge("A", "C", 2)
  graph.add_edge("C", "B", 1)
  let tree = graph.shortest_path_tree("A")
  assert_eq(tree.length(), 2)
}

Traversal tree export:

test "bfs tree demo" {
  let graph = @moonpath.Graph::new()
  graph.add_edge("A", "B", 1)
  graph.add_edge("A", "C", 2)
  graph.add_edge("B", "D", 3)
  let tree = graph.bfs_tree("A")
  assert_eq(tree.length(), 3)
}

Reachable subgraphs:

test "reachable subgraph demo" {
  let graph = @moonpath.Graph::new()
  graph.add_edge("A", "B", 1)
  graph.add_edge("B", "C", 2)
  graph.add_edge("X", "Y", 3)
  let subgraph = graph.reachable_subgraph("A")
  assert_eq(subgraph.node_count(), 3)
  assert_true(!subgraph.contains_node("X"))
}

Edge-list workflows:

test "edge list demo" {
  let graph = @moonpath.Graph::new()
  graph.add_edge("A", "B", 2)
  graph.add_edge("B", "C", 3)
  let rebuilt = @moonpath.Graph::from_arcs(graph.arcs())
  assert_true(rebuilt.path_cost(["A", "B", "C"]) == Some(5))
  let subgraph = graph.induced_subgraph(node => node != "C")
  assert_true(!subgraph.contains_node("C"))
}

Safe graph construction:

test "safe build demo" {
  let arcs = [
    @moonpath.Arc::{ from: "A", to: "B", cost: 2 },
    @moonpath.Arc::{ from: "B", to: "C", cost: 3 },
  ]
  assert_true(@moonpath.Graph::try_from_arcs(arcs) is Some(_))
}

Serialization:

test "serialization demo" {
  let graph = @moonpath.Graph::new()
  graph.add_node("isolated")
  graph.add_edge("A", "B", 2)
  let json = graph.to_json_string()
  assert_true(@moonpath.Graph::from_json_string(json) is Some(_))
  let text = graph.to_text()
  assert_true(@moonpath.Graph::from_text(text) is Some(_))
}

Bellman-Ford for negative edges:

test "bellman ford demo" {
  let arcs = [
    @moonpath.Arc::{ from: "S", to: "A", cost: 4 },
    @moonpath.Arc::{ from: "A", to: "T", cost: -2 },
  ]
  guard @moonpath.bellman_ford_path(["S", "A", "T"], arcs, "S", "T")
    is Some(path) else {
    fail("expected a path")
  }
  assert_eq(path.cost, 2)
}

Dynamic graph updates:

test "mutation demo" {
  let graph = @moonpath.Graph::new()
  graph.add_edge("A", "B", 1)
  graph.add_edge("A", "C", 2)
  assert_eq(graph.remove_edge("A", "B"), 1)
  assert_true(!graph.contains_edge("A", "B"))
  assert_true(graph.remove_node("C"))
}

Weighted graph summaries:

test "weight summary demo" {
  let graph = @moonpath.Graph::new()
  graph.add_edge("A", "B", 5)
  graph.add_edge("B", "C", 2)
  assert_eq(graph.total_edge_cost(), 7)
  assert_true(graph.min_edge_cost() == Some(2))
  assert_true(graph.max_edge_cost() == Some(5))
}

Directed graph structure queries:

test "structure query demo" {
  let graph = @moonpath.Graph::new()
  graph.add_edge("parse", "compile", 1)
  graph.add_edge("compile", "package", 1)
  graph.add_node("docs")
  assert_true(graph.sources().length() == 2)
  assert_true(graph.sinks().length() == 2)
  assert_true(graph.isolated_nodes() == ["docs"])
}

Bulk grid updates:

test "bulk grid demo" {
  let grid = @moonpath.Grid::new(5, 4)
  grid.block_rect(@moonpath.Point::new(1, 1), 3, 2)
  grid.unblock_rect(@moonpath.Point::new(2, 1), 1, 2)
  grid.set_cost_rect(@moonpath.Point::new(0, 0), 2, 2, 4)
  assert_true(grid.clear_cost(@moonpath.Point::new(1, 1)))
  assert_eq(grid.clear_cost_rect(@moonpath.Point::new(0, 0), 2, 1), 2)
  let rebuilt = @moonpath.Grid::from_parts(
    5,
    4,
    grid.blocked_points(),
    grid.terrain_cells(),
  )
  assert_true(rebuilt.terrain_cost(@moonpath.Point::new(1, 1)) == Some(4))
}

Grid resizing:

test "resize demo" {
  let grid = @moonpath.Grid::new(4, 4)
  grid.block(@moonpath.Point::new(1, 1))
  grid.set_cost(@moonpath.Point::new(2, 2), 7)
  let smaller = grid.resized(3, 3)
  assert_true(smaller.is_blocked(@moonpath.Point::new(1, 1)))
  assert_true(smaller.terrain_cost(@moonpath.Point::new(2, 2)) == Some(7))
}

Obstacle inflation:

test "obstacle inflation demo" {
  let grid = @moonpath.Grid::new(5, 5)
  grid.block(@moonpath.Point::new(2, 2))
  let inflated = grid.inflated_blocks(1)
  assert_eq(inflated.blocked_points().length(), 9)
  assert_true(inflated.is_blocked(@moonpath.Point::new(1, 1)))
  assert_true(!inflated.is_blocked(@moonpath.Point::new(0, 0)))
}

Grid reachability and open regions:

test "grid region demo" {
  let grid = @moonpath.Grid::new(2, 2)
  grid.block(@moonpath.Point::new(1, 0))
  grid.block(@moonpath.Point::new(0, 1))
  assert_eq(grid.reachable_points4(@moonpath.Point::new(0, 0)).length(), 1)
  assert_eq(grid.reachable_points8(@moonpath.Point::new(0, 0)).length(), 2)
  assert_eq(grid.component_count4(), 2)
  assert_eq(grid.component_count8(), 1)
  assert_true(!grid.is_fully_connected4())
  assert_true(grid.is_fully_connected8())
}

Path smoothing:

test "smooth path demo" {
  let grid = @moonpath.Grid::new(5, 5)
  let start = @moonpath.Point::new(0, 0)
  let goal = @moonpath.Point::new(4, 4)
  let jagged = [start, @moonpath.Point::new(1, 0), @moonpath.Point::new(4, 3), goal]
  assert_true(grid.line_of_sight(start, goal))
  assert_true(grid.smooth_path(jagged) == [start, goal])
}

Path validation:

test "grid path validation demo" {
  let grid = @moonpath.Grid::new(3, 3)
  guard grid.dijkstra4(@moonpath.Point::new(0, 0), @moonpath.Point::new(2, 2))
    is Some(path) else {
    fail("expected a path")
  }
  assert_eq(path.edge_count(), path.nodes.length() - 1)
  assert_true(grid.path_valid4(path.nodes))
  assert_true(grid.path_cost4(path.nodes) == Some(path.cost))
}

Run the CLI demo:

moon run cmd/main

Expected output:

moonpath demo: cost=14, steps=11, visited=21, open=21, components=1

Run the benchmark smoke command:

moon run cmd/bench

Expected output:

moonpath bench grid: nodes=571, edges=2122, open=571, components=1, cost=48, steps=48, visited=567
moonpath bench sparse-dag: nodes=80, edges=226, layers=80, critical=79, steps=79
moonpath bench dense: nodes=36, edges=216, reachable=36, tree=35, diameter=35
moonpath bench timing: [...]

Repository Layout

• types.mbt: public data types.
• graph_core.mbt: graph construction, edge queries, degree/source/sink queries, and transpose.
• graph_search.mbt: BFS, Dijkstra, bidirectional Dijkstra, A*, bidirectional A*, Bellman-Ford, path scoring, and distance summaries.
• graph_traversal.mbt: reachability, ancestors/descendants, reachable subgraphs, path existence, BFS tree export, and DFS traversal.
• graph_components.mbt: weak/strong components, connectivity predicates, and DAG helpers.
• grid.mbt: grid construction, terrain updates, terrain clearing, obstacle inflation, reachable regions, connectivity predicates, rectangular updates, grid neighbors, and grid pathfinding.
• serialization.mbt: JSON and text import/export for string graphs and grids.
• moonpath.mbt: package-level entry point.
• moonpath_test.mbt: blackbox behavior tests.
• cmd/main: runnable example.
• cmd/bench: deterministic benchmark smoke scenarios for grid, sparse DAG, and dense graph workloads.
• .github/workflows/ci.yml: CI for format, build, tests, demo, and benchmark smoke.
• docs/project-proposal.md: one-page contest proposal draft.
• docs/development-report.md: completion report draft.
• docs/complexity.md: complexity guide and API selection notes.
• docs/api.md: public API index.
• docs/error-semantics.md: abort, None, and empty collection behavior.
• docs/release-checklist.md: release and repository metadata checklist.
• docs/submission-checklist.md: GitHub/GitLink submission checklist.
• docs/final-submission.md: final contest submission summary.
• docs/submission-form-answers.md: copy-ready contest form answers.
• docs/competition-requirements.md: extracted requirements from the contest page.

Release Status

The contest MVP roadmap items are implemented: serialization, generated property checks, bidirectional A*, negative-edge Bellman-Ford helpers, and timed benchmark summaries are all present. Version v0.30.1 is tagged and published as a GitHub Release, with GitHub, GitLink, and the desktop artifact folder synchronized.

License

Apache-2.0.