### 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

**379** downloads per month

**MIT**license

11KB

157 lines

heapless_topo

A bare-bones

implementation of topological sort, using `no_std`

for storage.`heapless`

## Documentation

###
`lib.rs`

:

A bare-bones

implementation of topological sort, using `no_std`

for storage.`heapless`

This crate assumes your main graph data is stored elsewhere and you only create a

temporarily
with the express purpose of doing toposort. Hence the design decisions:`Graph`

- only store edge information, no node payload
- consume

on sort.`self`

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

is `[``(``0``,``1``)``,` `(``1``,``2``)``]`

.`[``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

for`std``#``[``derive``(``Debug``)``]`

for`defmt-03`

using`#``[``derive``(``Format``)``]`

v0.3`defmt`

#### Dependencies

~440–630KB

~13K SLoC