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 (stable_toposort, stable_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)
• stable toposort of SCCs (stable_toposort_scc, stable_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::stable_toposort;

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

License

MIT OR Apache-2.0