#topological #graph #toposort #no-std

no-std heapless_topo

no-std topological sort using heapless

5 releases

0.1.4 Oct 2, 2024
0.1.3 Oct 2, 2024
0.1.2 Oct 2, 2024
0.1.1 Oct 2, 2024
0.1.0 Oct 2, 2024

#873 in Data structures

Download history 339/week @ 2024-09-28 36/week @ 2024-10-05 3/week @ 2024-10-12 1/week @ 2024-10-19

379 downloads per month

MIT license

11KB
157 lines

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

Dependencies

~440–630KB
~13K SLoC