/
UnweightedGraph.swift
133 lines (121 loc) · 5.48 KB
/
UnweightedGraph.swift
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
//
// UnweightedGraph.swift
// SwiftGraph
//
// Copyright (c) 2014-2019 David Kopec
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
/// A subclass of Graph with some convenience methods for adding and removing UnweightedEdges. WeightedEdges may be added to an UnweightedGraph but their weights will be ignored.
open class UnweightedGraph<V: Equatable & Codable>: Graph {
public var vertices: [V] = [V]()
public var edges: [[UnweightedEdge]] = [[UnweightedEdge]]() //adjacency lists
public init() {
}
required public init(vertices: [V]) {
for vertex in vertices {
_ = self.addVertex(vertex)
}
}
}
extension Graph where E == UnweightedEdge {
/// Initialize an UnweightedGraph consisting of path.
///
/// The resulting graph has the vertices in path and an edge between
/// each pair of consecutive vertices in path.
///
/// If path is an empty array, the resulting graph is the empty graph.
/// If path is an array with a single vertex, the resulting graph has that vertex and no edges.
///
/// - Parameters:
/// - path: An array of vertices representing a path.
/// - directed: If false, undirected edges are created.
/// If true, edges are directed from vertex i to vertex i+1 in path.
/// Default is false.
public static func withPath(_ path: [V], directed: Bool = false) -> Self {
let g = Self(vertices: path)
guard path.count >= 2 else {
return g
}
for i in 0..<path.count - 1 {
g.addEdge(fromIndex: i, toIndex: i+1, directed: directed)
}
return g
}
/// Initialize an UnweightedGraph consisting of cycle.
///
/// The resulting graph has the vertices in cycle and an edge between
/// each pair of consecutive vertices in cycle,
/// plus an edge between the last and the first vertices.
///
/// If cycle is an empty array, the resulting graph is the empty graph.
/// If cycle is an array with a single vertex, the resulting graph has the vertex
/// and a single edge to itself if directed is true.
/// If directed is false the resulting graph has the vertex and two edges to itself.
///
/// - Parameters:
/// - cycle: An array of vertices representing a cycle.
/// - directed: If false, undirected edges are created.
/// If true, edges are directed from vertex i to vertex i+1 in cycle.
/// Default is false.
public static func withCycle(_ cycle: [V], directed: Bool = false) -> Self {
let g = Self.withPath(cycle, directed: directed)
if cycle.count > 0 {
g.addEdge(fromIndex: cycle.count-1, toIndex: 0, directed: directed)
}
return g
}
/// This is a convenience method that adds an unweighted edge.
///
/// - parameter from: The starting vertex's index.
/// - parameter to: The ending vertex's index.
/// - parameter directed: Is the edge directed? (default `false`)
public func addEdge(fromIndex: Int, toIndex: Int, directed: Bool = false) {
addEdge(UnweightedEdge(u: fromIndex, v: toIndex, directed: directed), directed: directed)
}
/// This is a convenience method that adds an unweighted, undirected edge between the first occurence of two vertices. It takes O(n) time.
///
/// - parameter from: The starting vertex.
/// - parameter to: The ending vertex.
/// - parameter directed: Is the edge directed? (default `false`)
public func addEdge(from: V, to: V, directed: Bool = false) {
if let u = indexOfVertex(from), let v = indexOfVertex(to) {
addEdge(UnweightedEdge(u: u, v: v, directed: directed), directed: directed)
}
}
/// Check whether there is an edge from one vertex to another vertex.
///
/// - parameter from: The index of the starting vertex of the edge.
/// - parameter to: The index of the ending vertex of the edge.
/// - returns: True if there is an edge from the starting vertex to the ending vertex.
public func edgeExists(fromIndex: Int, toIndex: Int) -> Bool {
// The directed property of this fake edge is ignored, since it's not taken into account
// for equality.
return edgeExists(E(u: fromIndex, v: toIndex, directed: true))
}
/// Check whether there is an edge from one vertex to another vertex.
///
/// Note this will look at the first occurence of each vertex.
/// Also returns false if either of the supplied vertices cannot be found in the graph.
///
/// - parameter from: The starting vertex of the edge.
/// - parameter to: The ending vertex of the edge.
/// - returns: True if there is an edge from the starting vertex to the ending vertex.
public func edgeExists(from: V, to: V) -> Bool {
if let u = indexOfVertex(from) {
if let v = indexOfVertex(to) {
return edgeExists(fromIndex: u, toIndex: v)
}
}
return false
}
}