topo_sort

在Rust中对具有依赖关系的节点集进行“循环安全”拓扑排序。基本上，它允许通过依赖关系对列表进行排序，同时检查图中的循环。如果检测到循环，则从迭代器返回 CycleError（或者如果使用 to/into_vec API，则返回 SortResults::Partial）。

拓扑排序用于对有向图的节点进行排序。典型应用包括任何需要基于依赖关系排序的东西。例如，它可以用来找到编译依赖的正确顺序，或者它可以用在不允许循环的语言中找到模块循环。应用范围无限。

示例

[dependencies]
topo_sort = "0.3"

基本示例

use topo_sort::{SortResults, TopoSort};

fn main() {
    let mut topo_sort = TopoSort::with_capacity(5);
    // read as "C" depends on "A" and "B"
    topo_sort.insert("C", vec!["A", "B"]);
    topo_sort.insert("E", vec!["B", "C"]);
    topo_sort.insert("A", vec![]);
    topo_sort.insert("D", vec!["A", "C", "E"]);
    topo_sort.insert("B", vec!["A"]);

    match topo_sort.into_vec_nodes() {
        SortResults::Full(nodes) => assert_eq!(vec!["A", "B", "C", "E", "D"], nodes),
        SortResults::Partial(_) => panic!("unexpected cycle!"),
    }
}

...或者使用迭代

use topo_sort::TopoSort;

fn main() {
    let mut topo_sort = TopoSort::with_capacity(5);
    topo_sort.insert("C", vec!["A", "B"]);
    topo_sort.insert("E", vec!["B", "C"]);
    topo_sort.insert("A", vec![]);
    topo_sort.insert("D", vec!["A", "C", "E"]);
    topo_sort.insert("B", vec!["A"]);

    let mut nodes = Vec::with_capacity(5);
    for node in &topo_sort {
        // We check for cycle errors before usage
        match node {
            Ok(node) => nodes.push(*node),
            Err(_) => panic!("Unexpected cycle!"),
        }
    }

    assert_eq!(vec!["A", "B", "C", "E", "D"], nodes);
}

循环检测

use topo_sort::TopoSort;

fn main() {
    let mut topo_sort = TopoSort::with_capacity(3);
    topo_sort.insert(1, vec![2, 3]);
    topo_sort.insert(2, vec![3]);
    assert_eq!(vec![2, 1], topo_sort.try_owned_vec_nodes().unwrap());

    topo_sort.insert(3, vec![1]); // cycle
    assert!(topo_sort.try_vec_nodes().is_err());
}

特性

• 循环检测 - 无法获取数据而无需处理循环错误
  • 选择获取“全部或无”或部分数据的方法
• 插入的节点永远不会被复制/克隆（除非明确通过 owned 方法请求）
• 仅需要节点上实现的 Eq 和 Hash
  • 有几个可选的 owned 方法需要 Clone
• 无依赖 - 仅使用 std
• 迭代或转换为 Vec 的选择
• 延迟排序 - 仅在迭代时启动排序

用法

使用 TopoSort 是一个基本的两步过程

1. 将节点和依赖关系添加到 TopoSort
2. 遍历结果 或 直接将它们存储在 Vec

• 对于第二步，有三种一般的方式来消费
  • 迭代 - 返回一个 Result，因此可以检测到每次迭代的循环
  • to/into_vec 函数 - 返回一个包含完整（无循环）或部分结果（当检测到循环时）的 SortResults 枚举
  • try_[into]_vec 函数 - 返回一个被 Result 包裹的 Vec（完整或无结果）

算法

这是使用 Kahn 算法 实现的。虽然作者在性能方面采取了一些基本的谨慎措施，但作者的使用案例对性能不敏感，并且尚未进行优化。尽管如此，作者试图在合理的范围内做出权衡，使其适用于各种使用场景，而不仅仅是作者自己的。

安全性

该包使用了两个微小的 unsafe 块，这些块使用新的 HashMap 中键的地址。这是为了通过自引用结构体来避免在拥有迭代时克隆插入的数据。由于常规迭代中没有删除（使用 iter() 或 for 循环使用 &），因此这应该是安全的，因为在借用迭代期间没有数据移动的机会。在拥有/消费迭代期间（使用 into_iter() 或不带 & 的 for 循环），我们会逐个删除条目。如果 Rust 的 HashMap 在删除过程中改变并缩小，这个迭代器可能会损坏。如果你对此感到不舒服，请简单地不要使用消费迭代。