Skip to content

Latest commit

 

History

History
144 lines (112 loc) · 4.9 KB

README.md

File metadata and controls

144 lines (112 loc) · 4.9 KB
Raw

topo_sort

Crate Docs

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) .

Topological sorts are used to sort the nodes of a unidirectional graph. Typical applications would include anything that requires dependency based sorting. For example, it could be used to find the correct order of compilation dependencies, or it could be used to find module cycles in languages that don't allow cycles. The applications are limitless.

Examples

[dependencies]
topo_sort = "0.3"

A basic example:

use topo_sort::{SortResults, TopoSort};

fn main() {
    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;

fn main() {
    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;

fn main() {
    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());
}

Features

  • Cycle detection - impossible to get data without handling cycle error
    • Choose methods for retrieving "all or nothing" or partial data
  • Inserted nodes are never copied/cloned (unless explicitly requested via owned methods)
  • Only requires Eq and Hash implemented on nodes
    • There are a few optional owned methods that require Clone
  • Dependency free - only uses std
  • Choice of iteration or converting into Vec
  • Lazy sorting - sorting is initiated on iteration only

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)

Algorithm

This is implemented using Kahn's algorithm. While basic caution was taken not to do anything too egregious performance-wise, the author's use cases are not performance sensitive, and it has not been optimized. Still, the author tried to make reasonable trade offs and make it flexible for a variety of use cases, not just the author's.

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.

It has been tested with Miri and passes all tests. (MIRIFLAGS=-Zmiri-tag-raw-pointers cargo miri test)

License

This project is licensed optionally under either: