swift-build/Tests/SWBUtilTests/GraphAlgorithmsTests.swift at main · ian-twilightcoder/swift-build · GitHub

Name: swift-build/Tests/SWBUtilTests/GraphAlgorithmsTests.swift at main · ian-twilightcoder/swift-build · GitHub
Rating: 4.6 (4291 reviews)
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
//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift open source project
//
// Copyright (c) 2025 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 Foundation
import Testing
import SWBUtil

@SuitefileprivatestructGraphAlgorithmsTests{
@Test
func minimumDistance(){
 #expect(SWBUtilTests.minimumDistance(from:1, to:2, in:[1:[2]])==1)

 // Check we find the minimum.
 #expect(SWBUtilTests.minimumDistance(from:1, to:5, in:[1:[2,3],2:[4],3:[5],4:[5]])==2)
 #expect(SWBUtilTests.minimumDistance(from:1, to:5, in:[1:[3,2],2:[4],3:[5],4:[5]])==2)

 // Check we handle missing.
 #expect(SWBUtilTests.minimumDistance(from:1, to:3, in:[1:[2]])==nil)

 // Check we handle cycles.
 #expect(SWBUtilTests.minimumDistance(from:1, to:3, in:[1:[2],2:[1]])==nil)
}

@Test
func shortestPath(){
 #expect(SWBUtilTests.shortestPath(from:1, to:2, in:[1:[2]])! ==[1,2])

 // Check we find the minimum.
 #expect(SWBUtilTests.shortestPath(from:1, to:5, in:[1:[2,3],2:[4],3:[5],4:[5]])! ==[1,3,5])
 #expect(SWBUtilTests.shortestPath(from:1, to:5, in:[1:[3,2],2:[4],3:[5],4:[5]])! ==[1,3,5])

 // Check we handle missing.
 #expect(SWBUtilTests.shortestPath(from:1, to:3, in:[1:[2]])==nil)

 // Check we handle cycles.
 #expect(SWBUtilTests.shortestPath(from:1, to:3, in:[1:[2],2:[1]])==nil)
}

@Test
func transitiveClosure(){
 #expect([2]==SWBUtilTests.transitiveClosure(1,[1:[2]]))
 #expect([]==SWBUtilTests.transitiveClosure(2,[1:[2]]))
 #expect([2]==SWBUtilTests.transitiveClosure([2,1],[1:[2]]))

 // A diamond.
letdiamond:[Int:[Int]]=[
1:[3,2],
2:[4],
3:[4]
]
 #expect([2,3,4]==SWBUtilTests.transitiveClosure(1, diamond))
 #expect([4]==SWBUtilTests.transitiveClosure([3,2], diamond))
 #expect([2,3,4]==SWBUtilTests.transitiveClosure([4,3,2,1], diamond))

 // Test cycles.
 #expect([1]==SWBUtilTests.transitiveClosure(1,[1:[1]]))
 #expect([1,2]==SWBUtilTests.transitiveClosure(1,[1:[2],2:[1]]))
}

@Test
func transitiveClosureDupes(){
letdiamond:[Int:[Int]]=[
1:[3,2],
2:[4],
3:[4]
]
letdupes=SWBUtil.transitiveClosure([4,3,2,1], successors:{diamond[$0]??[]}).1
 #expect([4]== dupes)
}

}

privatefunc minimumDistance<T>(
 from source:T, to destination:T, in graph:[T:[T]]
)->Int?{
returnminimumDistance(from: source, to: destination, successors:{graph[$0]??[]})
}

privatefunc shortestPath<T>(
 from source:T, to destination:T, in graph:[T:[T]]
)->[T]?{
returnshortestPath(from: source, to: destination, successors:{graph[$0]??[]})
}

privatefunc transitiveClosure(_ nodes:[Int], _ successors:[Int:[Int]])->[Int]{
returntransitiveClosure(nodes, successors:{successors[$0]??[]}).0.map{$0}.sorted()
}
privatefunc transitiveClosure(_ node:Int, _ successors:[Int:[Int]])->[Int]{
returntransitiveClosure([node], successors)
}