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 |
#1520 in Data structures
21 downloads per month
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)]
usingdefmt
v0.3
Dependencies
~435–620KB
~13K SLoC