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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
|
/*
This source file is part of the Swift.org open source project
Copyright (c) 2014 - 2017 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 Swift project authors
*/
public enum GraphError: Error {
/// A cycle was detected in the input.
case unexpectedCycle
}
/// Compute the transitive closure of an input node set.
///
/// - Note: The relation is *not* assumed to be reflexive; i.e. the result will
/// not automatically include `nodes` unless present in the relation defined by
/// `successors`.
public func transitiveClosure<T>(
_ nodes: [T], successors: (T) throws -> [T]
) rethrows -> Set<T> {
var result = Set<T>()
// The queue of items to recursively visit.
//
// We add items post-collation to avoid unnecessary queue operations.
var queue = nodes
while let node = queue.popLast() {
for succ in try successors(node) {
if result.insert(succ).inserted {
queue.append(succ)
}
}
}
return result
}
/// Perform a topological sort of an graph.
///
/// This function is optimized for use cases where cycles are unexpected, and
/// does not attempt to retain information on the exact nodes in the cycle.
///
/// - Parameters:
/// - nodes: The list of input nodes to sort.
/// - successors: A closure for fetching the successors of a particular node.
///
/// - Returns: A list of the transitive closure of nodes reachable from the
/// inputs, ordered such that every node in the list follows all of its
/// predecessors.
///
/// - Throws: GraphError.unexpectedCycle
///
/// - Complexity: O(v + e) where (v, e) are the number of vertices and edges
/// reachable from the input nodes via the relation.
public func topologicalSort<T: Hashable>(
_ nodes: [T], successors: (T) throws -> [T]
) throws -> [T] {
// Implements a topological sort via recursion and reverse postorder DFS.
func visit(_ node: T,
_ stack: inout OrderedSet<T>, _ visited: inout Set<T>, _ result: inout [T],
_ successors: (T) throws -> [T]) throws {
// Mark this node as visited -- we are done if it already was.
if !visited.insert(node).inserted {
return
}
// Otherwise, visit each adjacent node.
for succ in try successors(node) {
guard stack.append(succ) else {
// If the successor is already in this current stack, we have found a cycle.
//
// FIXME: We could easily include information on the cycle we found here.
throw GraphError.unexpectedCycle
}
try visit(succ, &stack, &visited, &result, successors)
let popped = stack.removeLast()
assert(popped == succ)
}
// Add to the result.
result.append(node)
}
// FIXME: This should use a stack not recursion.
var visited = Set<T>()
var result = [T]()
var stack = OrderedSet<T>()
for node in nodes {
precondition(stack.isEmpty)
stack.append(node)
try visit(node, &stack, &visited, &result, successors)
let popped = stack.removeLast()
assert(popped == node)
}
return result.reversed()
}
/// Finds the first cycle encountered in a graph.
///
/// This method uses DFS to look for a cycle and immediately returns when a
/// cycle is encountered.
///
/// - Parameters:
/// - nodes: The list of input nodes to sort.
/// - successors: A closure for fetching the successors of a particular node.
///
/// - Returns: nil if a cycle is not found or a tuple with the path to the start of the cycle and the cycle itself.
public func findCycle<T: Hashable>(
_ nodes: [T],
successors: (T) throws -> [T]
) rethrows -> (path: [T], cycle: [T])? {
// Ordered set to hold the current traversed path.
var path = OrderedSet<T>()
var validNodes = Set<T>()
// Function to visit nodes recursively.
// FIXME: Convert to stack.
func visit(_ node: T, _ successors: (T) throws -> [T]) rethrows -> (path: [T], cycle: [T])? {
if validNodes.contains(node) { return nil }
// If this node is already in the current path then we have found a cycle.
if !path.append(node) {
let index = path.firstIndex(of: node)!
return (Array(path[path.startIndex..<index]), Array(path[index..<path.endIndex]))
}
for succ in try successors(node) {
if let cycle = try visit(succ, successors) {
return cycle
}
}
// No cycle found for this node, remove it from the path.
let item = path.removeLast()
assert(item == node)
validNodes.insert(node)
return nil
}
for node in nodes {
if let cycle = try visit(node, successors) {
return cycle
}
}
// Couldn't find any cycle in the graph.
return nil
}
|
