SwiftGraph

SwiftGraph 是一个纯 Swift (无 Cocoa) 实现的图数据结构，适用于 Swift 支持的所有平台（iOS、macOS、Linux 等）。它支持带权图、无权图、有向图和无向图。它使用泛型来抽象顶点类型和权重类型。

它包含了大量的源代码文档、单元测试以及用于执行诸如广度优先搜索、深度优先搜索和 Dijkstra 算法等操作的搜索函数。此外，它还包括用于拓扑排序、Jarnik 算法（用于查找最小生成树）、检测 DAG（有向无环图）、枚举所有环等的实用函数。

SwiftGraph 3.0 及以上版本需要 Swift 5 (Xcode 10.2)。使用 SwiftGraph 2.0 支持 Swift 4.2 (Xcode 10.1)，SwiftGraph 1.5.1 支持 Swift 4.1 (Xcode 9)，SwiftGraph 1.4.1 支持 Swift 3 (Xcode 8)，SwiftGraph 1.0.6 支持 Swift 2 (Xcode 7)，SwiftGraph 1.0.0 支持 Swift 1.2 (Xcode 6.3)。 SwiftGraph 支持 GNU/Linux 并在其上进行了测试。

使用 CocoaPod SwiftGraph。

将以下内容添加到您的 Cartfile 中

github "davecom/SwiftGraph" ~> 3.1

使用此存储库作为您的依赖项。

将 Sources 文件夹中的所有源文件复制到您的项目中。

• 要了解如何使用 SwiftGraph，请查看单元测试
• 通过顶点索引插入边比通过需要查找索引的顶点对象插入边要快得多
• 通常，查找顶点的索引需要 O(n) 时间，其中 n 是图中顶点的数量
• SwiftGraph 包含函数 bfs() 和 dfs()，用于查找图中一个顶点和另一个顶点之间的路径，以及 dijkstra()，用于查找带权图中的最短路径
• 包含了一个实现 Nine Tails 问题的示例 Mac 应用程序 - 只需将项目的目标更改为 SwiftGraphSampleApp 即可构建它

有关更多详细信息，请查看文档部分，但此示例构建了一个美国城市加权图并对其进行了一些操作，应该可以帮助您入门。

let cityGraph: WeightedGraph<String, Int> = WeightedGraph<String, Int>(vertices: ["Seattle", "San Francisco", "Los Angeles", "Denver", "Kansas City", "Chicago", "Boston", "New York", "Atlanta", "Miami", "Dallas", "Houston"])

cityGraph 是一个具有 String 顶点和 Int 边的权重的 WeightedGraph。

cityGraph.addEdge(from: "Seattle", to:"Chicago", weight:2097)
cityGraph.addEdge(from: "Seattle", to:"Chicago", weight:2097)
cityGraph.addEdge(from: "Seattle", to: "Denver", weight:1331)
cityGraph.addEdge(from: "Seattle", to: "San Francisco", weight:807)
cityGraph.addEdge(from: "San Francisco", to: "Denver", weight:1267)
cityGraph.addEdge(from: "San Francisco", to: "Los Angeles", weight:381)
cityGraph.addEdge(from: "Los Angeles", to: "Denver", weight:1015)
cityGraph.addEdge(from: "Los Angeles", to: "Kansas City", weight:1663)
cityGraph.addEdge(from: "Los Angeles", to: "Dallas", weight:1435)
cityGraph.addEdge(from: "Denver", to: "Chicago", weight:1003)
cityGraph.addEdge(from: "Denver", to: "Kansas City", weight:599)
cityGraph.addEdge(from: "Kansas City", to: "Chicago", weight:533)
cityGraph.addEdge(from: "Kansas City", to: "New York", weight:1260)
cityGraph.addEdge(from: "Kansas City", to: "Atlanta", weight:864)
cityGraph.addEdge(from: "Kansas City", to: "Dallas", weight:496)
cityGraph.addEdge(from: "Chicago", to: "Boston", weight:983)
cityGraph.addEdge(from: "Chicago", to: "New York", weight:787)
cityGraph.addEdge(from: "Boston", to: "New York", weight:214)
cityGraph.addEdge(from: "Atlanta", to: "New York", weight:888)
cityGraph.addEdge(from: "Atlanta", to: "Dallas", weight:781)
cityGraph.addEdge(from: "Atlanta", to: "Houston", weight:810)
cityGraph.addEdge(from: "Atlanta", to: "Miami", weight:661)
cityGraph.addEdge(from: "Houston", to: "Miami", weight:1187)
cityGraph.addEdge(from: "Houston", to: "Dallas", weight:239)

