有向无环图 (DAGs) 以 严格上三角矩阵 表示。

有关更多信息，请参阅 crate 文档。

lib.rs:

有向无环图 (DAGs) 以 严格上三角矩阵 表示。

这是一个用于处理DAGs的创建，其中预先知道图是有向的并且没有循环。如果您需要构建一个图并检查其中是否有循环，则此crate不适用。对此代码强加了一些假设

1. DAG顶点是整数数字 (usize)，可以简单地测试添加边是否会形成循环：只有允许边“向前”移动，即从 u 到 v，如果且仅当 u < v。否则我们将引发恐慌。
2. 顶点编号从0开始。
3. 顶点数量在构造时确定，并且增长/缩小通常需要构建新的图。

作为对这些假设的交换，您将获得以下有用的属性

• 正确性：由于构造方式，不可能存在循环！
• 紧凑性：边只是位集中的位。实现只使用 |V*|-|+|-|+|/2 位 内存 + 一个常数。
• CPU缓存局部性：边以 行主序紧致表示 存储，因此遍历顶点的邻居只需遍历位集中的 连续 位。
• 认知开销低：无需处理类型级别的技巧即可完成基本任务。
• 渐近复杂度降低：生成随机有向无环图（DAG）是一个 O(|E|) 操作。这实际上是编写此软件包的原始动机。它可以与 quickcheck 高效地一起使用。实际上，DirectedAcyclicGraph 实现了 quickcheck::Arbitrary（具有有意义的缩小）。

反功能特性

• 不支持在顶点中存储任何内容。
• 不支持为边或顶点分配权重。
• 不支持枚举顶点的 进入 边，只支持 离开 边。
• 没有 serde 实现。只需使用您选择的库序列化/反序列化边的列表。

入口点

请参阅 DirectedAcyclicGraph::empty、DirectedAcyclicGraph::from_edges_iter 或 DirectedAcyclicGraph::from_adjacency_matrix 以获取此软件包的“入口点”。