heapless_topo

A bare-bones no_std implementation of topological sort, using heapless for storage.

Documentation

lib.rs:

A bare-bones no_std implementation of topological sort, using heapless for storage.

This crate assumes your main graph data is stored elsewhere and you only create a Graph temporarily with the express purpose of doing toposort. Hence the design decisions:

• only store edge information, no node payload
• consume self on sort.

Capacity requirements

The implementation uses one single const generic for all temporary data structures. In the pathological case it requires (number of graph edges) + 1, so be mindful of that: a toposort of e.g. [(0,1), (1,2)] is [0,1,2].

Usage

use heapless_topo::{Graph, Edge};
const CAPACITY: usize = 8;
// or `new_with_edges` if you have a `Vec<Edge>` already
let mut graph = Graph::<CAPACITY>::new();
graph.insert_edge(Edge::from((1,2)));
graph.insert_edge(Edge::from((0,1)));
let sorted = graph.into_topo_sorted();
let expected = [0,1,2].as_slice().try_into().unwrap();
assert_eq!(Ok(expected), sorted);

Crate features

• std for #[derive(Debug)]
• defmt-03 for #[derive(Format)] using defmt v0.3