#data-structures #dag #graph #incremental #topological

incremental-topo

Data structure to maintain an incremental topological ordering over a collection of values

3 releases

0.1.2 Aug 2, 2019
0.1.1 Sep 19, 2018
0.1.0 Sep 5, 2018

#706 in Data structures

Download history 1/week @ 2021-10-01 3/week @ 2021-10-08 3/week @ 2021-10-29 3/week @ 2021-11-05 10/week @ 2021-11-19 6/week @ 2021-11-26 17/week @ 2021-12-03 7/week @ 2021-12-10 13/week @ 2021-12-17 41/week @ 2021-12-24 16/week @ 2021-12-31 30/week @ 2022-01-07 79/week @ 2022-01-14

174 downloads per month

MIT/Apache

75KB
914 lines

Incremental Topo

Crates.io Travis CI Documentation

A data structure for maintaining an topological ordering in an incremental fashion.

Usage

To use incremental-topo, first add this to your Cargo.toml:

[dependencies]
incremental-topo = "0.1"

Next, add this to your crate:

extern crate incremental_topo;

use incremental_topo::IncrTopo;

let mut dag = IncrementalTopo::new();

dag.add_node("cat");
dag.add_node("dog");
dag.add_node("human");

assert_eq!(dag.size(), 3);

dag.add_dependency("human", "dog").unwrap();
dag.add_dependency("human", "cat").unwrap();
dag.add_dependency("dog", "cat").unwrap();

let animal_order: Vec<_> = dag.descendants("human").unwrap().map(|v| *v).collect();

assert_eq!(animal_order, vec!["dog", "cat"]);

See documentation for more details.

License

This project is dual licensed under the MIT license and Apache 2.0 license.

Dependencies

~0.5–1MB
~22K SLoC