SwiftNodes

👩🏻‍🚀 这个项目仍然处于实验阶段。欢迎贡献者和先驱者！

SwiftNodes提供了一个并发安全的图数据结构以及图算法。图在可识别的节点中存储值，这些节点可以通过边连接。

• 为什么？
• 如何使用？
• 包含的算法
• 架构
• 开发状态
• 路线图

除了数字之外，图可能是最基本的数学概念。它们在问题解决、数据分析和可视化方面有广泛的应用。虽然这种数据结构非常适合该语言，但 Swift 中缺少图的实现，尤其是在全面的图算法库方面。

SwiftNodes 及其包含的算法是从 Codeface 中提取的。但是 SwiftNodes 足够通用，可以服务于其他应用程序，并且具有足够的可扩展性，可以添加更多算法。

• 可用性、安全性、可扩展性和可维护性——这也意味着简单。
• 特别是，API 应该感觉熟悉并且与官方 Swift 数据结构很好地配合。因此，指导其设计的一个问题是：Apple 会怎么做？

我们将上述品质置于性能之上。但这并不意味着我们必然会得到次优的性能。SwiftNodes 的主要折衷方案是节点是值类型，不能被引用，因此必须进行哈希。但这不会改变平均情况复杂度，而且将来，我们甚至可以通过利用数组索引来避免在基本用例中进行哈希。

本节是一个教程，仅涉及 SwiftNodes API 的一部分。 我们建议探索DocC 参考文档、单元测试 和 生产代码。 特别是代码实际上很小，组织得有意义且易于掌握。

让我们看看我们的第一个图

let graph = Graph<Int, Int, Double>(values: [1, 2, 3],  // values serve as node IDs
                                    edges: [(1, 2), (2, 3), (1, 3)])

Graph 在三种类型上是通用的：Graph<NodeID: Hashable, NodeValue, EdgeWeight: Numeric>。 就像 Dictionary 存储唯一键的值一样，Graph 存储唯一节点 ID 的值。 实际上，Graph 将值存储在其节点内部，我们通过它们的 ID 来识别这些节点。 与 Dictionary 不同，Graph 还允许连接其唯一的“值位置”，即其节点 ID。 这些连接是图的边，并且每条边都有一个数值权重。

因此，在上面的示例中，Graph<Int, Int, Double> 存储 Int 节点 ID 的 Int 值，并通过每条边具有 Double 权重的边连接这些节点 ID（节点）。 我们提供了这些值并指定了边。 但是，实际的 Int 节点 ID 和 Double 边权重来自哪里？ 在这两方面，上面的初始化程序都是一个相当方便的程序，可以推断出一些东西

1. 当值和节点 ID 属于同一类型（因此可哈希）时，SwiftNodes 推断我们实际上不需要不同的节点 ID，因此每个唯一值也用作其自身节点的 ID。
2. 当我们不想使用或指定边权重时，我们可以仅通过它们连接的节点 ID 来指定边，并且 SwiftNodes 将使用默认权重 1 创建相应的边。

我们可以显式提供不同的节点 ID，例如类型为 String

let graph = Graph<String, Int, Double>(valuesByID: ["a": 1, "b": 2, "c": 3],
                                       edges: [("a", "b"), ("b", "c"), ("a", "c")])

如果我们要稍后添加所有边，我们可以通过数组和字典字面量创建没有边的图

let graph = Graph<Int, Int, Double> = [1, 2, 3]  // values serve as node IDs
        _ = Graph<String, Int, Double> = ["a": 1, "b": 2, "c": 3]

在上面的两个示例中（第 1 个和第 3 个图），SwiftNodes 可以推断节点 ID，因为节点值属于同一类型。 还有另一种类型的值，我们不需要提供节点 ID：节点值，它们可以通过与节点相同类型的 ID 来 Identifiable，即 NodeID == NodeValue.ID。 在这种情况下，每个值的唯一 ID 也用作值节点的 ID。 这不适用于数组字面量，但适用于初始化程序

struct IdentifiableValue: Identifiable { let id = UUID() }
typealias IVGraph = Graph<UUID, IdentifiableValue, Double>

