XDag

一个简单的DAG（有向无环图）库

注意

此库仅提供存储并检查DAG的数据结构。它不包含任何关于DAG的算法。

详细信息

XDAG通过HashMap存储DAG。它无法保证子节点和边的顺序

文档

docs.rs

示例

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

一个简单的DAG（有向无环图）库

注意

此库仅提供存储并检查DAG的数据结构。它不包含任何关于DAG的算法

详细信息

XDAG通过BTreeMap存储DAG。因为它可以保证边和节点的顺序。

一些示例

// 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))
}