Swift 图形库

Supported Swift versions Supported Swift platforms

Swift Graphs 库为处理图形提供了可组合且可扩展的基础。无论您是构建二叉树、执行复杂的图形遍历，还是优化加权图上的寻路算法，此库都提供了广泛图形相关用例所需的动态灵活性。

虽然某些功能仍处于早期开发阶段，但该项目正在积极发展，并强烈鼓励贡献。

文档 »

主要特性

示例用法

let graph = ConnectedGraph(edges: [
    "Root": ["A", "B", "C"],
    "B": ["X", "Y", "Z"]
])

graph.traverse(from: "Root", strategy: .bfs())
graph.traverse(from: "Root", strategy: .dfs())

graph.traverse(from: "Root", strategy: .bfs(.trackPath()))
graph.traverse(from: "Root", strategy: .dfs(order: .postorder()))
graph.traverse(from: "Root", strategy: .dfs().visitEachNodeOnce())

graph.shortestPath(from: "Root", to: "Z", using: .dijkstra()) // or .aStar() or .bellmanFord()
graph.shortestPaths(from: "Root", using: .dijkstra()) // or .bellmanFord()
graph.shortestPathsForAllPairs(using: .floydWarshall()) // or .johnson()
graph.minimumSpanningTree(using: .kruskal()) // or .prim() or .boruvka()
graph.maximumFlow(using: .fordFulkerson()) // or .edmondsKarp() or .dinic()
graph.stronglyConnectedComponents(using: .kosaraju()) // or .tarjan()
graph.colorNodes(using: .greedy()) // or .dsatur() or .welshPowell()
graph.isIsomorphoc(to: graph2, using: .vf2()) // or .weisfeilerLehman()
ConnectedGraph.random(using: .erdosRenyi()) // or .barabasiAlbert() or .wattsStrogatz() 

graph.isCyclic()
graph.isTree()
graph.isConnected()
graph.isPlanar()
graph.isBipartite()
graph.topologicalSort()

let lazyGraph = LazyGraph { node in
    dynamicNeighbors(of: node)
}

let gridGraph = GridGraph(grid: [
    ["A", "B", "C", "D", "E"],
    ["F", "G", "H", "I", "J"],
    ["K", "L", "M", "N", "O"],
    ["P", "Q", "R", "S", "T"],
    ["U", "V", "W", "X", "Y"]
], availableDirections: .orthogonal).weightedByDistance()

gridGraph.shortestPath(from: GridPosition(x: 0, y: 0), to: GridPosition(x: 4, y: 4), using: .aStar(heuristic: .euclideanDistance(of: \.coordinates)))
gridGraph.shortestPaths(from: GridPosition(x: 0, y: 0))
gridGraph.shortestPathsForAllPairs()

gridGraph.eulerianCycle()
gridGraph.eulerianPath()

gridGraph.hamiltonianCycle()
gridGraph.hamiltonianPath()
gridGraph.hamiltonianPath(from: GridPosition(x: 0, y: 0))
gridGraph.hamiltonianPath(from: GridPosition(x: 0, y: 0), to: GridPosition(x: 4, y: 4))

let binaryGraph = ConnectedBinaryGraph(edges: [
    "Root": (lhs: "A", rhs: "B"),
    "A": (lhs: "X", rhs: "Y"),
    "Y": (lhs: nil, rhs: "Z")
])
binaryGraph.traverse(from: "Root", strategy: .dfs(order: .inorder()))

let bipartite = ConnectedGraph(edges: [
    GraphEdge(source: "u1", destination: "v1"),
    GraphEdge(source: "u1", destination: "v2"),
    GraphEdge(source: "u2", destination: "v1"),
    GraphEdge(source: "u3", destination: "v2"),
    GraphEdge(source: "u3", destination: "v3"),
]).bipartite(leftPartition: ["u1", "u2", "u3"], rightPartition: ["v1", "v2", "v3"])

bipartite.maximumMatching(using: .hopcroftKarp())

安装

在您项目的 Package.swift 中添加 swift-graphs 作为包依赖项

// swift-tools-version:6.0
import PackageDescription

let package = Package(
    name: "MyPackage",
    dependencies: [
        .package(url: "https://github.com/tevelee/swift-graphs.git", from: "0.2.0")
    ],
    targets: [
        .target(name: "MyTarget", dependencies: [
            .product(name: "Graphs", package: "swift-graphs")
        ])
    ]
)

设计考虑

通用结构

该库建立在完全通用的结构之上，允许将所有节点和边定义为无约束的泛型类型。这种灵活性使得各种算法可以无缝集成到专门的图形上，例如加权图。通过使用泛型，该库确保算法保持广泛适用性的同时，针对特定图形类型进行了优化。

例如，二叉图可以利用专门的中序深度优先搜索，而分层遍历策略（例如唯一节点访问或路径跟踪）可以轻松添加到任何算法中。泛型约束有助于形式化需求，确保像 Dijkstra 算法这样的算法避免负权重以获得最佳性能。

可组合的组件和算法

该库的设计考虑了可组合性。类似于 Swift 标准库转换集合的方式（例如，ReversedCollection），此库提供了高效的图形转换，例如 TransposedGraph 或 UndirectedGraph。算法可以分层和动态扩展。

强大的默认值和灵活性

此库中的图形默认是有向的，允许将无向（双向）边作为转换分层。提供了合理的算法默认值，因此用户可以轻松上手，而无需手动指定算法。但是，用户可以保留在需要时使用特定解决方案覆盖默认值的灵活性。

可扩展的算法

库中的算法构建为具有多个内置默认值的抽象定义。但是，该架构允许用户在需要时插入自己的算法。例如，虽然提供了 Kruskal 和 Prim 算法用于查找最小生成树，但用户可以实现自己的反向删除算法，同时保持与相同 API 的兼容性。

灵活的图形声明

该库的基础是 Graph 协议，它仅需要一个方法：定义从节点发出的边。这种极简主义设计支持广泛的算法——例如遍历、最短路径和最小生成树——而无需复杂的接口。

多种具体的图形类型都符合此协议，包括急切表示（ConnectedGraph、DisjointGraph、ConnectedBinaryGraph 等）和优化的惰性评估（LazyGraph、LazyBinaryGraph）。诸如 WeightedGraph 之类的专用类型管理加权边，而 GridGraph 为基于 2D 网格的图形提供了方便的结构。

贡献

虽然核心库提供了坚实的基础，但某些领域仍在开发中，尚未经过全面的生产测试。强烈鼓励贡献、建议和反馈。欢迎随时提交问题、发起功能请求讨论，并通过拉取请求贡献代码。