便捷方法用于在各个顶点之间添加 WeightedEdge 连接。

let (distances, pathDict) = cityGraph.dijkstra(root: "New York", startDistance: 0)
var nameDistance: [String: Int?] = distanceArrayToVertexDict(distances: distances, graph: cityGraph)
// shortest distance from New York to San Francisco
let temp = nameDistance["San Francisco"] 
// path between New York and San Francisco
let path: [WeightedEdge<Int>] = pathDictToPath(from: cityGraph.indexOfVertex("New York")!, to: cityGraph.indexOfVertex("San Francisco")!, pathDict: pathDict)
let stops: [String] = cityGraph.edgesToVertices(edges: path)

使用 Dijkstra 算法找到图中各个顶点之间的最短路径。

let mst = cityGraph.mst()

找到连接图中所有顶点的最小生成树。

let cycles = cityGraph.detectCycles()

找到 cityGraph 中的所有环。

let isADAG = cityGraph.isDAG

由于 cityGraph 未被发现是有向无环图，因此 isADAG 为 false。

let result = cityGraph.findAll(from: "New York") { v in
    return v.characters.first == "S"
}

从纽约开始，对 cityGraph 中所有以字母“S”开头的城市执行广度优先搜索。

SwiftGraph 包含许多更有用的功能，但希望这个例子是一个不错的快速入门。

源代码中使用了最新的 Apple 文档技术，包含了大量的文档 - 因此您应该能够直接按住 Alt 键并单击方法名称，以在 Xcode 中获取有关它的许多有用信息。我们还使用 Jazzy 生成 HTML 文档。此外，这里概述了 SwiftGraph 的每个组件

边将图中的顶点相互连接。

• Edge (协议) - 图中所有边都必须遵循的协议。边是图中两个顶点之间的连接。顶点由它们在图中的索引指定，这是一个整数。所有 Edge 都必须是 Codable。
• UnweightedEdge - 这是无权图的 Edge 的具体实现。
• WeightedEdge - 这是带权图的 Edge 的具体实现。权重是一种泛型类型 - 它可以是任何实现 Comparable、Numeric 和 Codable 的东西。典型的权重类型是 Int 和 Float。

图是 SwiftGraph 的核心数据结构。所有顶点在插入到图中时都会被分配一个整数索引，并且通常通过索引引用它们比通过顶点的实际对象引用它们更快。

图实现了标准的 Swift 协议 Collection（用于迭代所有顶点以及通过下标按索引获取顶点）和 Codable。例如，以下示例在单独的行上打印图中的所有顶点

for v in g {  // g is a Graph<String>
    print(v)
}

我们可以使用下标通过索引获取特定的顶点

print(g[23]) // g is a Graph<String>

注意：目前，图是非线程安全的。但是，一旦构建了图，如果您只进行查找和搜索（不删除顶点/边，也不添加顶点/边），那么您应该能够从多个线程执行此操作。完全线程安全的图形实现是可能的未来方向。

• Graph (协议) - 这是所有图的基本协议。通常，您应该使用其规范的类实现之一，UnweightedGraph 或 WeightedGraph，而不是推出自己的适配器，因为它们提供了重要的内置功能。 Graph 中的顶点（定义为图创建时的泛型）可以是符合 Equatable 和 Codable 的任何类型。所有 Graph 都是 Codable。 Graph 具有以下方法：
  • 添加顶点
  • 获取顶点的索引
  • 查找索引/顶点的邻居
  • 查找索引/顶点的边
  • 检查从一个索引/顶点到另一个索引/顶点是否存在边
  • 检查顶点是否在图中
  • 添加边
  • 删除两个索引/顶点之间的所有边
  • 删除特定顶点（所有其他边关系都会自动同时更新（因为它们的连接的索引会发生变化），所以这很慢 - O(v + e)，其中 v 是顶点的数量，e 是边的数量）
• UnweightedGraph - Graph 的一个泛型类实现，它添加了用于添加和删除 UnweightedEdge 类型边的便捷方法。 UnweightedGraph 是顶点类型的泛型。
• WeightedGraph - Graph 的一个泛型类实现，它添加了用于添加和删除 WeightedEdge 类型边的便捷方法。 WeightedGraph 还添加了一种方法，用于返回一个元组列表，其中包含索引的所有相邻顶点以及它们各自的权重。 WeightedGraph 是顶点和权重类型的泛型。
• UniqueElementsGraph - Graph 的一个实现，支持联合操作，确保图中的所有顶点和边都是唯一的。

