stable_toposort

Deterministic, stable topological sorting and related DAG algorithms for Rust.

What it does

Given a DAG and an ordering of nodes, the crate computes a topological order that minimizes inversions with respect to that ordering. It also provides layered order (for parallel scheduling), strongly connected components (Tarjan), and condensation.

Implemented

• stable topological sort (toposort, toposort_by_key)
• layered topological order (toposort_layers, toposort_layers_by_key)
• strongly connected components (scc, scc_by_key)
• condensation graph (condensation, condensation_by_key)
• toposort of SCCs (toposort_scc, toposort_scc_by_key)
• cycle detection (CycleError<N> with .cycle, find_cycle)

API is nodes + edges iterators; (a, b) means a → b. No graph type required.

Example

use stable_toposort::toposort::toposort;

let order = toposort(["A", "B", "C"], [("A", "C"), ("B", "C")]).unwrap();
assert_eq!(order, ["A", "B", "C"]);

License

MIT OR Apache-2.0