moonbit-graph

A comprehensive graph algorithm library for MoonBit, providing graph data structures and 17+ classic graph algorithms. Pure MoonBit — no FFI dependencies.

Installation

Add to your moon.mod:

dependencies {
  "xiaohedehub/opentg": "0.1.0"
}

Or via CLI:

moon add xiaohedehub/opentg

Quick Start

let g = @graph.Graph::new()

// Add nodes
let a = g.add_node("Alice")
let b = g.add_node("Bob")
let c = g.add_node("Carol")

// Add edges
g.add_edge(a, b, 1)
g.add_edge(b, c, 2)
g.add_edge(a, c, 4)

// BFS traversal
let bfs_order = @traversal.bfs(g, a)
// => [a, b, c]

// Shortest path (Dijkstra)
let dists = @path.dijkstra(g, a, edge_cost=fn(_, e) {
  g.edge_weight(e).unwrap()
})
// dists[a] = 0, dists[b] = 1, dists[c] = 3

// Check for cycles
assert_eq!(@properties.is_cyclic_directed(g), false)

Package Structure

Package	Description
`graph`	Core graph data structures: `Graph[N, E]`, `NodeIndex`, `EdgeIndex`
`errors`	Shared error types: `Cycle`, `NegativeCycle`
`traversal`	BFS, DFS, topological sort
`path`	Dijkstra, A*, Bellman-Ford, Floyd-Warshall
`mst`	Minimum spanning tree: Kruskal, Prim
`connectivity`	Strongly connected components, bridges, articulation points
`flow`	Maximum flow: Edmonds-Karp, Dinic
`properties`	Cycle detection, bipartite check, reachability
`generators`	Random graph generation for testing
`bench`	Performance benchmarks

Algorithms

Traversal

Algorithm	Function	Complexity
BFS	`@traversal.bfs(g, start)`	O(V + E)
DFS (pre/post-order)	`@traversal.dfs(g, start)`	O(V + E)
Topological Sort	`@traversal.toposort(g)`	O(V + E)

Shortest Path

Algorithm	Function	Complexity
Dijkstra	`@path.dijkstra(g, source, edge_cost)`	O((V+E) log V)
A*	`@path.astar(g, start, is_goal, edge_cost, heuristic)`	O(V log V)
Bellman-Ford	`@path.bellman_ford(g, source, edge_cost)`	O(VE)
Floyd-Warshall	`@path.floyd_warshall(g, edge_cost)`	O(V³)

Minimum Spanning Tree

Algorithm	Function	Complexity
Kruskal	`@mst.mst_kruskal(g, edge_weight)`	O(E log E)
Prim	`@mst.mst_prim(g, root, edge_weight)`	O((V+E) log V)

Connectivity

Algorithm	Function	Complexity
Tarjan SCC	`@connectivity.tarjan_scc(g)`	O(V + E)
Kosaraju SCC	`@connectivity.kosaraju_scc(g)`	O(V + E)
Connected Components	`@connectivity.connected_components(g)`	O(V + E)
Bridges	`@connectivity.bridges(g)`	O(V + E)
Articulation Points	`@connectivity.articulation_points(g)`	O(V + E)

Maximum Flow

Algorithm	Function	Complexity
Edmonds-Karp	`@flow.edmonds_karp(g, s, t, capacity)`	O(VE²)
Dinic	`@flow.dinic(g, s, t, capacity)`	O(V²E)

Properties

Function	Description	Complexity
`@properties.is_cyclic_directed(g)`	Directed cycle detection	O(V + E)
`@properties.is_cyclic_undirected(g)`	Undirected cycle detection	O(V + E)
`@properties.is_bipartite(g)`	Bipartite check (2-coloring)	O(V + E)
`@properties.has_path(g, from, to)`	Reachability check	O(V + E)

Graph Operations

// Construction
let g = @graph.Graph::new()              // directed
let g = @graph.Graph::new_undirected()   // undirected
let g = @graph.Graph::with_directed_capacity(100, 500)
let g = @graph.Graph::with_undirected_capacity(100, 500)

// Add/Remove
let n = g.add_node(weight)               // -> NodeIndex
let e = g.add_edge(src, tgt, weight)     // -> EdgeIndex
let w = g.remove_node(node)              // -> Option[N]
let w = g.remove_edge(edge)              // -> Option[E]
g.clear()

// Query
g.node_count()                           // -> Int
g.edge_count()                           // -> Int
g.node_weight(node)                      // -> Option[N]
g.edge_weight(edge)                      // -> Option[E]
g.neighbors(node)                        // -> Iter[(NodeIndex, EdgeIndex)]
g.edges(node)                            // -> Iter[EdgeIndex]
g.find_edge(from, to)                    // -> Option[EdgeIndex]
g.out_degree(node)                       // -> Int
g.in_degree(node)                        // -> Int
g.contains_node(node)                    // -> Bool
g.contains_edge(edge)                    // -> Bool
g.is_directed()                          // -> Bool
g.is_undirected()                        // -> Bool

// Iteration
g.node_indices()                         // -> Array[NodeIndex]
g.edge_indices()                         // -> Array[EdgeIndex]

Key Design Decisions

Type-safe indices: NodeIndex and EdgeIndex are distinct structs — no accidental swaps
Edge weights are generic: Extract costs via callbacks, no trait bounds on edge types
Algorithms are free functions: Not methods on Graph, allowing future representation variants
Parallel edges supported: Real-world graphs (road networks, circuits) need them
Free-list for removals: Index stability with memory reuse
Pure MoonBit: No FFI, no C bindings — works on all MoonBit backends (native, WASM, JS)

Contributing

This project is an entry in the 2026 CCF Open Source Innovation Competition (MoonBit track). Contributions and feedback are welcome!

License

Apache License 2.0 — see LICENSE