Graphs in Swift
//----------------Graphs in Swift----------------//
//Graphs are made out of nodes and edges. Let's create a struct to represent both
struct Node {
var value: Int?
var edges: [Edge]
init(value: Int?) {
self.value = value
self.edges = []
}
}
//Instead of having a set number of children, each node has an array of Edges
struct Edge {
var value: Int?
var nodeFrom: Node?
var nodeTo: Node?
init(value: Int?, nodeFrom: Node?, nodeTo: Node?) {
self.value = value
self.nodeFrom = nodeFrom
self.nodeTo = nodeTo
}
}
//We can use nodes and edges to form a Graph class
class Graph {
var nodes: [Node]
var edges: [Edge]
init(nodes: [Node], edges: [Edge]) {
self.nodes = nodes
self.edges = edges
}
func getEdgeList() -> [[Int]] {
var edgeList = [[Int]]()
for edgeObject in edges {
let edge = [edgeObject.value!, edgeObject.nodeFrom!.value!, edgeObject.nodeTo!.value!]
edgeList.append(edge)
}
return edgeList
}
// Don't return any Node or Edge objects!
// You'll return a 3D array
// The indices of the outer list represent "from" nodes.
// Each section in the array will store an array of arrays where the inner-most arrays look like
// (To Node Value, Edge Value)
func getAdjacencyList() -> [[[Int]]] {
let max = getMaxIndex()
var adjacencyList = [[[Int]]]()
for _ in 0...max {
adjacencyList.append([])
}
for edgeObject in edges {
if !adjacencyList[(edgeObject.nodeFrom?.value)!].isEmpty {
adjacencyList[(edgeObject.nodeFrom?.value)!].append([edgeObject.nodeTo!.value!, edgeObject.value!])
} else {
adjacencyList[edgeObject.nodeFrom!.value!] = [[edgeObject.nodeTo!.value!, edgeObject.value!]]
}
}
return adjacencyList
}
// Return a matrix, or 2D array.
// Row numbers represent from nodes.
// Column numbers represent to nodes.
// Store the edge values in each spot, and a 0 if no edge exists.
func getAdjacencyMatrix() -> [[Int]] {
let max = getMaxIndex()
var adjacencyMatrix = [[Int]]()
for _ in 0...max {
var newArray: [Int] = []
for _ in 0...max {
newArray.append(0)
}
adjacencyMatrix.append(newArray)
}
for edgeObject in edges {
adjacencyMatrix[(edgeObject.nodeFrom?.value)!][(edgeObject.nodeTo?.value)!] = edgeObject.value!
}
return adjacencyMatrix
}
// Helper to be used with adjacency list and adjacency matrix
// max node value determines the size of the array
func getMaxIndex() -> Int {
var maxIndex = 0
for node in nodes {
if node.value! > maxIndex {
maxIndex = node.value!
}
}
return maxIndex
}
// inserts an edge between the "to" and "from" nodes with the specified values
func insertEdgeWithValue(_ newEdgeValue: Int, nodeFromValue: Int, nodeToValue: Int) {
var fromFound: Node? = nil
var toFound: Node? = nil
for node in nodes {
if nodeFromValue == node.value {
fromFound = node
}
if nodeToValue == node.value {
toFound = node
}
}
if fromFound == nil {
fromFound = Node(value: nodeFromValue)
nodes.append(fromFound!)
}
if toFound == nil {
toFound = Node(value: nodeToValue)
nodes.append(toFound!)
}
let newEdge = Edge(value: newEdgeValue, nodeFrom: fromFound, nodeTo: toFound)
fromFound?.edges.append(newEdge)
toFound?.edges.append(newEdge)
edges.append(newEdge)
}
}
// Test cases
let node = Node(value: 1)
let graph = Graph(nodes: [node], edges: [])
graph.insertEdgeWithValue(100, nodeFromValue: 1, nodeToValue: 2)
graph.insertEdgeWithValue(101, nodeFromValue: 1, nodeToValue: 3)
graph.insertEdgeWithValue(102, nodeFromValue: 1, nodeToValue: 4)
graph.insertEdgeWithValue(103, nodeFromValue: 3, nodeToValue: 4)
print(graph.getEdgeList()) // Should be [(100, 1, 2), (101, 1, 3), (102, 1, 4), (103, 3, 4)]
print(graph.getAdjacencyList()) // Should be [[], [(2, 100), (3, 101), (4, 102)], [], [(4, 103)], []]
print(graph.getAdjacencyMatrix()) // Should be [[0, 0, 0, 0, 0], [0, 0, 100, 101, 102], [0, 0, 0, 0, 0], [0, 0, 0, 0, 103], [0, 0, 0, 0, 0]]
//----------------Graphs in Swift----------------//
Sign up here with your email
ConversionConversion EmoticonEmoticon