SwiftGraph 3.1

SwiftGraph 3.1

×

测试已测试✓
语言语言 SwiftSwift
许可 Apache-2.0
发布最新发布2021年2月
SPM支持 SPM✓

由 David Kopec 维护。

SwiftGraph 3.1

SwiftGraph

Swift Versions CocoaPods Version Carthage Compatible SPM Compatible CocoaPods Platforms Linux Compatible Twitter Contact Build Status Maintainability Test Coverage

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

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

安装

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，并已在上面进行测试。

CocoaPods

使用 CocoaPod SwiftGraph。

Carthage

请在您的 Cartfile 中添加以下内容

github "davecom/SwiftGraph" ~> 3.1

Swift 包管理器 (SPM)

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

文档

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

技巧和窍门

  • 要了解如何使用 SwiftGraph，请查看单元测试
  • 通过顶点索引插入边比插入需要查找索引的顶点对象要快得多
  • 一般来说，查找顶点索引的时间复杂度为 O(n)，其中 n 是图中顶点的数量
  • SwiftGraph 包含用于在图中查找两个顶点之间路径的函数 bfs() 和 dfs()，以及用于在加权图中查找最短路径的 dijkstra() 函数
  • 包括一个实现九尾问题的示例 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

isADAG 是 false，因为未检测到 cityGraph 是一个有向无环图（DAG）。

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

从纽约开始执行广度优先搜索，以找到 cityGraph 中以字母 "S" 打头的所有城市。

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

文档

源代码中包含大量使用最新的 Apple 文档技术的文档——所以你只需在 Xcode 中 alt 点击方法名称，就可以获得许多关于它的详细信息。我们还使用 Jazzy 来生成 HTML 文档。此外，以下是 SwiftGraph 中每个组件的概述

边

边将图中各个顶点连接起来。

  • Edge（协议）- 所有图中的边都必须符合的协议。图中的边是两个顶点之间的连接。顶点由其图形中的索引指定，索引是一个整数。所有 Edge 必须是 Codable。
  • UnweightedEdge - 这是为无权图实现的 Edge 的具体实现。
  • WeightedEdge - 这是为加权图实现 Edge 的具体实现。权重是一种泛型类型——可以是实现了 Comparable、Numeric 和 Codable 的任何类型。典型的权重类型是 Int 和 Float。

图

图是 SwiftGraph 的核心数据结构。当顶点被插入图形时，它们被分配一个整数索引，通常通过索引引用它们比通过顶点的实际对象要快。

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

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。以下方法用于。
    • 添加一个顶点
    • 获取顶点的索引
    • 找到索引/顶点的邻居
    • 找到索引/顶点的边
    • 检查从一个索引/顶点到另一个索引/顶点的边是否存在
    • 检查顶点是否在图中
    • 添加一个边
    • 删除两个索引/顶点之间的所有边
    • 删除特定的顶点（所有其他边关系会同时自动更新，因为它们的连接索引发生变化，所以这很慢 - 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() 检查返回的最小生成树。在 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 上提交拉取请求和打开问题。

我要感谢所有在过去几年里帮助改进 SwiftGraph 的贡献者们，并激励着我。按照 Apache 许可协议对 SwiftGraph 的贡献也意味着您将自己的贡献以与原始项目相同的许可协议发布。然而，Apache 许可协议是宽松的，只要您给予它及其作者适当的认可，您就可以将其包含在商业、封闭源代码产品中（实际上 SwiftGraph 已经被包含在多个产品中）。有关详细信息，请参阅 LICENSE。

如果您将 SwiftGraph 用于您的产品中，请与我联系让我知道。这会很酷。

未来方向

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

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