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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
|
/*
This source file is part of the Swift.org open source project
Copyright (c) 2024 Apple Inc. and the Swift project authors
Licensed under Apache License v2.0 with Runtime Library Exception
See https://swift.org/LICENSE.txt for license information
See https://swift.org/CONTRIBUTORS.txt for Swift project authors
*/
extension DirectedGraph {
/// Returns a list of all finite (acyclic) paths through the graph from a given starting point.
///
/// The paths are found in breadth first order, so shorter paths are earlier in the returned list.
///
/// - Note: Nodes that are reachable through multiple paths will be visited more than once.
///
/// - Important: If all paths through the graph are infinite (cyclic), this function return an empty list.
func allFinitePaths(from startingPoint: Node) -> [Path] {
var foundPaths = [Path]()
for (path, isLeaf, _) in accumulatingPaths(from: startingPoint) where isLeaf {
foundPaths.append(path)
}
return foundPaths
}
/// Returns a list of the finite (acyclic) paths through the graph with the shortest length from a given starting point.
///
/// The paths are found in breadth first order, so shorter paths are earlier in the returned list.
///
/// - Note: Nodes that are reachable through multiple paths will be visited more than once.
///
/// - Important: If all paths through the graph are infinite (cyclic), this function return an empty list.
func shortestFinitePaths(from startingPoint: Node) -> [Path] {
var foundPaths = [Path]()
for (path, isLeaf, _) in accumulatingPaths(from: startingPoint) where isLeaf {
if let lengthOfFoundPath = foundPaths.first?.count, lengthOfFoundPath < path.count {
// This path is longer than an already found path.
// All paths found from here on will be longer than what's already found.
break
}
foundPaths.append(path)
}
return foundPaths
}
/// Returns a set of all the reachable leaf nodes by traversing the graph from a given starting point.
///
/// - Important: If all paths through the graph are infinite (cyclic), this function return an empty set.
func reachableLeafNodes(from startingPoint: Node) -> Set<Node> {
var foundLeafNodes: Set<Node> = []
for (path, isLeaf, _) in accumulatingPaths(from: startingPoint) where isLeaf {
foundLeafNodes.insert(path.last!)
}
return foundLeafNodes
}
}
// MARK: Path sequence
extension DirectedGraph {
/// A path through the graph, including the start and end nodes.
typealias Path = [Node]
/// Information about the current accumulated path during iteration.
typealias PathIterationElement = (path: Path, isLeaf: Bool, cycleStartIndex: Int?)
/// Returns a sequence of accumulated path information from traversing the graph in breadth first order.
func accumulatingPaths(from startingPoint: Node) -> some Sequence<PathIterationElement> {
IteratorSequence(GraphPathIterator(from: startingPoint, in: self))
}
}
// MARK: Iterator
/// An iterator that traverses a graph in breadth first order and returns information about the accumulated path through the graph, up to the current node.
private struct GraphPathIterator<Node: Hashable>: IteratorProtocol {
var pathsToTraverse: [(Node, [Node])]
var graph: DirectedGraph<Node>
init(from startingPoint: Node, in graph: DirectedGraph<Node>) {
self.pathsToTraverse = [(startingPoint, [])]
self.graph = graph
}
mutating func next() -> DirectedGraph<Node>.PathIterationElement? {
guard !pathsToTraverse.isEmpty else { return nil }
// This is a breadth first search through the graph.
let (node, path) = pathsToTraverse.removeFirst()
// Note: unlike `GraphNodeIterator`, the same node may be visited more than once.
if let cycleStartIndex = path.firstIndex(of: node) {
return (path, false, cycleStartIndex)
}
let newPath = path + [node]
let neighbors = graph.neighbors(of: node)
pathsToTraverse.append(contentsOf: neighbors.map { ($0, newPath) })
return (newPath, neighbors.isEmpty, nil)
}
}
|
