1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift open source project
//
// Copyright (c) 2024 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See http://swift.org/LICENSE.txt for license information
// See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
import struct DequeModule.Deque
/// Directed graph that stores edges in [adjacency lists](https://en.wikipedia.org/wiki/Adjacency_list).
@_spi(DontAdoptOutsideOfSwiftPMExposedForBenchmarksAndTestsOnly)
public struct DirectedGraph<Node> {
public init(nodes: [Node]) {
self.nodes = nodes
self.edges = .init(repeating: [], count: nodes.count)
}
public private(set) var nodes: [Node]
private var edges: [[Int]]
public mutating func addEdge(source: Int, destination: Int) {
self.edges[source].append(destination)
}
/// Checks whether a path via previously created edges between two given nodes exists.
/// - Parameters:
/// - source: `Index` of a node to start traversing edges from.
/// - destination: `Index` of a node to which a path could exist via edges from `source`.
/// - Returns: `true` if a path from `source` to `destination` exists, `false` otherwise.
@_spi(DontAdoptOutsideOfSwiftPMExposedForBenchmarksAndTestsOnly)
public func areNodesConnected(source: Int, destination: Int) -> Bool {
var todo = Deque<Int>([source])
var done = Set<Int>()
while !todo.isEmpty {
let nodeIndex = todo.removeFirst()
for reachableIndex in self.edges[nodeIndex] {
if reachableIndex == destination {
return true
} else if !done.contains(reachableIndex) {
todo.append(reachableIndex)
}
}
done.insert(nodeIndex)
}
return false
}
}
|