let values = [IdentifiableValue(), IdentifiableValue(), IdentifiableValue()]
let ids = values.map { $0.id }
let graph = IVGraph(values: values,  // value IDs serve as node IDs 
                    edges: [(ids[0], ids[1]), (ids[1], ids[2]), (ids[0], ids[2])])

有关所有初始化程序变体，请参见 Graph.swift 和 Graph+ConvenientInitializers.swift。

就像使用 Dictionary 一样，您可以通过下标和函数读取、写入和删除值

var graph = Graph<String, Int, Double>()

graph["a"] = 1
let valueA = graph["a"]
graph["a"] = nil

graph.update(2, for: "b")  // returns the updated/created `Node` as `@discardableResult`
let valueB = graph.value(for: "b")
graph.removeValue(for: "b")  // returns the removed `NodeValue?` as `@discardableResult`
        
let allValues = graph.values  // returns `some Collection`

就像图初始化程序一样，如果值本身或它们的 ID 可以用作节点 ID，则您不需要提供节点 ID。 在这里，值与其节点 ID 相同

var graph = Graph<Int, Int, Double>()

graph.insert(1)  // returns the updated/created `Node` as `@discardableResult`
graph.remove(1)  // returns the removed `Node?` as `@discardableResult`

每条边都由它连接的两个节点标识，因此边 ID 是两个节点 ID 的组合。 边也是有向的，这意味着它们指向一个方向，从一个节点到另一个节点，我们可能会称之为“起始节点”和“目标节点”（或类似）。 有向边是最一般的形式。 如果客户端或算法使用“无向”图，则仅仅意味着它不关心边的方向。

三个基本操作是插入、读取和删除边

var graph: Graph<Int, Int, Double> = [1, 2, 3]  // values serve as node IDs

graph.insertEdge(from: 1, to: 2)  // returns the edge as `@discardableResult`
let edge = graph.edge(from: 1, to: 2)  // the optional edge itself
let hasEdge = graph.containsEdge(from: 1, to: 2)  // whether the edge exists
graph.removeEdge(from: 1, to: 2)  // returns the optional edge as `@discardableResult`

当然，Graph 也有属性提供所有边、所有边的 ID 和所有边 ID。 它还具有初始化和改变边权重的方法。 有关整个边 API，请参见 Graph.swift 和 Graph+EdgeAccess.swift。

节点基本上是可以被边连接的可识别值容器。 但是除了值之外，它们还存储相邻节点的 ID。 Graph 会及时更新此冗余存储（缓存），并使图遍历更加高效和方便。 任何给定的 node 都具有这些基于缓存的属性

node.descendantIDs  // IDs of all nodes to which there is an edge from node
node.ancestorIDs    // IDs of all nodes from which there is an edge to node
node.neighbourIDs   // all descendant- and ancestor IDs
node.isSink         // whether node has no descendants
node.isSource       // whether node has no ancestors

有关整个节点 API，请参见 Graph.swift 和 Graph+NodeAccess.swift。

许多图算法确实将小的中间结果与单个节点关联。 文献通常将其称为“标记”节点。 最突出的例子是在遍历潜在的循环图时将节点标记为已访问。 一些算法将多个不同的标记写入节点。

当我们使 SwiftNodes 并发安全（以与新的 Swift 并发功能很好地配合）时，我们取消了直接标记节点的功能，因为这已经失去了其性能优化的潜力。 请参阅 包含的算法 现在如何使用哈希将标记与节点关联。

像官方的 Swift 数据结构一样，Graph 是一个纯 struct 并继承了值类型的好处

• 您可以通过使用 var 或 let 来决定可变性。
• 您可以将 Graph 用作 SwiftUI 中的 @State 或 @Published 变量。
• 您可以使用属性观察器，如 didSet 来观察 Graph 中的更改。
• 您可以轻松复制整个 Graph。

许多算法都会生成给定图的变体。 SwiftNodes 建议复制图而不是修改原始图，您可以像复制任何其他值一样复制 Graph。

如果其值和 ID 类型是 Sendable，则 Graph 也是 Sendable。 因此，SwiftNodes 已准备好用于 Swift 6 的严格并发安全性。 您可以在 Actor 之间安全地共享 Sendable Graph 值。 请记住，要在 Sendable 引用类型上声明 Graph 属性，您需要使该属性保持不变（使用 let）。

