#dag #directed-acyclic-graph #graph #lib #store

xdag

A simple Rust DAG(Directed Acyclic Graph) lib

5 releases

0.1.4 Sep 15, 2022
0.1.3 Sep 14, 2022
0.1.2 Sep 13, 2022
0.1.1 Sep 1, 2022
0.1.0 Sep 1, 2022

#2192 in Data structures

MIT license

28KB
590 lines

XDag

A simple DAG (Directed Acyclic Graph) library

Note

This lib just provides a data-structure to store DAG with checking. It doesn't contain any algorithm about DAG.

Details

XDAG stores DAG by HashMap. it CANNOT ensure the order of children and edges

Docs

docs.rs

Examples

// Create a new DAG
let mut dag = Dag::new();
// insert 3 nodes with data '()'
dag.insert_node(2, ());
dag.insert_node(4, ());
dag.insert_node(3, ());
// insert 2 edges with data '()'
dag.insert_edge(2, 3, ()).unwrap();
dag.insert_edge(2, 4, ()).unwrap();
// Get all roots and leaves in DAG
let roots = dag.roots().map(|(id, _)| id).collect::<Vec<_>>();
let leaves = dag.leaves().map(|(id, _)| id).collect::<Vec<_>>();

assert_eq!(&roots, &[2]);
for id in [3, 4].iter() {
    assert!(leaves.contains(id))
}

lib.rs:

XDag

A simple DAG (Directed Acyclic Graph) libarary

Note

This lib just provides a data-structure to store DAG with checking. It doesn't contain any algorithm about DAG

Details

XDAG stores DAG by BTreeMap. Because it can ensure the order of edges and nodes.

Some Examples

// Create a new DAG
let mut dag = Dag::new();
// insert 3 nodes with data '()'
dag.insert_node(2, ());
dag.insert_node(4, ());
dag.insert_node(3, ());
// insert 2 edges with data '()'
dag.insert_edge(2, 3, ()).unwrap();
dag.insert_edge(2, 4, ()).unwrap();
// Get all roots and leaves in DAG
let roots = dag.roots().map(|(id, _)| id).collect::<Vec<_>>();
let leaves = dag.leaves().map(|(id, _)| id).collect::<Vec<_>>();
assert_eq!(&roots, &[2]);
for id in [3, 4].iter() {
    assert!(leaves.contains(id))
}

No runtime deps