Lib.rs

incremental-topo crate的修改版本，用于PIE和PIE教程。

该crate的目的是在单个更新（如添加新节点、添加新边、删除边和删除节点）的情况下维护拓扑顺序。

添加节点、删除节点和删除依赖项执行更新所需的工作量非常小，因为这些操作不会改变拓扑顺序。添加新的依赖项可能会改变拓扑顺序。

什么是拓扑顺序

定义拓扑顺序至少需要一个简单的图定义，特别是有向无环图（DAG）。一个图可以描述为两个集合的对，(V, E) 其中 V 是图中所有节点的集合，而 E 是边的集合。边被定义为对，(m, n) 其中 m 和 n 是节点。有向图意味着边只表示两个节点之间单一方向的关系，而与无向图不同，无向图表示关系是双向的。社交网络中无向与有向的例子是Facebook与Twitter。Facebook上的友谊是双向关系，而Twitter上的关注并不意味着他们会回关你。

一个有向无环图，ord_D 的拓扑顺序，D = (V, E) 其中 x, y ∈ V，是将节点映射到优先级值的一种方式，使得对所有边 (x, y) ∈ E，都满足 ord_D(x) < ord_D(y)。这为图 D 中的节点提供了一个全序。

示例

use pie_graph::DAG;
use std::{cmp::Ordering::*, collections::HashSet};

let mut dag = DAG::new();

let dog = dag.add_node(());
let cat = dag.add_node(());
let mouse = dag.add_node(());
let lion = dag.add_node(());
let human = dag.add_node(());
let gazelle = dag.add_node(());
let grass = dag.add_node(());

assert_eq!(dag.len(), 7);

dag.add_edge(&lion, &human, ()).unwrap();
dag.add_edge(&lion, &gazelle, ()).unwrap();

dag.add_edge(&human, &dog, ()).unwrap();
dag.add_edge(&human, &cat, ()).unwrap();

dag.add_edge(&dog, &cat, ()).unwrap();
dag.add_edge(&cat, &mouse, ()).unwrap();

dag.add_edge(&gazelle, &grass, ()).unwrap();

dag.add_edge(&mouse, &grass, ()).unwrap();

let pairs = dag
    .descendants_unsorted(&human)
    .unwrap()
    .collect::<HashSet<_>>();
let expected_pairs = [(4, cat), (3, dog), (5, mouse), (7, grass)]
    .iter()
    .cloned()
    .collect::<HashSet<_>>();

assert_eq!(pairs, expected_pairs);

assert!(dag.contains_transitive_edge(&lion, &grass));
assert!(!dag.contains_transitive_edge(&human, &gazelle));

assert_eq!(dag.topo_cmp(&cat, &dog), Greater);
assert_eq!(dag.topo_cmp(&lion, &human), Less);

来源

D. J. Pearce和P. H. J. Kelly的论文描述了三种不同的增量拓扑排序算法，并分析了每个算法的运行时间界限。