SwiftNodes 已经开始积累一些图算法。 以下概述还链接到 Wikipedia 文章，这些文章解释了这些算法的作用。 我们建议也在代码中探索它们。

您可以映射图值，并按值、边和节点筛选图。 当然，过滤器会使边和节点邻居缓存保持一致，并产生适当的子图。

let graph: Graph<Int, Int, Int> = [1, 2, 10, 20]

let oneDigitGraph = graph.filtered { $0 < 10 }
let stringGraph = graph.map { "\($0)" }

请参阅 Graph+FilterAndMap.swift 中的所有筛选器。

graph.findComponents() 返回多个节点 ID 集合，这些节点 ID 代表 graph 的连通分量。

graph.findStronglyConnectedComponents() 返回多个节点 ID 集合，这些节点 ID 代表 graph 的强连通分量。

graph.makeCondensationGraph() 创建 graph 的凝聚图，该图是将原始 graph 的所有强连通分量折叠为单个节点的图，因此生成的凝聚图是非循环的。

graph.findTransitiveReductionEdges() 查找 graph 的传递归约（最小等效图）的所有边。 您还可以使用 filterTransitiveReduction() 和 filteredTransitiveReduction() 来创建图的 最小等效图。

目前，所有这些仅适用于非循环图，甚至可能会在循环图上挂起或崩溃。

graph.findEssentialEdges() 返回所有“基本”边的 ID。 您还可以使用 graph.filterEssentialEdges() 和 graph.filteredEssentialEdges() 从 graph 中删除所有“非基本”边。

当边对应于凝聚图的MEG（传递归约）的边时，边是基本的。 简单来说：基本边要么在循环中，要么对于图描述的可达性至关重要——即，除非破坏某些节点之间的唯一路径，否则无法删除它们。

请注意，只有凝聚图的边才可能不是基本的，因此循环中的边（即，在强连通分量中）都被认为是基本的。 这是因为从算法上以及概念上都很难确定循环中的哪些边是“非基本的”。 我们建议独立于使用此函数来处理循环。

graph.findNumberOfNodeAncestors() 返回一个 Dictionary<NodeID, Int>，其中包含 graph 中每个节点 ID 的祖先计数。祖先计数是该节点的所有（递归）祖先的数量。 基本上，它是可以到达该节点的其他节点的数量。

目前这只适用于无环图，并且对于环中的节点可能会返回不正确的结果。

祖先计数可以作为 拓扑排序 的替代方法。

这是 SwiftNodes 代码文件夹的架构（组成和关键依赖关系）

上面的图像是用 Codeface 创建的。

从版本/标签 0.1.0 开始，SwiftNodes 遵循 语义版本控制。 因此，在达到 1.0.0 之前，其 API 仍然可能经常发生重大变更，我们使用小版本号的提升来表示这些变更。

SwiftNodes 已经在生产环境中使用，但 Codeface 仍然是其主要客户端。 只要满足以下条件**之一**，SwiftNodes 就会迁移到 1.0.0 版本

• 通过为多个真实世界的客户提供服务，已经验证了基本实用性和概念合理性。
• 我们认为它已经足够成熟（完善且稳定的 API，全面的测试，完整的文档以及对设计目标的扎实实现）。

1. 审查、更新和完善所有文档，包括 API 注释
2. 再次审查测试，并添加更多测试以全面覆盖 API
3. 完善并添加算法（从 Codeface 的需求开始）
   1. 使现有算法与环兼容（仍有两个算法不兼容）。 意味着：不要挂起或崩溃，也许抛出一个错误！
   2. 如果可能，迁移到 1.0.0 版本
   3. 添加通用图遍历算法（BFT，DFT，与潜在的循环图兼容）
   4. 添加更好的拓扑排序方法
   5. 近似 最小反馈弧集，以便 Codeface 可以猜测“错误”或意外的依赖关系，即为了打破所有循环而需要删除的最少依赖关系。
4. 可能会优化性能——但只能基于测量，并且只有在测量表明优化可以带来显着加速的情况下才能进行。 优化算法可能比优化数据结构本身更有效。
   • @inlinable 在这里可以发挥什么作用？
   • lazy 在这里可以发挥什么作用？