# Graph and connectivity algorithms

This document explains the two algorithm packages added in version 0.4.0.
They are independent from the existing ordered collections so they can be
imported by compilers, build systems, schedulers, and network tools.

## Graph

src/graph stores an adjacency list and preserves vertex and edge insertion
order, making build plans and diagnostics reproducible.

```moonbit
import {
  "Hhsqoo/moon-collections/src/graph" @graph,
}

let graph : @graph.Graph[String] = @graph.Graph::new(true)
let _ = graph.add_edge("parse", "typecheck")
let _ = graph.add_edge("typecheck", "codegen")
let order = graph.topological_sort()
let path = graph.shortest_path("parse", "codegen")
```

Important operations include deterministic BFS/DFS, shortest unweighted paths,
cycle detection, topological sorting, reverse dependency graphs, and weakly
connected components. Traversal and topological sorting are O(V + E), with
O(V + E) adjacency storage. Vertex removal scans the vertex set because
incoming edges are not indexed separately.

## DisjointSet

src/disjoint_set models a fixed integer domain 0..<n. It is useful for
incremental connectivity, Kruskal-style algorithms, clustering, and grouping
resources into equivalence classes.

```moonbit
import {
  "Hhsqoo/moon-collections/src/disjoint_set" @disjoint_set,
}

let sets = @disjoint_set.DisjointSet::new(6)
let _ = sets.union(0, 1)
let _ = sets.union(1, 2)
println(sets.connected(0, 2).to_string())
println("\{sets.components()}")
```

find performs path compression and union uses rank balancing. Both are nearly
constant amortized time, O(alpha(n)). components and members are O(n). Invalid
indices return None or false rather than panic, and reset reuses allocations.

## Validation

Run the following commands with MoonBit 0.10.3:

```bash
moon fmt --check
moon check --fmt --deny-warn
moon check --target all --deny-warn
moon build --target all
moon test --target all --deny-warn
moon info
git diff --exit-code
```