Crate topo_sort

A “cycle-safe” topological sort for a set of nodes with dependencies in Rust. Basically, it allows sorting a list by its dependencies while checking for cycles in the graph. If a cycle is detected, a CycleError is returned from the iterator (or SortResults::Partial is returned if using the to/into_vec APIs).

Examples

[dependencies]
topo_sort = "0.4"

A basic example:

use topo_sort::{SortResults, TopoSort};

let mut topo_sort = TopoSort::with_capacity(5);
// read as "C" depends on "A" and "B"
topo_sort.insert("C", vec!["A", "B"]);
topo_sort.insert("E", vec!["B", "C"]);
topo_sort.insert("A", vec![]);
topo_sort.insert("D", vec!["A", "C", "E"]);
topo_sort.insert("B", vec!["A"]);

match topo_sort.into_vec_nodes() {
    SortResults::Full(nodes) => assert_eq!(vec!["A", "B", "C", "E", "D"], nodes),
    SortResults::Partial(_) => panic!("unexpected cycle!"),
}

…or using iteration:

use topo_sort::TopoSort;

let mut topo_sort = TopoSort::with_capacity(5);
topo_sort.insert("C", vec!["A", "B"]);
topo_sort.insert("E", vec!["B", "C"]);
topo_sort.insert("A", vec![]);
topo_sort.insert("D", vec!["A", "C", "E"]);
topo_sort.insert("B", vec!["A"]);

let mut nodes = Vec::with_capacity(5);
for node in &topo_sort {
    // We check for cycle errors before usage
    match node {
        Ok((node, _)) => nodes.push(*node),
        Err(_) => panic!("Unexpected cycle!"),
    }
}

assert_eq!(vec!["A", "B", "C", "E", "D"], nodes);

Cycle detection:

use topo_sort::TopoSort;

let mut topo_sort = TopoSort::with_capacity(3);
topo_sort.insert(1, vec![2, 3]);
topo_sort.insert(2, vec![3]);
assert_eq!(vec![2,1], topo_sort.try_owned_vec_nodes().unwrap());  
   
topo_sort.insert(3, vec![1]); // cycle
assert!(topo_sort.try_vec_nodes().is_err());

Usage

Using TopoSort is a basic two step process:

1. Add in your nodes and dependencies to TopoSort
2. Iterate over the results OR store them directly in a Vec

• For step 2, there are three general ways to consume:
  • Iteration - returns a Result so cycles can be detected every iteration
  • to/into_vec functions - returns a SortResults enum with a Vec of full (no cycle) or partial results (when cycle detected)
  • try_[into]_vec functions - returns a Vec wrapped in a Result (full or no results)

Safety

The crate uses two tiny unsafe blocks which use the addresses of HashMap keys in a new HashMap. This was necessary to avoid cloning inserted data on owned iteration by self referencing the struct. Since there is no removal in regular iteration (iter() or for loop using &), this should be safe as there is no chance of the data moving during borrowed iteration. During owned/consuming iteration (into_iter() or for without &), we remove the entries as we go. If Rust’s HashMap were to change and shrink during removals, this iterator could break. If this makes you uncomfortable, simply don’t use consuming iteration.

Structs

CycleError

An error type returned by the iterator when a cycle is detected in the dependency graph

IntoTopoSortIter

Consuming/owning iterator over the final node and dependent set of the topological sort

IntoTopoSortNodeIter

Consuming/owning Iterator over the final node only of the topological sort

TopoSort

TopoSort is used as a collection to map nodes to their dependencies. The actual sort is “lazy” and is performed during iteration.

TopoSortIter

Iterator over the final node and dependent set of the topological sort

TopoSortNodeIter

Iterator over the final node only of the topological sort

Enums

SortResults

Results of the sort - either full or partial results (if a cycle is detected)