搜索方法在 Search.swift 中的 Graph 和 WeightedGraph 的扩展中定义。

• bfs() (Graph 上的方法) - 使用广度优先搜索在 Graph 中查找从一个顶点到另一个顶点的路径。返回一个从源顶点到目标顶点的 Edge 数组，如果找不到路径，则返回一个空数组。此方法的一个版本接受一个函数 goalTest()，该函数对顶点进行操作并返回一个布尔值，以指示它是否是搜索的目标。它返回到第一个从 goalTest() 返回 true 的顶点的路径。
• dfs() (Graph 上的方法) - 使用深度优先搜索在 Graph 中查找从一个顶点到另一个顶点的路径。返回一个从源顶点到目标顶点的 Edge 数组，如果找不到路径，则返回一个空数组。此方法的一个版本接受一个函数 goalTest()，该函数对顶点进行操作并返回一个布尔值，以指示它是否是搜索的目标。它返回到第一个从 goalTest() 返回 true 的顶点的路径。
• findAll() 使用广度优先搜索来查找从起始顶点开始的所有连接顶点，这些顶点在通过 goalTest() 函数运行时返回 true。连接顶点的路径在数组中返回，如果未找到任何顶点，则该数组为空。
• dijkstra() (WeightedGraph 上的方法) - 查找从起始顶点到 WeightedGraph 中每个其他顶点的最短路径。返回一个元组，其第一个元素是按索引排列的到图中每个顶点的距离数组。元组的第二个元素是一个字典，它将图索引映射到从起始顶点以最短时间到达它们的先前的 Edge。使用此字典和函数 pathDictToPath()，您可以找到从起始顶点到任何其他连接顶点的最短路径。请参阅 DijkstraGraphTests.swift 中的 dijkstra() 单元测试以获取演示。
• bfs() 和 dfs() 的图形遍历版本，允许在每个停止点执行访问函数

Sort.swift 中 Graph 的扩展提供了拓扑排序和检测 DAG 的工具。

• topologicalSort() - 如果可能，则对给定图中的顶点进行拓扑排序（如果找到循环则返回 nil）。返回顶点的排序列表。以 O(n) 时间运行。
• isDAG - 一个属性，它使用 topologicalSort() 来确定图是否是 DAG（有向无环图）。以 O(n) 时间运行。

MST.swift 中 WeightedGraph 的扩展可以从带权图中找到最小生成树。

• mst() - 使用 Jarnik 算法（又名 Prim 算法）来查找由连接带权图中所有顶点的最小累积权重组成的树。这假定图是完全无向和连接的。如果图有向边，它可能不会返回正确的答案。此外，如果图未完全连接，它将为起始顶点所属的连接组件创建树。返回组成树的 WeightedEdge 数组。使用实用函数 totalWeight() 和 printMST() 来检查返回的 MST。以 O(n lg n) 时间运行。

Cycles.swift 中 Graph 的扩展会找到图中的所有循环。

• detectCycles() - 使用 Liu/Wang 开发的算法来查找图中的所有循环。可选地，此方法可以采用一个参数 upToLength，该参数指定停止搜索循环的长度。例如，如果 upToLength 为 3，则 detectCycles() 将找到所有 1 个顶点循环（自循环，具有指向自身的边的顶点）和 3 个顶点循环（连接到另一个顶点并返回，存在于所有具有 1 个以上顶点的无向图中）。没有 2 个顶点循环这样的东西。

Reversed.swift 中 Graph 的扩展会反转图中的所有边。

SwiftGraph 由 David Kopec 和其他贡献者编写（请参阅 CONTRIBUTORS.md）。它是在 Apache 许可证下发布的（请参阅 LICENSE）。您可以在我的 GitHub 个人资料页面上找到我的电子邮件地址。我鼓励您在 GitHub 上提交 pull request 并提出 issue。

我衷心感谢多年来帮助改进 SwiftGraph 并不断激励我的所有贡献者。 按照 Apache 许可协议的规定，向 SwiftGraph 贡献代码意味着您也要以与原始项目相同的许可协议发布您的贡献。 然而，Apache 许可协议是宽松的，您可以自由地将 SwiftGraph 包含在商业、闭源产品中，只要您注明它及其作者（事实上，SwiftGraph 已经应用于多个产品中）。 有关详细信息，请参见 LICENSE 文件。

如果您在您的产品中使用 SwiftGraph，请与我联系并告知我。 这仅仅是让人觉得很酷的事情。

该项目未来的发展方向可能包括：

• 更多实用工具函数
• Graph 的线程安全实现
• 更广泛的性能测试
• GraphML 和其他格式的支持